Вітаю Вас, Гость

Задача А. "Космодром «Центральний»"

Бали за задачу: 100
Обмеження часу: 1 с
Обмеження пам'яті: 64 M

Ім'я файлу, який містить вхідні дані: cosmodrome.in
Им'я вихідного файлу: cosmodrome.out

   2148 год. Більше століття назад люди освоїли практично усі планети нашого Всесвіту, і міжгалактичні подорожі стали повсякденністю. Космодром «Центральний» спеціалізується на запуску космічних вантажних кораблів. Пускові двигуни усіх космічних кораблів працюють на сонячній енергії. В залежності від вантажопідйомності кораблю для запуску може бути потрібно різне число ерстедів. Ерстед - одиниця виміру сонячної активності. Кожен робочий день космодрому починається з того, що відділ прогнозування космодрому представляє відділу роботи з клієнтами прогноз сонячної активності на найближчі N днів починаючи із завтрашнього. Прогноз можна представити у вигляді послідовності із N цілих чисел Aj, де Aj - число ерстед сонячної активності, що прогнозується в j-й день. Відділ роботи з клієнтами займається прийомом і обробкою заявок на запуск. Кожна і-я заявка описується за допомогою трьох цілих чисел Si, Fi і Ri. Si – мінімальна кількість днів, яка має пройти між запуском корабля і моментом подачі заявки, Fi – відповідно максимальне число днів і Ri – необхідна для запуску кількість ерстед. Результатом обробки і-ї заявки є число Li, де Si ≤ Li ≤ Fi і число | ALi – Ri | мінімальне із можливих. Нижче наведено приклад обробки одного запиту для N = 10 , S1 = 4, F1 = 9 і R1 = 81. Результат обробки заявки – число L1 = 7. Вам же знайти саме значення | ALi – Ri |.

Малюнок №1: другий приклад, перший запит.

   Космодром дійсно великий і має можливість запускати в день практично необмежену кількість кораблів. Ваша задача – розробити програму, яка по заданому прогнозу дозволить опрацювати усі прийняті за день заявки.

   Вхідні дані:
   Перший рядок вхідного файлу містить два цілих числа N і М (1 ≤ N, М ≤ 65536). N – кількість днів в прогнозі, М – кількість поданих за день заявок. Другий рядок вхідного файлу містить N цілих чисел Aj (1 ≤ Aj ≤ 109). Числа у рядку розділяються одиночними пробілами. Кожен із наступних М рядків описує одну заявку і містить три цілих числа Si, Fi і Ri (1 ≤ Si ≤ Fi ≤ N; 1 ≤ Ri ≤ 109).

   Вихідні дані:
   Вихідний файл має містити М цілих невід’ємних чисел Li, де Li – результат обробки і-ї заявки. Порядок слідування чисел | ALi – Ri | у вихідному файлі має відповідати порядку введення заявок.
   Зауваження:
   У 20% тестів N ≤ 5000.

Приклади

Вхідні дані   Результат роботи
5 2
1 3 2 9 5
1 3 3
2 4 7
0
2


 
10 3
81 70 52 19 85 41 78 62 98 31
4 9 81
1 7 30
3 8 52
3
11
0


 

 

Задача B. "Гра із сірниками"

Бали за задачу: 100
Обмеження часу: 100 мс
Обмеження пам'яті: 64 M

Ім'я файлу, який містить вхідні дані: game.in
Им'я вихідного файлу: game.out

   Степан вирішив кинути палити і щоб не думати про цигарки придумав гру із сірниками. У нього є дві коробки сірників по N штук у кожній. Він хоче викласти із сірників однієї коробки якомога більше число, а іншої — якомога менше число, причому він хоче використати усі сірники. Допоможіть Степану. Те, як з сірників викладаються цифри, ви можете подивитися на рисунку, наведеному нижче. Врахуйте, що Степан знає, що ставити на початок чисел нулі не можна.

   Вхідні дані:
   У першому рядку вхідного файлу задано натуральне числоN (2 ≤ N ≤ 2 000).

   Вихідні дані:
   У вихідний файл через пробіл виведіть два числа: найбільше і найменше натуральні числа, які може викласти Степан, витративши рівно N сірників на кожне з чисел.

Приклади

Вхідні дані   Результат роботи
5 71 2

 

Задача C. "(N, K) - те царство"

Бали за задачу: 100
Обмеження часу: 100 мс
Обмеження пам'яті: 64 M

