Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1034. Gangs
Комбинаторика, теория ПойаОлимпиадные задачи на английском языке
| 03/07/2008 | Лето 2008 дорешивание (12A) |
| 28/07/2008 | Лето 2008 - 12 (A) |
| 24/07/2013 | Лето 2013-16 (командная) (A) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
The downtown core of Inner City is laid out as a grid, with numbered
streets running north-south from 1st Street in the west to 20th
Street in the east, and numbered avenues running east-west from 1st
Avenue in the north to 20th Avenue in the south. The area is
controlled by two gangs, the Blips and the Cruds. The boundary between
their territory is the Green Line, running diagonally from the
intersection of 1st Street and 1st Avenue to the intersection of 20th
Street and 20th Avenue. The Blips control the area to the southwest of
the Green Line, and the Cruds the area to the northeast.
To prove their virility, the Blips go on "runs" through Crud
territory, starting at 1st Avenue and 1st Street and ending at a point
on the Green Line that varies from night to night. A run may return to
the Green Line in between but never crosses it. A run uses avenues
only in the east direction and streets only in the south
direction. Thus a run can be described by a string of E's and S's of
length `2*N-2`; such a run ends at `N`th Street and `N`th Avenue.
The Blips judge the runs made on a given night (all of which have the
same length) by how "OG" they are. A run `R_1` is more OG than a run `R_2`
if and only if:
- `R_2` returns to the Green Line for the first time at an earlier point than when `R_1` returns to the Green Line, or
- `R_1` and `R_2` return to the Green Line at the same point, but the portion of `R_1` to that point (ignoring the initial E and final S) is more OG than the portion of R2 to that point (also ignoring the initial E and final S), or
- `R_1` and `R_2` return to the Green Line at the same point and are identical to that point, but the rest of `R_1` is more OG than the rest of `R_2`.
Examples corresponding to these three cases:
- EESS is more OG than ESES.
- EEESSS is more OG than EESESS.
- EESSEESS is more OG than EESSESES.
If all the runs of a given length are ordered according to how OG they
are, then the rank of a run is its position in the resulting
list. EESS has rank 1 and ESES has rank 2.
Your task is to write a program to help the Blips plan and judge their
nightly activities.
The input to the program is a series of
instances followed by 0 0.
An instance
consists of a line containing a positive integer `N`, representing the terminus
of that night's run (`N`th Street and `N`th Avenue), followed by positive integer `M`.
The output corresponding to each instance is the run of length `2*N-2`
of rank `M`, or ERROR if there are fewer than `M` runs of length `2*N-2`.
Sample Input
3 1 3 2 3 3 0 0
Output for Sample Input
EESS ESES ERROR
