Задача A1. Мишень

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

Условие

Вы реализуете игру "дартс" в виртуальной реальности. Игра устроена следующим образом. Дана мишень в форме круга радиуса R, расположенная в плоскости XY с центром в координатах (0, 0), разбитая на n равных секторов. Сектора пронумерованы от 1 до n по часовой стрелке. В момент броска мишень находится в таком положении, что сегмент с номером 1 расположен в верхней полуплоскости справа от оси Y. Мишень закручивается вокруг оси Z по часовой стрелке и приобретает постоянную угловую скорость w градусов в секунду.

Игрок, стоя лицом к мишени на расстоянии z, бросает дротик из координаты (x, y) в плоскости XY перпендикулярно мишени в её сторону. Дротик летит прямолинейно с постоянной скоростью v, не изменяя высоту полёта.

Требуется написать программу, которая определяет номер сектора, в который попадёт игрок.

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

Входные данные содержат целые числа R, w, x, y, z, v, n. Гарантируется, что участник не попал в границу между секторами.

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

Выходные данные должны содержать единственное целое число — номер сектора, в который попал участник, или 0, если участник не попал в мишень.

Ограничения

1 ≤ r, w, v, z ≤ 100

 − 100 ≤ x, y ≤ 100

2 ≤ n ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 20 10 0 100 100 100
20
2
100 1 50 0 1 1 2
1

Задача A2. Распознавание метки

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

Условие

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

Алгоритм предварительной обработки неидеален, и мог совершить от 0 до N ошибок — выдать '#' вместо '.' или наоборот.

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

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

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

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

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

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

Ограничения

1 ≤ W, H ≤ 100, 0 ≤ N ≤ W × H

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

Решения работающие для W, H ≤ 20 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 1
.#.
##.
...
3
2
2 2 0
#.
.#
0

Задача A3. Полоса препятствий

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

Условие

Одно из заданий на соревнованиях по подводной робототехнике — полоса препятствий. Полоса состоит из n подряд идущих стен, высота i-й стены hi.

Цель робота — преодолеть все стены, достать флаг, который находится в конце полосы за всеми стенами, и вернуться обратно. Стену можно преодолеть двумя способами: подняться, проплыть над ней и опуститься обратно или сделать подкоп. Если стена была преодолена с помощью подкопа, то в при проходе в обратную сторону можно воспользоваться уже готовым подкопом. Всего разрешается сделать не более m подкопов.

Робот имеет ограниченный заряд батареи. Изначально он способен подняться над стеной высотой k или меньше, далее после каждого подъёма максимальная высота стены, которую может преодолеть робот, снижается на 1.

Робот поддерживает две команды: D — идти через подкоп (если подкопа ещё нет, то робот выкапывает его), U — проплыть над препятствием.

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

Первая строка входного файла содержит целые числа n m k. Следующая строка содержат n целых чисел hi - высоты стен.

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

Выходной файл должен содержать строку NO, если задание выполнить невозможно. В противном случае — две строки: строку YES и строку из 2 n символов U и D — последовательность команд робота, которая позволит ему преодолеть полосу препятствий и вернуться обратно. Первые n символов содержат описание прохождение от стены с номером 1 до стены с номером n, следующие n символов содержат описание прохождения от стены с номером n до стены с номером 1.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 109

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1401 ≤ n, m ≤ 102, 1 ≤ k, hi ≤ 109полная
2601 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 1091полная

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 5 10
10 1 4 2 4 3 4 4 8 9
YES
DUDUDUUUDDDDUUUDUDUD
2
5 1 1
5 5 5 5 5
NO
3
10 10 10000
13123 141323 213323 3213 213213 321 323213 1323 213 1232113
YES
DDDDDDDDDDDDDDDDDDDD

Задача B1. Программирование робота

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

Условие

Программа для робота X представляет из себя последовательность из 0 и 1. Известно, что если в коде содержится K подряд стоящих 0 или 1, то робот сбрасывается к заводским настройкам.

Вася написал программу для робота. В ходе написания программы часто допускаются ошибки, поэтому программа Васи может содержать K или более подряд идущих 0 или 1. Вася не хочет сброса настроек на роботе, но в тоже время он хочет как можно быстрее запустить свою программу. Для этого он хочет внести минимальное количество изменений в код программы, так чтобы программа не вызывала сброса настроек. Изменения бывают только двух видов: замена символа 1 на 0 и замена символа 0 на 1.

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

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

Первая строка входных данных содержит два целых числа n и k. Вторая строка входных данных содержит строку длины n, состоящую из 0 и 1.

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

Выходные данные должны содержать одну строку длины n — откорректированную программу.

Если решений несколько, выведите любое из них.

Ограничения

3 ≤ n, k ≤ 3 ⋅ 105

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

Решения, работающие для n ≤ 3, оцениваются из 20 баллов. Решения для n ≤ 10 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

Стандартный вход Стандартный выход
1
3 3
111
110
2
10 3
1110001110
1100101100
3
3 3
101
101

Задача B2. Усовершенствование космического корабля

Автор:И. Блинов, М. Кузин   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Вася пишет игру — 2D космический симулятор. Космический корабль представляет из себя выпуклый многоугольник, состоящий из n вершин. По задумке Васи улучшение корабля должно происходит следующим образом: корабль заменяется на другой корабль — выпуклый многоугольник большего размера, стороны которого содержат все вершины прошлого выпуклого многоугольника, и при этом имеет минимальное возможное количество вершин.

Вася понял, что ему не хватает знаний для реализации данной механики, поэтому он хочет для начала определить, сколько вершин будет содержать космический корабль после улучшения. С этой задачей он тоже не справился, поэтому делегировал её вам.

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

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

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

Выходные данные должны содержать одно целое число — количество вершин в новом многоугольнике.

Ограничения

 − 10000 ≤ xi, yi ≤ 10000

3 ≤ N ≤ 104

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

Баллы выставляются за каждый успешно пройденный тест.

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

Стандартный вход Стандартный выход
1
6
0.5 0.5
3 0
5 2
3 3
1 3
0 2
3
2
4
0 0
0 1
1 1
1 0
3

Задача B3. Слон Пахом и разработка RPG

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

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

  1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
  2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
  3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

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

Игрок появляется в левом верхнем углу лабиринта и должен пройти в правый нижний угол.

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

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

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

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

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

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

Если лабиринт проходимый, то следующая строка должна содержать целое число k — минимальное количество поворотов, необходимое для прохождения лабиринта.

Ограничения

1 ≤ n, m ≤ 103

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

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

Стандартный вход Стандартный выход
1
5 5
+++++
+++++
+++++
+++++
+++++
YES
0
2
1 8
+-------
YES
0
3
1 8
+------|
NO
4
5 6
|-----
|-###-
#|---#
####|#
+++#|-
YES
5
5
1 1
#
NO

Задача C1. Перепад глубины

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

Условие

Автономный необитаемый подводный аппарат проплыл по заданной траектории, записав последовательность целых чисел ai — глубину своего погружения в метрах на i-й секунде.

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

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

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

Входные данные содержат целые числа n и d — количество измерений и максимальный перепад глубины. Далее следует n целых чисел ai — измерения глубины.

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

Выходные данные должны содержать единственное целое число — наименьшее количество удаляемых элементов.

Ограничения

1 ≤ n ≤ 20 000, 0 ≤ d ≤ 1000, 0 ≤ ai ≤ 109

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

Стандартный вход Стандартный выход
1
3 4
10 15 14
1

Задача C2. Отладка шарика

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

Условие

Юный программист Вася решил разработать собственную платформу виртуальной реальности. Для начала он реализовал вывод пустой чёрной сцены с единственным красным шаром. Однако в алгоритме вывода шара Вася допустил ошибки, из-за которых шар не всегда выводился правильно.

Для отладки Вася сделал скриншоты своего приложения (шар на них должен превратиться в круг). Скриншот представлен прямоугольным массивом символов, в котором символ "#" представляет красный пиксель, а символ "." — чёрный пиксель.

Если шар нарисован правильно, то красными будут только те пиксели, координаты которых (x; y) удовлетворяют условию (x − x0)2 + (y − y0)2 ≤ r2, где x0, y0, r — неизвестные целые числа.

Требуется написать программу, которая по изображению выяснит, правильно ли на нём нарисован шар (спроецированный в круг), и если да, то определит значения x0, y0, r.

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

Первая строка входных данных содержит целые числа X Y — ширину и высоту прямоугольника. Следующие Y строк содержат по X символов "#" и "." каждая — описание изображения.

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

Выходные данные должны содержать целые числа 1 x0 y0 r, если изображение является правильным, и число 0 в противном случае. Координаты отсчитываются от верхнего левого угла.

Ограничения

3 ≤ X, Y ≤ 2000, r ≥ 1

1 ≤ x0 − r < x0 + r ≤ X, 1 ≤ y0 − r < y0 + r ≤ Y

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

Стандартный вход Стандартный выход
1
3 3
.#.
###
.#.
1 2 2 1

Задача C3. Морской бой

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

Условие

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

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

Первая строка входных данных содержит 3 целых числа xc, yc, rc — координаты и радиус мины. Вторая строка содержит одно целое число N — количество вершин в многоугольнике, описывающем корабль. Следующие N строк содержат N пар чисел (xi, yi) (по одной паре в строке) — координаты вершин выпуклого многоугольника, описывающего корабль, в порядке обхода по часовой стрелке.

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

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

Ограничения

 − 1000 ≤ xc, yc, rc, xi, yi ≤ 1000

3 ≤ N ≤ 103

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

Решения, работающие для  − 10 ≤ xc, yc, rc, xi, yi ≤ 10, оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 1
4
0 0
0 1
1 1
1 0
0.785398163
2
0 0 1
3
0 0
0 1
1 0
0.5
3
0 0 4
4
0 0
0 2
4 4
2 0
7.07035

0.784s 0.015s 31