Главная->Інформатика та програмування->Содержание->Додаткові задачі, що пропонувалися на Всеукраїнських олімпіадах з програмування у 2001 та 2002 роках (м. Одеса, м. Чернівці)

Додаткові задачі, що пропонувалися на Всеукраїнських олімпіадах з програмування у 2001 та 2002 роках (м. Одеса, м. Чернівці)

Задача “Шифр”

Задано символьний рядок 5^і довжини N (0 < N < 100) та словник, що містить М слів (0 < М < 100), довжина кожного з яких не перебільшує N. Слова словника і рядок 5 складаються з літер а, Ь, ..., 2.

Завдання

Складіть програму СІРНЕР, котра визначає найменшу кількість символів, яку треба викреслити із заданого рядка 5, щоб результуючий рядок можна було подати як послідовність слів словника. Кількість використань кожного слова не обмежується. Вважається, що пустий рядок можна подати за допомогою слів будь-якого словника.

Рядок у прикладі після викреслювання зайвих букв £ і Ь набуде вигляду аЬасЬгізуа (було зроблено два викреслювання: аЬа£сЬЬгі.зуа) , та може бути поданий як послідовних наступних слів: а, ЬасЬ, гі.зу, а.

Вхідні дані

В першому рядку вхідного файла СІРНЕК. БАТ знаходяться два цілих числа N та М, відокремлених пропусками. У другому рядку знаходиться символьний рядок 8. У кожному з наступних М рядків знаходиться слово словника.

Приклад вхідного файлу

11 5 аЬаІсШзуа аЬа а Ьасії гізу 2ЄҐ0

Вихідні дані

В єдиному рядку вихідного файлу СІРНЕК.ЗОЬ має знаходитись натуральне число - мінімальна кількість викреслювань, після яких зашифрований рядок можна подати у вигляді послідовності слів словника.

Приклад вихідного файлу 2

Задача "Абракадабра"

Під час своєї роботи алгоритм стискання даних методом «сортування блоку» застосовує до блоків даних перетворення, яке визначається наступним чином.

Рядок Р називається ротацією рядка 8, якщо він утворений циклічним зсувом символів 8, тобто якщо 8=аіа₂...а_№ де а₁ —

і-ий символ рядка 8, то Р=а_ра_р+і ...адаї ...а_р-ь де 1<р<М. Розглянемо таблицю М розміру NxN, рядками якої є всі ротації рядка 8, відсортовані у лексикографічному (словниковому) порядку за зростанням.

Нехай рядок Ь є останнім стовпчиком таблиці М. Пряме перетворення отримує на вхід рядок 8, видає рядок Ь та число К —

номер рядка таблиці М, що містить рядок 5. (Якщо таких рядків декілька, видається номер будь-якого з них).

Для 5='аЬгака' таблицю М зображено на малюнку. Рядок 5 знаходиться у другому рядку таблиці М, £=‘кагааЬ\

Завдання

Напишіть програму АВКАКА, що виконує зворотнє перетворення, тобто отримує на вхід рядок Ь і число К, та видає рядок 5.

Вхідні дані

Перший рядок вхідного файлу АВКАКА.БАТ містить два цілих числа: К та И, 1<И<30000, 1<К<И. Другий рядок містить N символів рядка Ь — маленьких латинських літер.

Вихідні дані

Єдиний рядок вихідного файлу АВКАКА. 8ОЬ повинен містити рядок

5 .

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

АВКАКА.йАТ	АВКАКА.ЗОІ.
2 6 кагааЬ	аЬгака

 

Задача "Циферблат"

На циферблаті записана послідовність чисел у двійковій системі числення. Циферблат може бути розбитий на сектори. Лінії розбиття можуть проходити як між числами, так і між цифрами одного числа, розбиваючи його на два чи більше чисел. Для кожного сектора можна порахувати суму чисел, які в ньому розташовані.

Кожне число в послідовності не дорівнює 0, та його запис почитається з одиниці. Кількість цифр в двійковому запису числа не перевищує 25. Загальна кількість цифр на циферблаті не більша за 100.

На малюнку зображено звичний нам циферблат з числами від 1 до 12 (в дещо незвичному вигляді). Його розбито на 4 сектори. Суми для секторів будуть 1, 15, 18 та 36.

Завдання

Напишіть програму БІАЬ, що за заданою послідовністю визначає кількість різних розбиттів циферблату на сектори, такі що сума чисел у всіх секторах однакова.

Вхідні дані

В єдиному рядку вхідного файлу БІАЬ.БАТ задана послідовність чисел. Числа послідовності розділені пропуском.

Вихідні дані

В єдиному рядку вихідного файлу БІАЬ.8ОЬ повинно знаходитися натуральне число — кількість шуканих розбиттів циферблату на сектори.

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

йІАІ-.ОАТ	йІАІ-.ЗОІ-
101 1 1101	9

 

Задача "Кубики"

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

Завдання

Напишіть програму СЦВЕ8, що отримує на вхід фронтальну та праву проекції фігури та визначає мінімальну          та                                                                                       максимальну кількість

кубиків, яку можна було б використати            для побудови      фігури   із

заданими проекціями.

Вхідні дані

В першому рядку вхідного файлу СЦВЕ8.БАТ знаходиться три числа N, М та К, що задають розміри проекцій (1<^ М, К<100). Далі задаються дві проекції: спочатку фронтальна, а потім права. Проекція задається N рядками, кожний з яких складається з чисел 0 та 1, що розділені пропуском. Для фронтальної проекції таких чисел буде М, а для правої — К. 0 означає вільну клітину проекції, 1 — заповнену. Вихідні дані

В єдиному рядку вихідного файлу СЦБЕ8.8ОЬ повинно знаходитися два числа: мінімальна та максимальна кількість кубиків, які можна було б використати для побудови фігури із заданими проекціями. Приклад вхідних та вихідних даних

СІІВЕЗ.йАТ	СІІВЕЗ.ЗОІ.
2 2 3	4 7
1 0
1 1
0 0 1
1 1 1

 

 

 

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

Схожі підручники

• Курс Інвестування (стисло)
• Бонківська Система задачі
• Філософія Хрестоматія (частина 2)
• Лекції з Філософії (частина 2)
• Методичні вказівки до виконання розрахункової роботи з дисципліни «Системи промислових технологій в галузях економіки»
• НАВЧАЛЬНИЙ ПОСІБНИК ГРОШІ ТА КРЕДИТ теорія і практика (частина 2)