|
Введення
|
Виведення
|
|
7 4
|
2 4
|
|
12 3
|
4 10
|
Задача TR2
Інокентій влаштував ремонт на кухні. Як професійний будівельник, він добре знає, що для кухні немає нічого кращого, ніж кахельна плитка.
Кухня Інокентія - це прямокутник W на H метрів. На жаль, потрібна плитка продається лише в одному магазині. Кожна плитка має
фіксований розмір a на b метрів, і на неї нанесено складний
візерунок. Для того, щоб підлога кухні мала гарний
вигляд, плитку треба класти так, щоб кожна сторона
плитки межувала максимум с одною плиткою і була паралельна одній з стін кухни. Візерунок на плитках дуже специфічний, тому плитки не можна повертати, навіть
усі одночасно — сторона кухні довжиною a повинна завжди бути паралельною
стороні плитки довжиною W.
Можливо, плитки доведеться розрізати на менші частини за допомогою прямолінійних розрізів вздовж однієї з сторін. При цьому отримані частини плитки можна
такої розрізати на менші частини. Інокентій хоче замостити кухню так, щоб у підсумку було використано мінимальну можливу кількість плиток та їх частин.
Допоможіть Інокентію підрахувати, яку мінімальну кількість
цілих плиток розміром a на b треба придбати, щоб красиво замостити всю кухню.
Технічні
умови.
Програма
читає з клавіатури через пропуск чотири цілих числа: W, H — розміри кухні, та a, b
– розміри плитки (1<=a<=W<=10000, 1<=b<=H<=10000). Программа виводить на екран одне
число — мінімальну кількість плиток, необхідних Інокентію. Пам’ятайте, що плитки ні в якому разі не можна повертати!
Приклади
|
Введення
|
Виведення
|
|
10 10 2 2
|
25
|
|
3 5 2 2
|
4
|
|
35 17 25 1
|
26
|
Задача Tr3.
Уявімо
собі масив, що складається з n елементів. Кожен елемент масиву характеризується
двома цілими додатними числами – l[i] і r[i]. Вважатимемо, що елемент
з індексом і впливає на елемент з індексом j, якщо
виконується одна з двох умов:
1)
i<j, а також j-i<=r[i]
2)
i>j, а також i-j<=l[i]
Ваша задача – для кожного елементу массиву порахувати кількість елементів, що на нього впливають.
Технічні
умови. Програма Tr3 читає з клавіатури натуральне число – кількість
елементів масиву n(1<=n<=100000) Наступна стрічка містить n
цілих чисел l[i], розділених пропусками (1<=l[i]<=100000)
Наступна
стрічка містить n цілих чисел r[i], розділених пропусками (1<=r[i]<=100000). Програма виводить на екран n чисел через пропуск - відповідь на задачу.
Приклад
Введення
4
1 2 1 2
1 2 3 4
Виведення
1 3 2 2
Задача Tr4
Вам
задана послідовність із n цілих чисел, в якій кожне число
від 1 до n зустрічається рівно один раз.
Підпослідовністю даної послідовності назвемо таку послідовність, яка може бути
отримана із початкової шляхом видалення деякої(можливо, нульової) кількості
елементів. Цікавою послідовністю назвемо послідовність, що утворюється за такими правилами:
1)
Послідовність із одного
або двох елементів є цікавою послідовністю
2)
Послідовність із трьох або
більше елементів вважається цікавою, якщо для будь-якого i>2 справедливим є таке твердження: якщо a[i]>a[i-1], то a[i-1]<a[i-2]; якщо ж a[i]<a[i-1], то a[i-1]>a[i-2].
Ваша
задача – знайти довжину найдовшої цікавої підпослідовності заданої
послідовності.
Технічні умови Програма Tr4 читає
з клавіатури число n(1<=n<=100000) – розмір вхідної послідовності, а далі
через пропуск n різних цілих чисел, розділених пробілом, кожне з яких
лежить у межах від 1 до n.
Програма
виводить на екран єдине число - відповідь на задачу
Приклад
Введення
6
1 5 6 3 4 2
Виведення
5
