Задача Mountain. Для поповнення бюджету країни, що відома своїми гірськими маршрутами, ввели новий податок для альпіністів. Величина податку пропорційна довжині маршруту, але, оскільки маршрут проходить по горах і пройдену відстань, яка залежить від висоти спуску і підйому, підрахувати складно, податок утримується без урахування висоти, тобто величина податку пропорційна горизонтальному переміщенню туристичної групи. Крім того, в силу старовинного звичаю усі туристичні групи повинні переміщатися по горах строго із заходу на схід. Експедиція хоче заощадити на податку, тому вона розробляє гірський маршрут з мінімальною величиною податку. При цьому, оскільки маршрут є гірським, він повинен містити підйом в гору і спуск з гори, тобто на маршруті має бути точка, яка знаходиться строго вище початку і кінця маршруту.
Альпіністи склала карту, що містить інформацію про висоту гір при пересуванні із заходу на схід. Висоти гір виміряні в точках через рівні відстані. Знайдіть на цій карті туристичний маршрут, за який податок буде мінімальний, а підйом та спуск, як і личить альпіністам, буде на маршруті.
Технічні умови. Програма Mountain читає з пристрою стандартного введення число N - кількість точок на карті гір. У наступному рядку N чисел через пропуск містять інформацію про висоту гір в даних N точках при русі із заходу на схід. Всі числа натуральні, не перевищують 105. Програма виводить два числа - номер точки початку маршруту і номер точки закінчення маршруту. Точки нумеруються від 1 до N. Якщо маршруту, що задовольняє умовам, не існує, програма повинна вивести одне число 0. Якщо знайдеться декілька маршрутів, то вивести той що починається ближче до точки старту експедиції.
Приклади
|
Введення
|
Виведення
|
|
7
18 10 15 20 20 10 3
|
3 6
|
|
3
9 8 5
|
0
|
Задача Lattice Є прямокутник розміром M*N, що складається з клітинок 1*1. Знайдіть кількість квадратів, всі вершини яких є вершинами клітинок. Сторони квадратів НЕ обов’язково паралельні до сторін прямокутника.
Технічні умови. Програма Lattice читає з пристрою стандартного введення два цілих числа - розміри прямокутника M та N (1≤M,N≤10000) і виводить на пристрій стандартного виведення шукану кількість квадратів.
Приклад
Введення 2 3
Виведення 10
 Задача Raft Петрик влітку відпочиває у бабусі в селі. Особливо йому подобається купатись на сільському озері. Посередині озера плаває пліт, який має форму прямокутника. Сторони плота спрямовані уздовж паралелей і меридіанів. Введемо систему координат, в якій вісь ОХ направлена на схід, а вісь ОY - на північ. Нехай південно-західний кут плоту має координати (x1, y1), північно-східний кут - координати (x2, y2). Петрик знаходиться в точці з координатами (x, y). Визначте, до якої сторони плоту (північної, південної, західної чи східної) або до будь-якого кута плоту (північно-західному, північно-східному, південно-західному, південно-східному) Петрику потрібно плисти, щоб якомога швидше дістатися до плоту.
Технічні умови. Програма Raft читає з пристрою стандартного введення шість чисел в наступному порядку: x1, y1 (координати південно-західного кута плоту), x2, y2 (координати північно-східного кута плоту), x, y (координати Петрика). Всі числа цілі і по модулю не перевершують 100. Гарантується, що x1 < x2, y1 < y2, x ≠ x1, x ≠ x2, y ≠ y1, y ≠ y2, координати Петрика знаходяться поза плотом. Якщо Петрику слід пливти до північної сторони плоту, програма повинна вивести на пристрій стандартного виведення символ «N», до південної - символ «S», до західної - символ «W», до східної - символ «E». Якщо Петрику слід пливти до кута плоту, потрібно вивести один з наступних рядків: «NW», «NE», «SW», «SE».
Приклад
|
Введення
|
Виведення
|
|
-1 -2 5 3 -4 6
|
NW
|
Задача Balloon. Герої Жюля Верна мандрували на повітряній кулі. У них був таймер та висотомір. Таймер відміряв час з моменту старту в годинах, а висотомір – висоту, на якій у цю мить знаходиться куля. Результати вимірів вони записували, інколи – не щогодини, але якщо в час T1 висота складала Y1, а в час T2 висота складала Y2, то між годинами T1 та T2 висота рівномірно змінювалася від Y1 до Y2. Мандрівники вирішили дізнатися, скільки часу тривав самий затяжний підйом (тобто максимальний проміжок часу, на якому висота зростала).
Технічні умови. Програма Balloon читає з пристрою стандартного введення (клавіатури) число N (1 ≤ N ≤105) – кількість найдених записів. В наступних N стрічках по 2 цілих числа А та В, де А – номер години польоту, а В – висота в цей момент часу. (1 ≤ А, В ≤ 109). Гарантується, що всі А різні. Програма виводить на пристрій стандартного введення (екран) єдине число – тривалість самого затяжного підйому у годинах.
Приклад
Введення Виведення
10 3
1 6
2 20
3 15
4 10
6 13
7 20
8 20
9 20
10 20
11 21
|
