Задача A. Ребристый параллелепипед

Автор:А. Баранов, А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:32 Мб
Максимальный балл:100  

Условие

Прямоугольный параллелепипед состоит из одинаковых по размеру кубических ячеек. Поверхность каждой ячейки может быть разбита на составляющие ее двумерные грани и ребра, эти грани разделяющие. Совпадающие между собой ребра (в которых две и более ячейки соприкасаются друг с другом) полагаются тождественными и рассматриваются как одно общее ребро.

Например, блок размером 2 × 2 × 2 состоит из 8 ячеек и содержит в себе 54 ребра.

Требуется по данным числам m и n определить, существует ли прямоугольный параллелепипед, состоящий из m кубических ячеек и при этом имеющий ровно n ребер.

Формат входного файла

Входной файл содержит два натуральных числа m n.

Формат выходного файла

Выходной файл должен содержать единственное целое число:

1 — если заданный параллелепипед существует;

0 — в противном случае.

Ограничения

0 < m < 232, 0 < n < 264

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8 54
1
2
6 43
0

Задача B. Хвостовые нули

Автор:А. Баранов, А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:32 Мб
Максимальный балл:100  

Условие

Пусть P(A, B) — величина, равная произведению всех натуральных чисел от A до B включительно.

Для заданных значений A, B и q требуется определить количество нулевых разрядов, которыми оканчивается запись числа P(A, B) в системе счисления по основанию q.

Формат входного файла

Входной файл содержит три натуральных числа: A B q.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество нулевых разрядов.

Ограничения

0 < A ≤ B < 264, 2 ≤ q < 232

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 100 10
24
2
9 75 120
17

Задача C. Представление дробей

Автор:А. Баранов
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:32 Мб
Максимальный балл:100  

Условие

Пусть имеется некоторая простая дробь, заданная своим числителем A и знаменателем B. Требуется преобразовать указанную дробь, представив ее в одном из следующих форматов:

Если дробная часть равна нулю, результат записывается как целое число. В противном случае полученную дробь следует привести к несократимому виду. При этом <числитель> должен быть меньше, чем <знаменатель>.

В свою очередь, если такая дробь без потери точности может быть записана в формате с десятичной точкой, ее необходимо привести к указанному виду.

Формат входного файла

Входной файл содержит два натуральных числа: A B.

Формат выходного файла

Выходной файл должен содержать дробь A / B, отформатированную в соответствии с условием задачи.

Ограничения

0 < A, B < 264

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1736744720710
5067073484375
11977549798 / 34945334375
2
5729534680
35148600
163 ( 7822 / 878715 )
3
10098403664
400000
25246.00916
4
1675223508
13509867
124

Задача D. 2048

Автор:М. Спорышев
Ввод / вывод: интерактивный   Ограничение времени:5 сек
  Ограничение памяти:256 Мб
Максимальный балл:  

Условие

Данная задача является интерактивной.

Задача состоит в прохождении игры 2048 с наилучшим результатом.

2048 играется на поле N × M клеток. Клетки, в которых записаны числа, сдвигаются по нажатию пользователем клавиш курсора.

После каждого хода в случайном пустом поле появляется число 2, либо 4. Клетки сдвигаются в заданном пользователем направлении, пока их не остановит либо другая непустая клетка, либо граница поля.

Если две клетки с одинаковыми числами сталкиваются друг с другом во время сдвига, они объединяются в одну клетку с числом равным их сумме.

Клетка не может быть объединена с другими более одного раза во время сдвига. Клетки сдвигаются и объединяются последовательно от первого к последнему в направлении движения.

Система оценивания

На каждом тесте участник получает количество баллов, равное степени двойки максимального из чисел на доске на момент конца игры.

Протокол взаимодействия

На первом шаге ваша программа должна считать два целых числа N, M — размеры поля.

