Завдання 1 туру NetOI-2012

Розв'язки приймаються до 0 годин 17 листопада 2012 р. Здати розв'язок задачі можна лише 1 раз.  Працює  on-line перевірка розв'язків на авторських тестах. Кількість перевірок необмежена.

Увага!!!!  Не плутайте on-line перевірку розв'язків та надсилання

ОСТАТОЧНОГО розв'язку на офіційну перевірку!!!

Задача Rectangle

На  квадратному   аркуші паперу «в клітинку» (розміру N*N кліток) намальовано декілька  прямокутників.  Кожен  прямокутник  складається  з  цілих кліток;  різні  прямокутники  не  накладаються  один на одного і можуть стикатися лише кутами. Знайдіть кількість цих прямокутників.

Технічні умови  Програма Rectangle читає з клавіатури число N (2 ≤ N ≤ 100)   а в кожному з наступних N рядків міститься  по N цифр 0 чи 1 через пропуск  (1- якщо клітинка належить якомусь з прямокутників і 0, якщо ні). Програма виводить на  екран єдине число – кількість прямокутників.

 Задача Parket1

Щоб зобразити за допомогою паркету  Новий Візерунок, треба N₁ дощечок розмірами 1×1, N₂ дощечок розмірами 2×1, N₃ роз­мірами 3×1, N₄ розмірами 4×1 та N₅ дощечок розмірами 5×1. Купити можна лише дощечки розмірами 5×1. Дощечки можна різати, але не можна склеювати. Наприклад, коли потрібні п’ять дощечок 2×1, їх не можна зробити з двох дощечок 5×1, але можна з трьох. Для цього дві з них розріжемо на три частини 2×1, 2×1 та 1×1 кожну, а третю — на дві частини 2×1 та 3×1. Отримаємо потрібні п’ять дощечок 2×1, а дві дощечки 1×1 та одна 3×1 підуть у відходи. Напишіть програму, яка, прочитавши кількості дощечок N₁, N₂, N₃, N₄ та N₅, знайде, яку мінімальну кількість дощечок 5×1 необхідно купити.        

 Технічні умови Програма Parket1 читає з клавіатури п’ять чисел N₁, N₂, N₃, N₄ та N₅ (саме в такому порядку), розділені пропусками. Всі числа невід’ємні, і їх сума менша,   ніж 2*10⁹  Програма виводить на екран кількість дощечок 5×1, які необхідно купити.

 Задача Birthday

Маленькому Вані на день народження подарували велику прямокутну шоколадку, яка складається з m*n квадратних плиточок. Ваня їсть лише квадратні шоколадки, тому він вирішив виламати квадратний шматок (можливо, це буде вся шоколадка), з’їсти його, а решту роздати друзям. Зрозуміло, ламати плиточки не можна. Допоможіть Вані підрахувати кількість способів поласувати шоколадом.

  Технічні умови. Програма Birthday читає з клавіатури через пропуск два числа m та n (1<=m,n<=1000) і виводить на екран шукану кількість способів.

Задача Fazenda

Згідно Закону про землю кожний громадянин зобов’язаний отримати ділянку землі і зареєструвати її у Великому Прозорому Будинку (ВПБ). Ділянка землі має форму трикутника, в реєстрі ВПБ вказані відстані від кожної вершини до прямої, що з’єднує дві інші вершини (висоти трикутника). Громадяни почали питати головного програміста ВПБ, яка площа їхньої ділянки та якої довжини  доведеться будувати паркан. На жаль, головний програміст не брав участі в NetOI і тому не зміг допомогти. Допоможіть Ви.

Технічні умови. Програма Fazenda читає з клавіатури через пропуск висоти трикутника - дійсні числа h1, h2, h3 (1<=h1, h2, h3<=10000) та виводить на екран через пропуск без заокруглення  площу і периметр трикутника. Якщо трикутника не існує, вивести через пропуск двічі 0.

Задача Second.  Позначимо через Рі і-те просте число (Р1=2, Р2=3, Р3=5 тощо). Для даного числа n розглянемо вираз: Р1 / Р2 / Р3 / … / Рn. Напишіть програму, яка б підраховувала, скільки різних раціональних чисел можна отримати, розставляючи в даному виразі дужки. Наприклад, якщо n=4, то таких чисел буде теж 4: (((2/3)/5)/7 = 2/105, 2/(3/(5/7)) = 10/21, (2/3)/(5/7)=14/15 та 2/((3/5)/7) = 70/3.

Технічні умови.  Програма Second читає з клавіатури  ціле число n (від 2 до 100) і виводить на екран кількість можливих раціональних чисел.

Завдання підготували Г.Непомнящий, Ю.Пасіхов, І. Порубльов