Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Разбор случаев

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

12/12/2013 | Занятие 12 для продолжающих (Задачи NEERC 2013) (K) |

*Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Kabaleo Lite is a board game. The board consists of several stacks of conical chips of various colors.
Only the color of the top chip of the stack is visible.

Each player has a unique *target color* and a set of colored chips. The target color is hidden from other
players, while the set of chips is visible to them. On his turn, player selects one of his chips and puts it
on one of the board stacks, thus recoloring it to the color of the chosen chip.

After the last turn, the number of visible board chips of each color is calculated. The winning color is
the color that occurs the maximum times. The player (if any) that has this color as his target color, wins
the game. If there is no such player or if there are two or more colors that occur the maximum times,
the game ends in a draw.

You are playing your last chip in the Kabaleo Lite game. Other players also have one chip left. You want
to determine all possible moves that lead you to winning the game. You do not know the target colors of
other players and you cannot predict their moves, so your move must guarantee your victory regardless
of moves of your opponents.

The first line contains four integers `n`, `p`, `c` and `h` – the number of stacks
on the board (`1\ ≤\ n\ ≤\ 10^6`),
the number of players (`1\ ≤\ p\ ≤\ 10^6`), the number of chips' colors (`p\ ≤\ c\ ≤\ 10^6`), and your hidden color
(`1\ ≤\ h\ ≤\ c`).

The second line contains `n` integers `b_i` – the color of the visible board chip for each stack on the board
(`1\ ≤\ b_i\ ≤\ c`).

The third line contains `p` integers `l_i` – the color of the last chip for each player (`1\ ≤\ l_i\ ≤\ c`). The players
are numbered from one (you) to `n` in the order of their turns.

The first line must contain `w` – the number of winning moves.
The second line must contain `w` distinct numbers `m_i` – the numbers of the stacks on which your chip
should be put to win. Stacks are numbered starting from 1 in the order that their visible colors are given
in the input file. You can output their numbers in any order on this line.

Remember, that your move should be winning regardless of the moves of all other players.

Sample Input

6 3 4 2 2 1 2 3 2 2 2 1 1

Sample Output

1 2

Note, that if you put the chip on the 4th stack, other players may place their chips on the 1st and the
3rd stack, which leads to a draw, because the number of visible chips of the ?rst and the second colors
is the same (three chips of each color).