Problem A. Triathlon ≡

Statement

Triathlon is an athletic contest consisting of three consecutive sections that should be completed as fast as possible as a whole. The first section is swimming, the second section is riding bicycle and the third one is running. The speed of each contestant in all three sections is known. The judge can choose the length of each section arbitrarily provided that no section has zero length. As a result sometimes she could choose their lengths in such a way that some particular contestant would win the competition.

Input file format

The first line of the input file contains integer number N, denoting the number of contestants. Then N lines follow, each line contains three integers V_i, U_i and W_i, separated by spaces, denoting the speed of i-th contestant in each section.

Output file format

For every contestant write to the output file one line, that contains word "Yes" if the judge could choose the lengths of the sections in such a way that this particular contestant would win (i.e. she is the only one who would come first), or word "No" if this is impossible.

Constraints

1 ≤ N ≤ 100

1 ≤ V_i, U_i, W_i ≤ 10000

Sample tests

9
10 2 6
10 7 3
5 6 7
3 2 7
6 2 6
3 5 7
8 4 6
10 4 2
1 8 7

Yes
Yes
Yes
No
No
No
Yes
No
Yes

Задача B. Буратино ≡

Условие

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

Папа Карло начинает работу ровно в 9 часов. С 13 часов у него начинается обеденный перерыв. При этом если он незадолго до обеда хочет начать вбивать гвоздик, но понимает, что до перерыва он не закончит эту работу, то он и не начинает ее. Аналогично в 14 часов он вновь приступает к работе, а в 18 уходит домой. Это значит, что в 9:00:00 (аналогично, как и в 14:00:00) он уже может начать забивать гвоздик. Если, например, в 12:59:59 (аналогично, в 17:59:59) он хочет начать вбивать гвоздик, и на это у него уйдет 1 секунда, то он успевает вбить гвоздик до обеда (до окончания работы соответственно), а если 2 — то уже нет.

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

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

Во входном файле записано расписание телевизионных передач с 9:00:00 до 18:00:00 в следующем формате. В первой строке число N — количество телевизионных передач в этот период. В каждой из последующих N строк записано описание одной передачи: сначала время ее начала в формате ЧЧ:ММ:СС (ЧЧ — две цифры, задающие часы, ММ — две цифры, задающие минуты начала, СС — две цифры, задающие секунды начала). А затем через один или несколько пробелов число T_i — время в секундах, которое папа Карло будет тратить на забивание одного гвоздика, если он перед этим увидит по телевизору эту передачу.

Передачи записаны в хронологическом порядке. Первая передача всегда начинается в 09:00:00. Можно считать, что последняя передача заканчивается в 18:00:00.

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

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

Ограничения

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

2
09:00:00 3600
14:00:00 3600

8

4
09:00:00 1800 
12:59:31 10
13:45:23 1800
15:00:00 3600

14

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

Условие

Из правил проведения студенческого командного чемпионата мира по программированию 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
25

1

2
20 
10

1 2

2
10 20

2 1

Задача D. Васины очки ≡

Условие

Вася в казино играет в интересную игру.

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

На автомате, в который он играет, есть три кнопки. Когда он нажимает первую, к его очкам добавляется A очков. Когда нажимает вторую - добавляется B. Когда нажимает третью - добавляется C очков.

Ему разрешается сначала несколько раз (или ни разу) нажать третью кнопку, и затем несколько раз (или ни разу) - первую. Нажимать вторую кнопку Васе запрещено.

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

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

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

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

Во входном файле записаны числа X, A, B, C, Y. Каждое из этих чисел - целое из диапазона [-10⁹, 10⁹].

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

В выходной файл выведите одно число - количество различных выигрышных последовательностей. Если таких последовательностей бесконечно много, выведите -1.

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

1 1 0 -1 10

-1

1 2 4 -2 -20

0

1 1 2  3 10

4