Problem A. Judging tires

Author:A. Zhuplev
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

According to ISO stadnard Metric tire code, tire dimensions are described by a string of letters and numbers in the following format:

Rules of ACM (Any Car Modification) race specify a fixed tire dimensions for all participating cars. Young racer Vasya has not been able to find this type of tire. However, his car will still be approved for the race by judges only if radius of the wheel (wheel disk radius plus sidewall height) differs by at most K percent from that of the specified tire.

Note: 1 inch = 25.4 millimeters. Number a differs from b by at most c percent when 100 × |a − b| / b ≤ c.

Input file format

First line of input file contains integer K.

Second and third lines contain Metric tire codes of specified tire and Vasya's tire respectively. Tire codes contain only digits, R and slash (ASCII 47) characters.

Output file format

Output file must contain a single string — APPROVED if Vasya's car is approved to the race or DISAPPROVED otherwise.

Constraints

0 ≤ K ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
195/65R15
205/55R15
DISAPPROVED
2
1
195/65R15
185/070R15
APPROVED

Problem B. Aquatic life

Author:A. Klenin
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

Scientists of Nearsea Institute of Underwater Life obtained a picture of the mysterious aquatic life form. They wanted to determine the creature's species.

To do that, picture copies were distributed among N experts. Each expert made Gi guesses, each guess consisting of the name of the species and the score sij reflecting expert's level of confidence in the guess. For each expert, all guesses name different species.

You program must choose the species which received the highest total score from all experts.

In the first sample below "Ceramaster_arcticus" species received the total score of 14.

Input file format

Input file contains integer N on the first line, followed by N line blocks — one for each expert.

Each line block contains integer Gi, on the first line, followed by Gi lines — one for each guess.

Each guess line contains an integer sij followed by a string — guess score and species name. Names consist of Latin letters and underscores (ASCII 95). Names are case-sensitive ("a" and "A" are different names).

Output file format

Output file must contain names of all species with the score equal to the highest total score, one name per line, sorted lexicographically.

Constraints

1 ≤ N ≤ 100, 1 ≤ Gi ≤ 100, 1 ≤ sij ≤ 100

Species names contain from 1 to 50 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
2
5 Ceramaster_patagonicus
5 Ceramaster_arcticus 
3
7 Neoferdina_insolita
1 Neoferdina_glyptodisca
1 Ceramaster_arcticus 
2
8 Ceramaster_arcticus
2 Neoferdina_insolita
Ceramaster_arcticus
2
2
3
5 a
6 b
1 c
2
3 a
7 c
a
c
3
1
4
13 a
7 b
13 B
9 A
B
a

Problem C. Easy money

Author:A. Klenin
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

Young programmer Vasya was not at all interested in car races, but many of his friends were. One day, friends persuaded Vasya to come with them to a sports bar to drink beer and watch some very important race involving N cars — they told Vasya the name of the race, but he immediately forgot it.

At first Vasya was not keen to go, but the perspective of a good beer won him over.

After an hour at the bar, Vasya understood that that the endless images of the cars driving around and around were just as boring with beer as without it. His friends, however, got quite excited and started to place bets on race results. Due to the amount of beer consumed, the bets were wild and some of them did not reflect actual chances at all. In total, M bets were suggested.

Since Vasya was unable to have fun, he decided at least to make some profit. All bets are of the form "I bet A roubles versus B roubles that car p will come ahead of car q". That means betting person agrees to pay A roubles if he was wrong (i.e. q will come ahead of car p), and requires the other side to pay him B roubles if he was right.

By betting on the same cars with different friends, Vasya would in some cases guarantee himself a net win, even if he loses some of the bets. So as not to alienate too many of his friends, Vasya decided to accept only two bets.

Find two bets for Vasya which will guarantee him the largest profit in the worst case.

Input file format

Input file contains integers N M followed by M bet descriptions.

Each bet description contains integers Ai Bi pi qi.

Output file format

Output file must contain a single integer — the maximum amount of guaranteed profit. If there is no way to select two bets to be always profitable, output must contain 0.

Constraints

2 ≤ N, M ≤ 10000;

1 ≤ Ai, Bi ≤ 10000;

1 ≤ pi, qi ≤ N, pi ≠ qi;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2
100 10 1 2
100 10 2 1
90
2
3 3
200 100 1 2
40 50 2 1
100 1 1 3

0

Задача D. Супрематизм

Автор:А. Малова, А. Комаров (Жюри XXI командной олимпиады школьников СПб по информатике)
Входной файл: supreme.in   Ограничение времени:2 сек
Выходной файл: supreme.out   Ограничение памяти:256 Мб

Условие

Недавно на уроках ИЗО Казимиру рассказали о различных направлениях искусства. Больше всего его впечатлил супрематизм, и он решил нарисовать свою первую картину в этом стиле.

Казимир помнил, что в супрематизме картина состоит из простых фигур, поэтому, сначала он нарисовал прямоугольник n × m, составленный из разноцветных квадратов 1 × 1. После критического переосмысления своего творения, Казимир пришел к выводу, что получившаяся картина слишком сложна, и не все смогут понять его задумку. Второго холста у него не было, и он решил исправлять эту картину. На достаточно простой картине, по мнению Казимира, должен присутствовать всего один цвет.

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

Помогите Казимиру определить, cможет ли он с помощью этих операций исправить свою картину и сделать ее достаточно простой.

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

В первой строке заданы два числа n и m (1 ≤ n, m ≤ 300) — размеры картины. Далее, в n~строках задано по m чисел ci,j (1 ≤ ci,j ≤ 1 000 000) — цвета квадратов, из которых составлена картина. Гарантируется, что на картине представлено хотя бы два цвета.

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

Если Казимиру не удастся сделать картину достаточно простой, выведите Poor Kazimir.

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

Разрешается сделать не более 1000 действий.

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

Входной файл (supreme.in) Выходной файл (supreme.out)
1
3 3
1 1 2
2 1 1
2 2 2
5
R 1
R 2
C 1
C 2
C 3
2
3 3
1 1 2
2 1 1
2 2 2
4
C 1
C 3
R 1
R 2
3
2 2
1 2
3 4
Poor Kazimir

0.063s 0.006s 15