Ім'я файлу, який містить вхідні дані: kingdom.in
Им'я вихідного файлу: kingdom.out

   У ті ж самі незапам'ятні часи в тому ж Тридев'ятому Царстві відбувалися ще деякі цікаві події, згадки про які давно вже стерлися з часом. Йдеться про те саме - мудрого радника і про його таємну дослідницьку лабораторію, яка перебувала в глибоких надрах замкового підземелля. Тоді як цар з царицею народжували синів, ростили їх і ділили між ними спадщину, радник тримав штат програмістів-простолюдинів, які, як виявилося, не були такими вже простолюдинами. А були вони геніальними дослідниками проблеми існування паралельних світів.
За довгі роки копіткої дослідницької роботи, провівши безліч експериментів, із залученням як природознавства, так і магічного знання (астрології, алхімії, некромантії і тп.), Програмістам все-таки вдалося виграти один бій з трансцендентністю.
Дослідження показали, що є ще царства крім Тридев'ятого, і вони характеризуються як (N, K)-ті Царства. Але існувати (N, K)-те Царство може лише в тому випадку, якщо K може бути представлено у вигляді суми не більше ніж N простих чисел. Нагадаємо, що натуральне число X, більше одиниці, називається простим, якщо воно не ділиться без остачі ні на які числа, крім 1 і X.

   Наприклад, (3, 9)-е (Тридев'яте) Царство існує, бо 9 = 2 + 7 (ще варіанти: 9 = 3 + 3 + 3 і 9 = 2 + 2 + 5). Також має право на існування і (2, 10)-е (двадесяте) Царство, т.к. 10 = 5 + 5. Водночас (2, 27)-е (Двадвадцатьсьоме) Царство існувати не може, оскільки 27 не можна представити у вигляді суми не більше ніж двох простих чисел.
   Знайдіть кількість існуючих (N, K)-царств за умови, що числа N і K можуть змінюватися в деякому діапазоні: a ≤ N ≤ b, c ≤ K ≤ d.

   Вхідні дані:
   Цілі числа a і b - нижня і верхня межа на N. Цілі числа c і d - нижня і верхня межа на K.

   Вихідні дані:
   Ціле число, рівне кількості існуючих (N, K)-царств, для яких a ≤ N ≤ b і c ≤ K ≤ d.

   Обмеження:
   1. Число a від 1 до 1 000 000 включно.
   2. Число b від a до a + 1000 включно.
   3. Число c від 1 до 1 000 000 включно.
   4. Число d від c до c + 1000 включно.

Приклади

Вхідні дані   Результат роботи
1
1
2
10
4


 
1
2
20
30
12


 
2
4
45
64
58


 
1
20
459588
470425
15701


 

 

Задача D.

Бали за задачу: 100
Обмеження часу: 1 с
Обмеження пам'яті: 64 M

   На планеті Зем живуть істоти схожі на людей, але досконаліші (так вони вважають). Земці мають по три пальці на обох руках і тому користуються системою числення з основою 6. Допоможіть інопланетянам знайти різницю двох чисел. Земці забобонні і тому не використовують числа довжина яких більша або рівна 444 знаків.

   Вхідні дані:
   В двох рядках вхідного потоку записані числа в Земській системі числення.

   Вихідні дані:
   У єдиний рядок вихідного потоку різниця першого і другого чисел.

Приклади

Вхідні дані   Результат роботи
10
2
4
 
12.05
-0.52
13.01
 

 

Задача E.

Бали за задачу: 100
Обмеження часу: 2 с
Обмеження пам'яті: 64 M

   Вадим з Андрієм повинні навчитися грати в гру «Виграй або розділи та виграй». Ігрове поле являє собою рядок, який розбитий на клітинки. В клітинках записані цілі числа. Вадим з Андрієм по черзі повинні виконувати одну з двох дій: або забирати собі крайню клітинку рядка, або розрізати рядок на дві частини. Право першого кроку в обох утворених рядках отримує суперник. Завдання кожного – зібрати максимальну суму чисел. Розрахуйте, які максимальні суми зберуть хлопці при оптимальних стратегіях гри.

   Вхідні дані:
   Перший рядок вхідного потоку містить натуральне число n (1 ≤ n ≤100) – розмір ігрового поля. У наступному рядку через пропуск записані n чисел, абсолютне значення яких не перевищує 1000000.

   Вихідні дані:
   У єдиний рядок вихідного потоку записати два числа – суми зібраних клітин першим та другим гравцями.

Приклади

Вхідні дані   Результат роботи
3
1 100 5
6 100
 
6
9 100 9 9 100 9
200 36