Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Полный перебор

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

19/07/2013 | Лето 2013-13 (F) |

*Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

These days, the TV studio has started shooting another new season of Jamie Oliver's cooking show.
This season, Jamie plans to introduce the delights of Croatian cuisine to the world. In the first episode,
the master chef has baked a walnut roll `L` meters long, the longest ever baked in this part of the world.
After hours of sweating and toiling in the kitchen, he has decided to reward each one of his `N` faithful
spectators in the studio.

He has chopped the walnut roll into one meter long chops and marked them with numbers from 1 do
`L`, from left to right. Each spectator has received aunique number ID (a positive integer from 1 to `N`),
as well as a paper with two integers, `P` and `K`. Each spectator was then allowed to take all chops from
the `P`-th to the `K`-th, inclusive. Spectators were allowed to take their share in order of their ID numbers
(spectator 1 first, followed by spectator 2, etc.). This order resulted in some spectators receiving fewer
chops than they initially thought they would get. The following image corresponds to the first example
test case:

Write a program to determine which spectator expected to get the most walnut roll chops, and which
spectator actually got the most.

The first line of input contains the positive integer `L` (`1\ ≤\ L\ ≤\ 1000`), the length of the walnut roll.

The second line of input contains the positive integer `N` (`1\ ≤\ N\ ≤\ 1000`), the number of spectators.

Each of the following Nlines contains two positive integers `P_i` and `K_i` (`1\ ≤\ P_i\ ≤\ K_i\ ≤\ L`, `i\ =\ 1…N`),
the values `P` and `K` as described in the problem statement for spectator number `i`.

The first line of output must contain the ID numberof the spectator who was expecting to receive the
most walnut roll chops.

The second line of output must contain the ID number of the spectator who actually received the most
walnut roll chops in the end.

In both cases, if there is more than one spectator satisfying the condition, output the one with the
smallest ID.

Sample Input #1

10 3 2 4 7 8 6 9

Sample Output #1

3 1

Sample Input #2

10 3 1 3 5 7 8 9

Sample Output #2

1 1

Sample Input #3

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

Sample Output #3

4 5