Сайт підготовки до олімпіади з інформатики

Ремонт кораблів (DOCKS)

На судоремонтний завод для докового ремонту одночасно прийшло N кораблів. В док на ремонт може зайти тільки одне судно. Необхідний час стоянки в доці для кожного судна різний. Після ремонту судно одразу йде в рейс.

Скласти програму, що визначає порядок постановки кораблів у док, при якій сумарний час, протягом якого кораблі чекають своєї черги, мінімальний.

Формат вхідних даних:

У першому рядку файлу міститься число N – кількість кораблів, що прийшли на ремонт (1£N£10000). В наступних N рядках – пари чисел – номер судна та через пропуск – час ремонту (натуральні числа, не більші 10000).

Формат вихідних даних:

Вихідний файл повинен містити послідовність чисел ­– номери кораблів, у тому порядку, в якому вони заходять у док.

Між числами має бути по одному проміжку. Наприкінці рядка проміжок не ставте.

Приклад вхідних та вихідних даних:

Працівники (STAFF)

(XVІІ Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)

На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.

Існують правила, за якими визначається, чи можна обробляти деталь на певному верстаті.

$11)      Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.

$12)      У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.

Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.

Напишіть програму STAFF, яка за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.

Формат вхідних даних:

Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2≤N≤28) – кількість деталей яку необхідно обробити.

Формат вихідних даних:

Єдиний рядок вихідного файлу STAFF.RES має містити ціле число – максимальну можливу кількість працівників заводу.

Приклад вхідних та вихідних даних:

Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий  має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станку B – деталі 2 та 4. Інших варіантів послідовності обробки немає.

Затори на дорогах (JAMMING)

Автомобільні затори трапляються усюди, навіть у нашому невеличкому містечку. Дороги у нас мають дві смуги в одному напрямку, а автомобілі є лише двох типів габаритів: легкові (у пробці займають квадрат 1х1, якщо за 1 взяти ширину смуги) та вантажні (у пробці займають місце 2х1 вздовж смуги).

Водії дуже дисципліновані у тому плані, що вони не стають поперек смуги, не займають чужу площу, але й не залишають вільних місць.

Визначте, скільки існує різних за послідовністю типів машин (легкова - вантажна) заторів між мерією міста та моїм будинком, якщо вони на одній вулиці, а відстань між ними S.

Формат вхідних даних:

Вхідний файл містить єдине число S (1£S£10000) – задана відстань.

Формат вихідних даних:

Єдиний рядок вихідного файла повинен містити відповідь – кількість розстановок тур.

Достеменно відомо, що кількість цифр у відповіді не перевищує 700.

Приклад вхідних та вихідних даних:

Кубики (CUBES)

(XV Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)

Тривимірна фігура складається з одиничних кубиків. За фігурою можна побудувати її фронтальну та праву проекції. Очевидно, що за цими двома проекціями не завжди можна відтворити фігуру.

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

Формат вхідних даних:

У першому рядку вхідного файлу CUBES.DAT знаходиться три числа N, M та К, що задають розміри проекцій (1≤ N, M, K ≤100). Далі задаються дві проекції: спочатку фронтальна, а потім права. Проекція задається N рядками, кожний з яких складається з чисел 0 та 1, що розділені прогалиною. Для фронтальної проекції таких чисел буде M, а для правої — K. 0 означає вільну клітинку проекції, 1 — заповнену.

Формат вихідних даних:

У єдиному рядку вихідного файлу CUBES.SOL повинно знаходитися два числа: мінімальна та максимальна кількість кубиків, які можна було б використати для побудови фігури із заданими проекціями.

Приклад вхідних та вихідних даних: