<ПРЕД Задача:
СЛЕД>
Задачу решили 42 пользователя: vi002, dan, Mishunin_Alexander, vanger, JohnJones_001, rvashegin, ilyich, Rizvanov, tourist, sridhar87, pmnox, WsemirZ, mage, Glukenstein, wojtekt, zloy_mipt, Chmeli_BSU, Ravent, Philip_PV, lutyj, mazahaka, UdH-WiNGeR, defrager, RAVEman, Kuznetsov_S, topspin, piter, li0n, fetetriste, lm, EAA2008, Dest, ripatti, DAV, regmar, s01A15, tttttt, LiuChenheng, mmagnet, NIGHTFIT, mathematic, Robert_Gerbicz.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Time Management

Time limit = 2 секунд(ы)

Вы стали IT специалистом высокого класса и уже неплохо зарабатываете. Вам поступают предложения от серьезных фирм, есть возможность поучаствовать в ряде больших проектов. Да и у вас есть с десяток интересных идей. Вы планируете заняться йогой, посетить Австралию, Гоа, Кубу, Исландию и Алжир, покататься на яхте в Средиземном море. Также необходимо сдать экзамен на водительские права, изучить японский язык, закончить институт. Далее семья и дети и т.д. и т.п.

Уже сейчас вы прекрасно понимаете, что необходим реальный поминутный Time Management. Очень здорово, что это понимание пришло именно сейчас, а не через 20 или 50 лет.

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

Кроме того, вы расписали все свои планы на ближайшие 50 лет, разбили их на отдельные маленькие задачи (самые маленькие задачи, длиной 20 и менее минут вы, всё таки, решили исключить из этого плана), указав для каждой задачи промежуток времени, который вы на неё потратите. Это промежуток можно сдвигать на 10 минут назад или вперед по времени, но не более.

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

К сожалению некоторые задачи перекрываются.

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

Вход

Первая строка содержит количество задач N, 1 < N < 50001. Каждая из следующих N строк содержит два целых числа из отрезка [0, 2000000000] --- начало и конец временного промежутка времени (моменты времени, представленные в минутах от некоторого фиксированного момента времени).

Выход Первая строка должна содержать целое число K — максимальное количество задач, которые могут не перекрываться с учётом того, что каждую задачу можно подвинуть не более чем 10 минут (на целое число минут) назад или вперёд по времени.

В следующих K строках находятся описание взятых задач. Каждая строка — это идентификатор задачи и величина смещения (целое число из отрезка [-10, 10]).

Вход#1
4
30 66
1 30
6 38
20 52
Выход#1
2
1 -10
3 0
Вход#2
7
67 98
30 66
1 30
37 58
6 38
40 62
48 70
Выход#2
4
2 -10
3 -10
6 0
0 3
Вход#3
7
56 98
30 66
1 30
37 58
6 38
40 62
48 70
Выход#3
3
2 -10
3 -10
6 0


Автор:
Артем Ворожцов, Личная студенческая олимпиада МФТИ, 7 октября 2007 г.
4 декабря 2007

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 34.204.171.214