Задача A. Марфа Геннадьевна в кустах

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

Условие

Марфа Геннадьевна считает, что её соседка по даче, Элеонора Агафьевна, слишком любопытна и постоянно подглядывает за Марфой Геннадьевной из окна. Граница участков Марфы Геннадьевны и Элеоноры Агафьевны представляет собой отрезок длиной L см.

Марфа Геннадьевна решила загородить соседке обзор, засадив границу кустами. У Марфы Геннадьевны имеются семена N видов кустов. Известно, что кусты i-го вида вырастают до ширины в ai см. При этом для нормального развития кустам i-го вида необходимо, чтобы расстояние между краями соседних кустов, а также от края куста до края границы участков было не менее bi см.

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

Рекомендуется рассмотреть следующие частичные решения

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

Входной файл содержит целые числа N L, за которыми следует N пар целых чисел ai bi — ширина куста и минимальное расстояние для i-го вида.

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

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

Ограничения

1 ≤ N ≤ 103

2 ≤ L ≤ 104

1 ≤ ai, bi ≤ 104.

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

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

Задача B. Открытый подсчёт

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

Условие

Юный робототехник Вася построил робота, который способен перемещаться по неограниченному клетчатому полю согласно заложенной в него программе. Робот занимает ровно одну клетку поля. Программа для робота состоит из последовательности команд, разделённых запятой. Каждая команда состоит из латинской буквы и натурального числа. Буква задаёт направление движения (U — на север, D — на юг, L — на запад, R — на восток), а число — количество клеток, на которое робот должен сдвинуться.

Требуется по данной программе определить количество различных клеток (считая начальную), которые посетит робот во время её выполнения. Например, при выполнении программы D3,U4 робот сдвинется на юг на 3 клетки, затем на север на 4. В сумме робот посетит 5 различных клеток (3 из них — по два раза каждую).

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

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

Первая строка входного файла содержит целое число N — количество программ. Последующие N строк содержат по одной программе каждая.

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
D100,L10
R1,L1,R1,L2
111
3

Задача C. Посекундная тарификация

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

Условие

Телефонная компания ввела новый тарифный план "Посекундный". Согласно этому плану, каждый месяц абоненту предоставляется F бесплатных минут. При этом длительности звонков, использующих только бесплатные минуты, округляются вверх до целой минуты. Например, звонок продолжительностью 3 минуты 15 секунд использует 4 бесплатных минуты.

Когда бесплатные минуты исчерпаны (даже если это произошло в середине звонка), включается посекундная тарификация — 1 рубль в секунду.

История звонков абонента представляет собой список из N пар чисел m s, где m — число минут, s — число секунд. Напишите программу, которая по истории звонков абонента за месяц определяет, сколько рублей ему придётся заплатить.

В первом примере первый и второй звонок тратят по 1 бесплатной минуте, третий звонок тратит 4 бесплатных минуты. На последний звонок остаётся 4 бесплатных минуты. После их исчерпания абонент оплачивает 12 секунд.

Рекомендуется рассмотреть частичные решения

  1. F = 0;
  2. N ≤ 1.

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

Входного файла содержит целые числа N F, за которыми следует N пар целых чисел mi si.

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

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

Ограничения

0 ≤ N, F ≤ 1000, 0 ≤ si ≤ 59, 0 ≤ mi ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 10
1 0
0 5
3 40
4 12
12
2
2 5
6 40
70 11
4311

Задача D. Топография

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

Условие

Юный топограф Вася тренируется в рисовании карт местности. Вася отметил на карте вокруг своей школы четыре точки A, B, C, D, образующие выпуклый четырёхугольник, и тщательно измерил расстояния AC, AD, BC и BD. Измерить расстояние CD ему помешало здание школы.

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

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

Входной файл содержит целые числа AC AD BC BD.

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

Выходной файл должен содержать два целых числа — минимальное и максимальное возможные расстояния CD. Если подходящих целочисленных значений расстояния CD не существует, выведите единственное число  − 1.

Ограничения

1 ≤ AC, AD, BC, BD ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 5 6 3
4 7
2
3 2 50 60
-1

Задача E. Гаджет в кредит

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

Условие

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

В магазине Васе объяснили правила предоставления кредита.

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

Рекомендуется рассмотреть частичные решения

  1. P = 0
  2. C, P ≤ 103

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

Входной файла содержит целые числа N P C.

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

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

Ограничения