Далее, на каждом шаге взаимодействия ваша программа должна:

  1. Считать целое число a0,0 из входного потока.
  2. Если a0,0 равно 1, игра закончена, ваша программа должна завершиться.
  3. Иначе, считать N ⋅ M − 1 чисел ai,j — числовые значения клеток, выведенные построчно.

    Соответствующая клетка пуста, если ai,j равно 0.

    a0,0 — числовое значение в первой клетке или 0, если клетка пуста.

  4. Выведите символ команды сдвига ('l', 'r', 'u' или 'd' для сдвига влево, вправо, вверх или вниз соответственно) с последующим символом конца строки.

    Не забудьте очистить буфер. (flush)

Формат входных данных

Первая строка входного потока состоит из двух чисел N и M  — размеры поля.

Далее на каждом шаге следует N строк по M чисел, задающих каждую клетку. 0, если клетка пустая.

Входной поток содержит единственное число 1, если игра окончена.

Формат выходных данных

В выходной поток на каждой итерации необходимо вывести единственный символ, характеризующий направление сдвига и символ конца строки.

Символ 'l'  — движение плиток влево, 'r'  — вправо, 'u'  — вверх, 'd'  — вниз.

Ограничения

Количество шагов не превышает 104

2 ≤ N, M ≤ 10


Problem E. Gomoku

Author:Petr Mitrichev, Pavel Mavrin
Input / output: interactive   Time limit:3 sec
  Memory limit:256 Mb
Maximum points:  

Statement

This is an interactive problem.

Gomoku is a two-player game on a two-dimensional grid. Each cell of the grid can be either empty, contain the first player’s mark (black), or contain the second player’s mark (white), but not both. Initially the entire grid is empty. Two players make alternating moves, starting with the first player. At each move, a player can put her mark into exactly one empty cell. The first player to have her five adjacent marks in a single row wins. The winning row can be either vertical, horizontal or diagonal.

Position where the second player (white marks) had won.

The players use a 19 × 19 grid in this problem. If the entire grid gets filled with marks but no player has won, the game is declared a draw.

The first player uses the following strategy: as the first move, she puts her mark into the center cell of the grid. At every other move, she picks such a move that maximizes the score of the resulting position.

In order to find the score of a position, the first player considers all possible places where the winning combination might eventually form — in other words, all horizonal, vertical and diagonal rows of five consecutive cells on the board (of course, they may overlap each other). If such a row contains both the first player’s marks and the second player’s marks, it is disregarded. If such a row contains no marks, it is disregarded as well. For each row with exactly k (1 ≤ k ≤ 5) marks of the first player and no marks of the second player, add 502 k1 to the score of the position. For each row with exactly k marks of the second player and no marks of the first player, subtract 502 k from the score of the position. Finally, add a random integer number between 0 and 5021 to the score. This random number is chosen uniformly.

In case when several moves of the first player have equal scores (such ties are quite rare because of the random addition mentioned above), the first player picks the one with the smallest x-coordinate, and in case of equal x-coordinates, the one with the smallest y-coordinate.

Your task is to write a program that plays the second player and beats this strategy.

Your program will play 100 games against the strategy described above, with different seeds of random generator. Your program must win all these games.

Interaction protocol

On each step, your program must:

  1. Read numbers x and y from the input.
  2. If both these numbers are equal to  −1 then the game is over and your program must exit.
  3. Otherwise these numbers are the coordinates of the first player’s move (1 ≤ x, y ≤ 19).
  4. Print the coordinates of the move of the second player, followed by line end. Don’t forget to flush the output buffer.

Note

There are many variations of Gomoku rules in the world. Please only consider the rules described in this problem statement.

In the example below the first player does not use the strategy from the problem statement. The example is given only to illustrate the interaction format.

Final position from the example.

Sample tests

No. Standard input Standard output
1
10 10
10 11
10 12
10 13
9 10
9 11
9 9
11 13
-1 -1
11 10
11 11
10 9
10 14
8 9
11 9
11 12
11 8

0.063s 0.005s 26