Задача TR1
До Вінницького зоопарку скоро приїдуть нові мешканці – аж N папуг. Поки вони в дорозі, Рада орнітологів вирішує їхню долю. А саме, як розподілити по наявним к зоопарку К кліткам так, щоб жодна клітка не залишилась порожньою. Оскільки головним критерієм при розміщенні птахів є комфорт, орнітологів цікавить, скільки папуг житиме в клітці, що найбільше заселена (тобто в клітці з максимальним числом папуг). Вам, як головному (і, як це не прикро, єдиному) програмісту зоопарку, доручили оцінити цю величину, тобто знайти, яку мінімально та максимально можлива кількість птахів може жити в найбільш заселеній клітці при умові, щоб жодна клітка не залишиться порожньою.
Технічні умови
Програма читає з клавіатури два натуральних числа, розділених пропуском: N – кількість папуг і К – кількість кліток (1<=К<=N<=109). Програма виводить на екран два натуральних числа: мінімально та максимально можливу кількість папуг у найбільш заселеній клітці.
Приклади
|
Введення |
Виведення |
|
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
© LIKT 1998-2024