Problem A. Hlelo? wrold

Input file:Standard input   Time limit:1 sec
Output file:Standard output   Memory limit:512 Mb

Statement

Young programmer Vasya writes a "hello world" program in a simple programming language. Program consists of a single line and should look like that:

print("Hello,World")

Vasya is very bad at typing. While trying to enter the line above, he pressed letter keys L times, special character keys C times (including quotes, comma and parentheses). Vasya also pressed backspace key B times, erasing a single character every time.

Your program must determine if it is possible in principle that Vasya achieved the exact text above.

Input format

Input file contains integers L, C, B.

Output format

Output file must contain a single line YES or NO.

Constraints

0 ≤ L, C, B ≤ 100

L + C ≥ B

Sample tests

No. Standard input Standard output
1
15 5 0
YES
2
2 7 6
NO

Задача B. Предусмотрительное жюри

Автор:Кировская командная олимпиада 2001 года   Ограничение времени:5 сек
Входной файл:c.in   Ограничение памяти:64 Мб
Выходной файл:c.out  

Условие

Из правил проведения студенческого командного чемпионата мира по программированию ACM:

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

Если же решение проходит все тесты, то данная задача считается решенной, и команде начисляется некоторое количество штрафного времени. Штрафное время — это время в минутах от начала тура до момента посылки правильного решения этой задачи на проверку плюс по 20 штрафных минут за каждую неверную попытку по этой задаче (до тех пор, пока решение не прошло все тесты, никакого штрафного времени за задачу не начисляется).

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

Задача:

Жюри точно уверено, что команда "Super solvers", известная своей непобедимостью, все равно за тур успеет решить все задачи, и, скорее всего, каждую из задач — с первой же попытки (то есть штрафное время за каждую задачу будет равно времени от начала тура до момента ее посылки на проверку). Конечно, жюри может попытаться усложнить задачи, однако оно не хочет этого делать, так как опасается, что в этом случае из остальных команд вообще никто ничего не решит.

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

Среди членов жюри есть тренер этой команды. Он прознал про тактику, которой решила придерживаться команда, а также может примерно оценить время, которое потребуется команде для решения каждой задачи. Жюри прекрасно понимает, что уже никак не может повлиять на число решенных командой задач, но зато, учитывая тактику команды, жюри может влиять на штрафное время, которое получит команда, располагая задачи в разном порядке. В самом деле, если на тур предлагается две задачи, и на решение одной из них команда тратит 10 минут, а на решение второй - 20, то штрафное время команды, если задачи расположить именно в таком порядке, будет равно 40 минутам (первую задачу команда сдает на 10-й минуте тура, вторую - на 30, 10+30=40). Если же задачи расположить в обратном порядке, то штрафное время будет равно 50 (сначала команда потратит 20 минут, потом еще 10, то есть пошлет задачи на 20-й и 30-й минутах, и штрафное время будет равно 20+30=50).

Жюри хочет, чтобы штрафное время команды "Super solvers" было как можно больше (быть может, это даст хоть какой-то шанс другим командам). Помогите членам жюри расположить задачи в таком порядке.

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

Во входном файле записано сначала число N — количество задач на тур. Затем идет N натуральных чисел, каждое из которых не превышает 300. i-ое из этих чисел задает количество минут, которое (по прогнозу тренера) команда "Super solvers" потратит на решение задач номер i.

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

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

Ограничения

1 ≤ N ≤ 20

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

Входной файл (c.in) Выходной файл (c.out)
1
1
25
1
2
2
20 
10
1 2
3
2
10 20
2 1

Задача C. Фонари

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

Условие

На улице длиной в 100 метров установлено N фонарей высотой y1, y2, …, yN метров на расстоянии x1, x2, … xN метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

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

  1. N ≤ 2

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

Во входном файле содержится число N, за которым следует N пар целых чисел x1 y1 x2 y2… xN yN.

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

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

Ограничения

1 ≤ N, yi ≤ 100, 0 ≤ xi ≤ 100.

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

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

Задача D. Три точки на букву

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

Условие

Юный программист Вася решил создать свой язык, состоящий из всего четырех букв, которые выглядят так: '//', '\\', '/\' и '\/'.

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

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

Если при рассмотрении точек слева направо их координаты y образуют возрастающую последовательность, то это буква '//'. Если убывающую — '\\'. Если последовательность точек сначала возрастает, потом убывает, это буква '/\'. Если сначала убывает, потом возрастает — '\/'.

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

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

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

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

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

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

Первая строка входного файла содержит целое число N — количество букв. Последующие N строк содержат по 6 целых чисел — x1, y1, x2, y2, x3, y3 — координаты точек буквы в произвольном порядке.

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

Выходной файл должен содержать N строк — '//', '\\', '/\', либо '\/' — названия соответствующих букв.

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

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

Задача E. Быстрая помощь

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

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности ai минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10000; 1 ≤ ai, L ≤ 1000

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

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

Задача F. Три сына

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:1 сек
Входной файл:division.in   Ограничение памяти:256 Мб
Выходной файл:division.out  

Условие

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

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

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

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

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

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

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

Ограничения

6 ≤ N ≤ 109

Пояснение к примеру

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

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

Подзадача 1 (25 баллов)

N ≤ 50

Подзадача 2 (25 баллов)

N ≤ 2000

Подзадача 3 (25 баллов)

N ≤ 40 000

Подзадача 4 (25 баллов)

N ≤ 109

Получение информации о результатах окончательной проверки

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

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

Входной файл (division.in) Выходной файл (division.out)
1
6
1 2 3

Задача O. Финишные позиции

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

Условие

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

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

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

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

Во входном файле содержится число N — количество элементов списка.

Далее следуют N чисел, задающие список.

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

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

Ограничения

1 ≤ N ≤ 106

Номера машин являются целыми неотрицательными числами, не превосходящими 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 1 10
5 1 10
2
8
4 7 8 7 4 8 7 4
7 4 8
3
16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222
17 39 88 222222222

1.099s 0.056s 29