Задача Игра Был ничем не примечательный, холодный зимний вечер, когда Андрей снова пролистывал



Скачать 69.29 Kb.
Pdf просмотр
Дата14.04.2017
Размер69.29 Kb.
Просмотров363
Скачиваний0
ТипЗадача

Заключительный этап Всесибирской открытой олимпиады школьников по информатике
15 марта 201 5 года
1
Для всех задач:
Имя входного файла:
input.txt
Имя выходного файла:
output.txt
Ограничение по памяти:
256 Мб

Ограничение по времени:
1 с. на тест

Максимальная оценка за задачу:
100 баллов

Задача 1. Игра

Был ничем не примечательный, холодный зимний вечер, когда Андрей снова пролистывал список доступных приложений на телефон. Вот он остановился на игре, на которую прежде никогда не натыкался. Описание было многообещающим: «обруливайте препятствия, развивайте реакцию, минимизируйте расстояние».
Андрей тут же установил приложение, и начал играть. Суть игры заключалась в следующем:
Игровой уровень — это карта, которая имеет длину L и высоту H. Есть q препятствий в виде прямоугольников различных размеров. Игрок представляет собой прямоугольник шириной a и высотой b. Расположение препятствий и игрока задается координатами верхней левой клетки прямоугольника на карте. Координата по длине отсчитывается от левой границы карты и координата по ширине — от верхней границы карты. Начальное положение игрока в левом верхней клетке, координаты по длине и ширине равны 1.
Игрок двигается по карте по определенным правилам. Если игрок врезается в препятствие
— уровень считается проигранным и игра заканчивается. Когда самая правая клетка игрока пересекает правую границу карты, то он выигрывает уровень. Каждую единицу времени игрок перемещается на одну клетку вправо, а также, нажимая кнопки «вверх»/«вниз», может сдвинуться на одну клетку вверх или вниз одновременно с движением вперед. За верхние и нижние границы сдвигаться нельзя. Стоит отметить, если игрок нажимает кнопку «вверх»( или
«вниз»), то в следующий момент времени он одновременно переместится и вперёд, и вверх (или вниз). И если при таком перемещении игрок перемещается на свободные клетки, то считается, что игрок не задел препятствие.
Не один раз прошёл Андрей игру, но для получения бонуса требуется пройти все уровни с минимальным количеством нажатий кнопок «вверх»/«вниз». Помогите ему, напишите программу, которая по заданному игровому уровню определяет минимальное количество нажатий кнопок, которое потребуется сделать.
Входные данные

Первая строка входного файла содержит два целых числа L и H
— ширину и высоту
(1 ≤ L ≤ 10000, 1 ≤ H ≤ 100).
На следующей строке заданы два целых числа
a и b
— ширина и высота игрока
(1 ≤ aL,
1 ≤ bH) .
Далее на отдельной строке записано число q — количество препятствий (1 ≤ q ≤ 10 5
).
В следующих q строках идет описание препятствий. В каждой строке содержится описание одного препятствия в виде четырёх целых чисел: x, y, w, h — координата по длине, координата по ширине, ширина и высота прямоугольника, соответственно (1 ≤ x, wL, 1 ≤ y, hH). Все стороны прямоугольника параллельны границам карты.
Некоторые из препятствий могут пересекаться между собой. Гарантируется, что уровень проходим. Препятствия могут выходить за границы карты.
Гарантируется, что изначально игрок не пересекается с препятствиями.
Выходные данные

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

Заключительный этап Всесибирской открытой олимпиады школьников по информатике
15 марта 201 5 года
2
Примеры

input.txt
output.txt
5 3 1 1 2
3 1 2 2 5 3 1 1 3
6 3 2 1 3
3 1 1 1 4 2 1 1 6 3 1 1 3
Пояснение к примерам

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

Заключительный этап Всесибирской открытой олимпиады школьников по информатике
15 марта 201 5 года
3

Задача 2. Криптография

Вася и Петя решили стать специалистами в области криптографии. Для начала они хотят научиться кодировать сообщения в виде целого числа в диапазоне от 1 до 2
n
. Сообщение будет передаваться от Пети Васе. Они договорились действовать следующим образом.
Сначала Вася записывает строку, состоящую из нулей и единиц. Длина строки должна быть кратна 2
n
. Записанную строку

Вася передаёт Пете.
Если Петя хочет закодировать число m, он выписывает символы, стоящие в Васиной строке на позициях m, m+2
n
, m+2·2
n
, m+3·2
n
... и т.д. Позиции в строке нумеруются с единицы. Таким образом, Петя получает новую строку, которая в 2
n
раз короче Васиной. Эту строку он возвращает Васе.
Вася знает, что если придумает подходящую строку, то, получив ответ от Пети, он сможет восстановить закодированное Петей число m.
Напишите программу, которая поможет Васе найти такую строку минимальной длины.
Если подходящих строк минимальной длины существует несколько, то Васю устроит любая из них.
Входные данные

Во входном файле задано натуральное число n (1 ≤ n ≤ 18).
Выходные данные

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

Пример
input.txt
output.txt
2 00110101
Пояснение к примеру

Вася знает, что сообщение Пети — это число от 1 до 4 (2 2
). Вася записал строку "00110101". Теперь Петя ответит Васе некоторой строкой, в зависимости от того, какое число m он собирается закодировать. Например, если m = 1, то Петя возьмёт первый и пятый символы
Васиной строки, и получит из них строку "00", которую передаст Васе в качестве ответа. При других значениях m Петя будет передавать Васе ответ "01", "10" или "11". Так как для разных значений m ответы будут различны, то Вася сможет однозначно расшифровать ответ и узнать m.
Задача 3. Василиса и компьютерная игра

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

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

В первой строке входного файла задано натуральное число N — количество игр
(0 < N 10 6
).
В следующей строке содержится описание результатов игр в виде последовательности букв
W” и “L”. “W” означает победу Василисы в игре, “L” — поражение.
Гарантируется, что
Василиса одержала хотя бы одну победу. Игры в последовательности нумеруются числами от 1 до N, начиная с левого символа.


Заключительный этап Всесибирской открытой олимпиады школьников по информатике
15 марта 201 5 года
4


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

input.txt
output.txt
8
WWWLWWLL
4 1 6

Задача 4. Телефон

Однажды, гуляя в парке, математик Саша встретил прекрасную девушку Алису. Они катались на каруселях, кормили лебедей, в общем, прекрасно проводили время. На прощание
Алиса записала свой номер телефона на бумажке, а Саша пообещал позвонить ей, чтобы договориться о следующей встрече.
Но, как известно, у влюбленных ветер в голове. Вот и Саша, когда пришел домой, бросил свои джинсы в стирку вместе с номером. После стирки записка распалась на N частей. Саша был в отчаянии, но он смог вспомнить, что номер телефона делился на целое число d, и что других цифр, кроме цифр номера, на записке не было.
Напишите программу, которая определяет сколько номеров нужно набрать Саше, чтобы гарантированно услышать голос Алисы. Номер мог содержать ведущие нули.
Входные данные

В первой строке входного файла через пробел заданы два целых числа N и d — количество кусочков, на которые распалась записка с номером, и число, которому был кратен исходный номер (1 ≤ N ≤ 8, 1 ≤ d < 1000).
В следующих N строках содержатся части телефонного номера, по одной в каждой строке.
Известно, что количество цифр во всех частях не превышает 30, и любая часть содержит хотя бы одну цифру. Суммарное количество цифр по всем частям не превышает 30.
Выходные данные

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

Пример
input.txt
output.txt
3 5 172 80 15 4

Заключительный этап Всесибирской открытой олимпиады школьников по информатике
15 марта 201 5 года
5
Задача 5. Тир
После похода в тир Вася решил сделать себе мишень. Васина мишень состоит из 10 вложенных друг в друга квадратов. Длины сторон разных квадратов различны. Каждый квадрат имеет ненулевую площадь. Координаты вершин квадратов – целые числа. Каждый квадрат содержит все остальные квадраты меньшего размера. Квадраты пронумерованы числами от 1 до
10. Номер 10 имеет самый большой по площади квадрат, номер 9 — второй по размеру квадрат, и т.д. У самого маленького квадрата номер 1.
За попадание в квадрат с номером 1, включая его границу, начисляется 10 очков. За попадание в квадрат с номером 2, включая границу, но промах в первый начисляется 9 очков и т.д. За непопадание ни в один из квадратов начисляется 0 очков. Количество очков за серию выстрелов — это сумма очков, начисленных за каждый выстрел.
Вася делает серию из N выстрелов. При этом i-ый выстрел он делает с расстояния L
i и целится в точку с координатами (x
i
, y
i
). При выстреле с расстояния L пуля может сместиться в сторону от целевой точки как по вертикали, так и по горизонтали независимым образом, т.е. расстояние, на которое пуля сместится по оси Ox, никак не повлияет на смещение по Oy, и наоборот. Пуля может сместиться от x
i
на расстояние не более чем на a

L по оси Ox и от y
i
не более чем на b

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

В первой строке входного файла через пробел заданы три целых числа N, a и b — количество выстрелов и коэффициенты смещения (0 < N ≤ 10 5
, 0 < a, b ≤ 10).
В следующих 10 строках идет описание квадратов мишени. Каждая строка содержит описание одного квадрата в виде четырёх целых чисел x
1
, y
1
, x
2
, y
2
координаты левой нижней и правой верхней вершины.
Затем, следующие N строк содержат описания выстрелов. В каждой строке задано описание очередного выстрела в виде трех целых чисел x, y, L — координат точки, в которую Вася целится, и расстояния, с которого выстрел производится (0 ≤ L ≤ 100).
Координаты вершин квадратов и координаты цели выстрелов по модулю не превосходят
1000.
Стороны квадратов параллельны осям координат. Квадраты мишени во входном файле могут идти в произвольном порядке.
Выходные данные

В выходной файл требуется вывести сумму средних количеств очков за серию выстрелов с точностью не менее 10
–5

Пример
input.txt
output.txt
2 1 1
-1 -1 1 1
-2 -2 2 2
-3 -3 3 3
-4 -4 4 4
-5 -5 5 5
-6 -6 6 6
-7 -7 7 7
-8 -8 8 8
-9 -9 9 9
-10 -10 10 10 0 0 10 0 0 5 11.05



Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал