Это перевод на русский язык условия двухнедельного соревнования TopCoder Maraton, задачи SquareRemover.

Соревнование длится с 9 по 23 апреля 2014 года, в нем можно поучаствовать в рамках марафон-матча 83 (или в рамках TopCoder Open 2014, если вам есть 18 лет). Когда будете регистрироваться на TopCoder, в качестве того, кто вас привлек, можете указать М. Э.: никнейм darnley.

Задача SquareRemover

"Square Remover" - это игра для одного игрока, состоящая из:

• Доски NxN, в которой каждая клетка 1x1 покрашена в один из colors цветов.
• Ленты, состоящей из клеток 1x1, также покрашенных в один из colors цветов. Лента бесконечно продолжается вправо.

Во время игры игрок делает ровно 10000 ходов. Каждый ход состоит в том, что игрок выбирает две соседние (по стороне) клетки и меняет их местами.

В каждый момент игры, если существует одноцветный квадрат 2x2, то счет игрока увеличивается на 1, а клетки этого квадрата перекраживаются в цвета очередных четырех клеток бесконечной ленты.

Ваша задача - максимизировать счет в конце игры.

Вот псевдокод происходящего процесса:

Обработка_одноцветных_квадратов
Для хода номер 0, 1, ..., 9999:
    Игрок делает ход
    Обработка_одноцветных_квадратов

Процедура Обработка_одноцветных_квадратов:
    Пока есть хотя бы один одноцветный квадрат 2x2:
	Пусть S - самый верхний одноцветный квадрат.
	Если самых верхних несколько, то пусть S - самый левый из них.
	Счет игрока увеличивается на 1.
	Покрасить верхнюю левую клетку квадрата S в цвет очередной клетки с бесконечной ленты.
	Покрасить верхнюю правую клетку квадрата S в цвет очередной клетки с бесконечной ленты.
	Покрасить нижнюю левую клетку квадрата S в цвет очередной клетки с бесконечной ленты.
	Покрасить нижнюю правую клетку квадрата S в цвет очередной клетки с бесконечной ленты.

 

Реализация

Вам надо реализовать метод playIt, принимающий параметры int colors, String[] board и int startSeed.

colors это количество цветов в игре. Цвета нумеруются от 0 до colors-1.

board описывает изначальную раскраску доски. Это массив, содержащий N элементов-строчек, каждая из которых имеет длину N символов. j-й символ в i-м элементе - это цифра, задающая цвет клетки в строке номер i, в столбце номер j. Строки нумеруются от 0 до N-1 сверху вниз, столбцы - от 0 до N-1 слева направо.

startSeed порождает бесконечную ленту, а именно рассматривается бесконечная последовательность чисел A[i]:

A[0] = startSeed
A[i] = (A[i-1] * 48271) % 2147483647

Цвет i-й (нумерация с нуля) клетка на бесконечной ленте - это A[i] % colors.

Здесь X % Y - это остаток от деления. Не забудьте использовать 64-битный тип данных при построении последовательности A/

Метод playIt должен возвращать int[], содержащий 30,000 элементов. Ваш i-й ход описывается тремя элементами в этом массиве:

• Элементы 3*i и 3*i+1 задают строку и столбец одной из клеток, участвующих в обмене.
• Элемент 3*i+2 задает направление ко второй клетке, участвующей в обмене: 0 -- вверх, 1 -- вправо, 2 -- вниз, 3 -- влево.

 

Генерация тестов

Каждый тест генерируется так:

• colors - произвольное от 4 до 6.
• N - произвольное от 8 до 16.
• Цвет каждой клетки - произвольный от 0 до colors-1.
• startSeed - произвольное от 1 до 2147483646.

 

Визуализатор и шаблон

Оригинальный визуализатор/тестер доступен здесь.

 

Проверка на сервере

For each test case we will calculate your raw and normalized scores. If you were not able to produce a valid return value (due to time limit, memory limit, crash, numbers in your return value do not describe 10,000 valid moves, etc.), then your raw score is -1 and the normalized score is 0. Otherwise, the raw score will be your score once the game is finished. The normalized score for each test is 1,000,000.0 * YOUR / BEST, where BEST is the highest score currently obtained on this test case (considering only the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases.

You can see your raw scores on each example test case when you are making an example submit. You can also see total scores of all competitors on provisional test set in the match standings. No other information about scores is available during the match.

The time limit is 30 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.

There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.

The compilation time limit is 60 seconds. You can find information about compilers that we use and compilation options here.

There are 10 example test cases and 100 full submission (provisional) test cases.

 

официальная информация • контакты • © 2003–2024 • ФТШ • Виктор Кропп