Задача A. Плавное движение ≡

Условие

Объект в компьютерной игре должен переместиться по горизонтали из точки с x-координатой A в точку с x-координатой B (B > A) за время, в точности равное T кадрам анимации.

Пусть за кадр с номером i объект перемещается вправо на целое число пикселей d_i (таким образом, d₁ + d₂ + ⋯ + d_T = B − A). Для обеспечения плавности анимации ускорение объекта не должно превосходить одного пикселя на кадр за кадр. То есть для любого i > 0 должно выполняться |d_i − d_i−1| ≤ 1. Будем считать, что d₀ = 0.

Напишите программу, которая по данным A, B и T находит подходящий набор d_i или определяет, что это сделать невозможно.

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

Входной файл содержит целые числа A B T.

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

Выходной файл должен содержать T целых чисел d_i. Если существует несколько решений, выведите любое из них. Если решения не существует, выведите единственное число −1.

Ограничения

0 ≤ A < B ≤ 10⁹, 1 ≤ T ≤ 10000

Описание подзадач и системы оценивания

Баллы за первую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены. Баллы за вторую подзадачу начисляются за каждый тест в отдельности, но только в случае прохождения всех тестов первой подзадачи.

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

1 5 3

1 2 1

3 10 2

-1

Задача B. Первый проект VR ≡

Условие

Вы — начинающий разработчик игрового движка. Не успели освоиться, как заказчик потребовал поддержку VR, к тому же попросил продемонстрировать его работу уже завтра!

Коллективом проектных менеджеров было решено разработать следующую демонстрацию. На игровом поле будут заданы положения N зарядов, также будут даны значения зарядов в кулонах. Задание заключается в том, чтобы промоделировать перемещение зарядов под действием сил электростатического взаимодействия.

Решено сначала написать двумерный прототип, т.е. каждый заряд имеет две координаты в метрах. Также решено промоделировать заданное число M шагов, длительностью T секунд каждый. Чтобы упростить моделирование, предполагается, что в течение каждого шага, действующие на заряды силы не изменяются. Перед каждым шагом необходимо пересчитать действующие на каждый заряд силы согласно закону Кулона. Согласно этому закону сила взаимодействия каждой пары зарядов по модулю будет равна F_1,2 = k|q₁| ⋅ |q₂|r21,2. Сила будет направлена в сторону взаимодействующего заряда, в случае, если его значение противоположно по знаку, и в обратную сторону — иначе. Для простоты коэффициент k необходимо взять численно равным 1. Массу всех зарядов считать одинаковой, равной 1 кг.

Предлагается также использовать уравнение движения x = x₀ + v_{x 0} ⋅ T + a_x ⋅ T²2, где x₀, v_{x 0} — положение и скорость в момент времени перед шагом (аналогичные параметры для координаты y), a_x — компонента x ускорения, которую можно вычислить из второго закона Ньютона m ⋅ a_x = F_x, где F_x — компонента x силы кулоновского взаимодействия (аналогично с компонентой y). Время T — это длительность шага.

Все заряды могут проходить сквозь друг в друга. Чтобы избежать деления на ноль при вычислении закона Кулона, в знаменателе при вычислении решено брать максимум из 0.1 и r².

Осталось дело за малым — написать код!

Отправка решения и тестирование

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

Первая строка входного файла содержит 2 целых числа N, M и 1 вещественное число T — количество зарядов, количество шагов, и длительность каждого шага моделирования соответственно.

В каждой из N последующих строк заданы 3 вещественных числа x_i, y_i, q_i, разделенных пробелом — координаты и значение i-го заряда соответственно.

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

В выходной файл выведите M раз по N строк — результаты моделирования после каждого шага. В каждой строке по две координаты x_i,j и y_i,j j-го заряда в момент времени после i-го шага. Координаты будут считаться верными, если либо абсолютная, либо относительная погрешность не превосходит 10⁻² (второй знак после запятой).

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

2 10 0.1
0 0 1
1 1 -1

0.00176776 0.00176776
0.99823223 0.99823223
0.00708363 0.00708363
0.99291636 0.99291636
0.01599877 0.01599877
0.98400122 0.98400122
0.02861942 0.02861942
0.97138057 0.97138057
0.04511558 0.04511558
0.95488441 0.95488441
0.06573648 0.06573648
0.93426351 0.93426351
0.09083666 0.09083666
0.90916333 0.90916333
0.12092011 0.12092011
0.87907988 0.87907988
0.15671878 0.15671878
0.84328121 0.84328121
0.19934315 0.19934315
0.80065684 0.80065684

4 10 0.01
0 0 1
1 1 1
0 1 1
1 0 -1

0.00003232 -0.00006768
1.00006768 0.99996768
-0.00003232 1.00003232
0.99993232 0.00006768
0.00012930 -0.00027069
1.00027069 0.99987070
-0.00012928 1.00012928
0.99972928 0.00027072
0.00029100 -0.00060897
1.00060897 0.99970900
-0.00029084 1.00029084
0.99939087 0.00060913
0.00051753 -0.00108237
1.00108237 0.99948247
-0.00051695 1.00051695
0.99891704 0.00108296
0.00080907 -0.00169068
1.00169068 0.99919093
-0.00080750 1.00080750
0.99830775 0.00169225
0.00116585 -0.00243360
1.00243360 0.99883415
-0.00116236 1.00116236
0.99756291 0.00243709
0.00158815 -0.00331078
1.00331078 0.99841185
-0.00158138 1.00158138
0.99668245 0.00331755
0.00207632 -0.00432178
1.00432178 0.99792368
-0.00206437 1.00206437
0.99566626 0.00433374
0.00263078 -0.00546610
1.00546610 0.99736922
-0.00261110 1.00261110
0.99451422 0.00548578
0.00325196 -0.00674316
1.00674316 0.99674804
-0.00322131 1.00322131
0.99322619 0.00677381

Задача C. Виртуальный лабиринт ≡

Условие

Лабиринт в компьютерной игре представлен полем из H строк по W символов каждая, где каждый символ равен либо '.' (ASCII 46), что означает свободную клетку, либо '#' (ASCII 35), что означает стену.

Игроки появляются в случайной свободной клетке лабиринта и могут за один ход перемещаться на любую из соседних по горизонтали или вертикали свободных клеток. Обозначим перемещения игрока буквами N, S, W, E для направлений на север, юг, запад и восток соответственно. Направление взгляда игрока совпадает с направлением последнего сделанного им хода. Перед первым ходом игрок смотрит на север.

Игра построена на основе трёхмерного графического движка с видом от первого лица. Поэтому в каждый момент времени игрок видит только содержимое клетки непосредственно перед ним в направлении его взгляда, а также двух клеток непосредственно слева и справа от него. Один из игроков опубликовал видео своих перемещений по игровому миру. В результате анализа видео было получено количество шагов N и символы L_i F_i R_i для для каждого хода, обозначающие содержимое клеток слева, впереди и справа перед i-м ходом игрока.

Вокруг лабиринта находится неограниченное поле из пустых клеток, но известно, что игрок никогда не покидал пределы лабиринта.

Напишите программу, которая определит начальную позицию и последовательность ходов игрока или выяснит, что это сделать невозможно.

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

Первая строка входного файла содержит целые числа H W. Следующие H строк содержат по W символов . и # каждая — описание лабиринта. Строка номер H + 2 содержит целое число N. Следующие N строк состоят из трёх символов L_i F_i R_i каждая.

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

Первая строка выходного файла должна содержать два целых числа x y — столбец и строку начальной позиции игрока (нумерация начинается с 1). Вторая строка должна состоять из N символов N, S, W, E — последовательность ходов игрока. Если существует несколько решений, выведите любое из них. Если решения не существует, выведите единственное число −1.

Ограничения

1 ≤ W, H ≤ 100, 1 ≤ N ≤ 1000, 1 ≤ x ≤ W, 1 ≤ y ≤ H

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

4 5
.....
.#.#.
.#.#.
.###.
6
#..
...
#..
...
#.#
###

5 2
N
W
W
S
S

1 1
#
1
##.

-1