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

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

Условие

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

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

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

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

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

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

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

Ограничения

0 ≤ A < B ≤ 109, 1 ≤ T ≤ 10000

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
T
125T ≤ 10
275T ≤ 100001

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 5 3
1 2 1
2
3 10 2
-1

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

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

Условие

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

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

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

Предлагается также использовать уравнение движения x = x0 + vx 0 ⋅ T + ax ⋅ T22, где x0, vx 0 — положение и скорость в момент времени перед шагом (аналогичные параметры для координаты y), ax — компонента x ускорения, которую можно вычислить из второго закона Ньютона m ⋅ ax = Fx, где Fx — компонента x силы кулоновского взаимодействия (аналогично с компонентой y). Время T — это длительность шага.

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

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

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

Все тесты к данной задаче доступны в одном файле. Этот файл можно скачать ЗДЕСЬ.

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

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

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
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. Виртуальный лабиринт

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 5
.....
.#.#.
.#.#.
.###.
6
#..
...
#..
...
#.#
###
5 2
N
W
W
S
S
2
1 1
#
1
##.
-1

0.183s 0.033s 13