1 ≤ C ≤ 109; 0 ≤ P ≤ 109; 1 ≤ N ≤ 104

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

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

Задача F. БуКвест

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

Условие

Юный любитель RPG Вася начал играть в новую компьютерную игру БуКвест. Игровой мир представляет собой прямоугольное поле размером W клеток в ширину и H в высоту. Каждая клетка либо пуста, либо занята стенкой, либо содержит главное сокровище, либо содержит монстра уровня k.

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

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

В первом примере Васе необходимо победить монстра A за одну минуту, затем монстра B за 2 минуты. Во втором примере Вася мог бы победить сначала A, потом B, потом C, затратив 1 + 2 + 3 = 6 минут, но быстрее победить монстра D за 4 минуты, и с полученным за него оружием без дополнительных затрат времени пройти монстров A, B и C.

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

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

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

Первая строка входного файла содержит целое число N — количество тестов в данном файле

Далее N идёт блоков с описанием тестов:

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

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

Ограничения

1 ≤ W, H ≤ 50

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
6 5
.####.
...AB.
..###.
...D#*
..###.

6 5
.####.
..ABC.
..###.
...D#*
..###.

3
4

Задача G. Восстановление сетки

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

Условие

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

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

Назовём упорядоченной такую первоначальную последовательность участников, что в каждом матче сетки победителем оказывается первый участник. Например, первоначальная последовательность в приведённой справа сетке не соответствует этому условию — чтобы это исправить, нужно расположить участников в порядке: Life, MarineKing, TaeJa, Leenock, Mvp, Symbol, Rain, Hero.

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

Рекомендуется рассмотреть частичные решения

N ≤ 10;

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

Входной файла содержит целое число N, за которым следуют 2N − 1 пар чисел Wi Li, означающих, что участник с номером Wi победил участника с номером Li. Участники пронумерованы от 1 до 2N.

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

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

Ограничения

1 ≤ N ≤ 20

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2  3 1  7 3
7 6  6 5  7 8  3 4
7 8 6 5 3 4 1 2 

Задача H. Автостоянка на улице Кантора

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

Условие

Автостоянка, находящаяся поблизости от улицы имени Г. Кантора, ограничена с севера и запада домами, а с востока и юга открыта в большое поле.

Чтобы упорядочить размещение автомобилей, владелец стоянки решил пронумеровать места на ней и выделить каждому клиенту номер и соответствующее место. Нумерацию решено производить так: месту в углу стоянки присвоен номер ноль, далее нумерация идёт по диагоналям в направлении с северо-востока на юго-запад.

013610
24711
5812
913
14

Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).

Требуется написать программу, которая для каждого из N данных номеров мест определит их координаты.

Рекомендуется рассмотреть частичные решения

N = 1

C ≤ 106

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

Входной файла содержит число N, за которым следуют N целых чисел Ci — номера мест.

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

Выходной файл должен содержать N пар чисел xi yi — координаты мест, соответствующие номерам во входном файле.

Ограничения

1 ≤ N ≤ 105

0 ≤ Ci ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
1 0
2
2
20101204
226
6106 234
4 16

Задача I. Современная библиотека

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

Условие

Группа, состоящая P из юных программистов, поступила на первый курс университета. Занятия на первом курсе будут продолжаться в течение D дней. Помочь студентам в приобретении знаний может новая библиотека университета, в которой имеется B различных книг, посвящённых программированию. Из-за проблем с финансированием каждая книга имеется в единственном экземпляре.

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

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

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

Если несколько студентов приходят в библиотеку в один день, они обслуживаются в порядке списка, составленного при поступлении в университет.

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

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

Рекомендуется рассмотреть частичные решения

P = 2

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

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

Каждое описание содержит D пар целых чисел Ri, Ti, которые означают что в i-ый день студент хочет сдать книгу с номером Ri и получить книгу с номером Ti. Если студент не собирается брать или сдавать книгу в этот день, соответствующее число равно нулю.

Планы перечислены в порядке, соответствующем порядку обслуживания студентов.

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

Выходной файл должен содержать P пар целых чисел Qi Mi, где Qi — количество книг, которые прочитает i-й студент, Mi равно единице, если i-ый студент будет отчислен, и нулю в противном случае.

Ограничения

1 ≤ P, D ≤ 200

1 ≤ B ≤ 105

0 ≤ Ri, Ti ≤ B

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

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

1.161s 0.019s 37