Задача Foto

Василько  отримав завдання розмістити на шкільному сайті фото з новорічного свята. Василько знав, що фото слід «вписати»  в заданий  прямокутник, тобто  фото зменшується (або збільшується) таким чином, що одна з його сторін стає точно рівною відповідній стороні заданого прямокутника, а друга сторона підбирається  так, аби співвідношення сторін отриманого зображення було як можна ближче до оригіналу. При цьому розміри отриманого зображення повинні бути найбільш можливими,  але не повинні  при цьому  перевищувати  розміри  прямокутника.  Всі  розміри повинні бути натуральними числами. Зрозуміло, що повертати зображення не можна.

 Технічні умови. Програма Foto читає з пристрою стандартного введення  4 цілих числа A, B,С,D (1≤ A;B;C;D ≤ 10⁴), где A и B — ширина і висота початкового фото, а C и D — ширина и висота прямокутника,  в який це фото слід помістити. Програма виводить а екран 2 цілих числа – ширину та висоту вже обробленого зображення.

Приклади

Введення                                Виведення

1280 720 640 480                   640 360

640 480 1280 720                   960 720

Задача Kinder

Петрик П’яточкін вирішив подарувати своїм  K друзям на свято по кіндер-сюрпризу з іграшкою всередині.  Кожен кіндер-сюрприз містить одну іграшку – машинку, ляльку або робота. Петрик хоче, щоб його друзі не посварились між собою, тому вони повинні отримати однакові іграшки. У крамниці є рівно C кіндер-сюрпризів  з машинками, D з ляльками і R з роботами, але невідомо, яка іграшка знаходиться в якому  кіндер-сюрпризі. Яку найменшу кількість   кіндер-сюрпризів  повинен придбати Петрик, щоб серед них гарантовано було хоча б K однакових?

Технічні умови

Програма Kinder читає з клавіатури натуральні числа K, C, D, R

(1≤ K,C,D,R≤1000000) і виводить на екран мінімальну кількість кіндер-сюрпризів або 0, якщо придбати неможливо.

Приклади

Введення

5 6 7 10

Виведення

13

Введення

16 10 7 5

Виведення

0

Коментар

У першому прикладі Петрику може дістатись по 4 іграшки кожного типу, тому 12 іграшок не вистачить

Задача  Balls2

На столі розкладено N червоних та  M синіх  кульок. Двоє грають в гру, хід гравця полягає в тому, щоб взяти дві довільні кульки і покласти на стіл замість забраних  червону кульку, якщо він забирав кульки різного кольору,  або кульку синього кольору, якщо забирав кульки одного кольору. Гравці ходять по черзі, гра  триває поки  не залишиться 1 кулька.  Перемагає перший гравець, якщо остання кулька виявилась червоного кольору, якщо ж  синього - другий.  Дізнайтеся  для заданої кількості  кульок, хто виграє при оптимальній грі обох гравців.

Технічні умови. Програма Balls2 читає  з клавіатури єдине число Т – кількість тестів (1 ≤  T  ≤500). В наступних  Т рядках  задано по два цілих числа   N і M

(1 ≤  N +M,  0 ≤  N;M  ≤  10⁹)

Програма Balls2   виводить   для кожного тестового прикладу у новому рядку  1, коли виграє 1-й гравець і 2,  коли виграє другий  

Приклад

Введення     Виведення

3                   1

1 0                 2         

0 1                 1         

1 1

Задача Queens

Ферзь – шахова фігура, яка ходить по горизонталі, вертикалі або діагоналі на довільну кількість клітинок. Клітинка безпечна, якщо на ній не стоїть ферзь і коли жоден ферзь не може в ній опинитись за один хід. На квадратній шахівниці розміщені ферзі. Порахуйте на ній кількість безпечних клітинок.

Технічні умови. Програма Queens читає з клавіатури через пропуск два числа – розмір шахівниці N та кількість ферзів K (1≤N≤10000, 1≤K≤100000). Далі програма читає K рядків по два розділених пропуском натуральних числа i та j, не більших N – номери рядків і стовпчиків, на яких стоїть відповідний ферзь. Рядки і стовпчики нумеруються від 1 до N цілими числами. Жодні два ферзі не стоять на одній клітинці. Програма виводить на екран єдине число – кількість безпечних клітинок.

Приклад

Введення

3 2

3 2

2 3

Виведення

1