루미 알고리즘

#1577플래티넘Floor Area

PO 2024 결선코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

You are soon going to sell your house, but first, you need to figure out the size of the floor area. It might sound easy, but you have an unused storage room for which you've lost the key, and you have no idea how big the storage room is. The only thing in the storage room is a robot vacuum cleaner. If you start the vacuum cleaner and see where it ends up, maybe you can figure out how big the storage room is?

The storage room consists of an N × M grid, where N and M are unknown positive integers. The rows are numbered from 0 to N-1 from top to bottom, and the columns are numbered from 0 to M-1 from left to right. The robot has a list of instructions s. The instructions are described by a string consisting of the characters <, >, ^, and v. When the robot is started, it reads these instructions, and for each one, it moves one step in the corresponding direction. If the robot tries to move outside the grid, then it hits a wall and nothing happens. The robot starts in the upper-left corner, i.e., at row 0 and column 0.

You are given the string s and the row and column where the robot ended up after following the instructions. Calculate the smallest possible value of N · M that is consistent with this information.

Input

The first line contains an integer K (1 ≤ K ≤ 3 · 10^5), the length of the string s.

The second line contains the string s.

The third line contains two integers r and c (0 ≤ r,c < 3 · 10^5), where r is the row where the robot ended up, and c is the column where it ended up.

Output

Print an integer, the smallest possible value of N · M. If there is no choice of N and M consistent with the information in the test data, then print -1 instead.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
115The robot only moves down and to the right.
230K ≤ 100
320K ≤ 5000
435No additional constraints.

Explanation of sample case

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: The picture shows the smallest possible grid in sample case 1. The robot travels according to the black curve. The dark square is the robot's final position.

예제

예제 1

입력
14
>v<v>v>^^^>>v<
1 2
출력
8

예제 2

입력
1
>
100000 100000
출력
-1

예제 3

입력
4
>><<
0 0
출력
1

출처 표기

출처: Programmeringsolympiaden 2024년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.