XІ обласна олімпіада – 1997 рік

Визначення сторiнок

(В.О.Бардадим, В.В.Бондаренко)

При друкуваннi великих документiв може виникнути потреба друкувати не весь документ, а тiльки деякi його сторiнки. Серед аргументiв програми друку є рядок з послiдовнiстю номерiв сторiнок. Потрiбно надрукувати не окремi сторiнки, а дiапазони сторiнок i, можливо, вказувати початок i кiнець дiапазонiв, а не послiдовнi числа.

Завдання: Напишiть програму, яка буде перетворювати списки сторiнок у вiдповiдну послiдовнiсть номерiв сторiнок.

Вхiднi данi: Вхiдний файл PRINT.DAT мiстить один рядок, який має таку структуру: сторiнка–1, сторiнка–2, сторiнка-3, ..., сторiнка – N.

Сторiнка – i – або номер сторiнки, або дiапазон у виглядi початок–кiнець (початок <= кiнець).

Сторiнки та дiапазони перерахованi в зростаючому порядку i не перетинаються. Дiапазон включає початкову та кiнцеву сторiнки. Номери сторiнок – числа вiд 1 до 1000000. 1 <= N <= 1000000.

Вихiднi данi: Результат треба вивести до файлу PRINT.SOL у виглядi сторiнка-1, сторiнка-2, сторiнка-3,..., сторiнка – М без пропускiв.

Технiчнi вимоги: Ваша програма повинна мати назву PRINT.*, де розширення залежить вiд мови програмування.

Приклад:

PRINT.DAT

1,4-5,7-7,10-20

PRINT.SOL

1,4,5,7,10,11,12,13,14,15,16,17,18,19,20

Множина

(М.З.Грузман)

Нехай х – деяке натуральне число, а М_х – множина чисел, що утворюються з числа х перестановкою його цифр. Будемо називати число у безпосередньо наступним для х, якщо:

1. у належить М_х;

2. не iснує числа у₁, що належить М_х i для якого виконується спiввiдношення

х < y₁ < y.

Будемо називати число z безпосередньо попереднiм для х, якщо:

1. z належить М_х;

2. не iснує числа z₁, що належить М_х i для якого виконується спiввiдношення

z < z₁ < x.

Зауваження. Числа розглядаються в десятковiй системi числення. Нулями лiворуч вiд першої ненульової цифри нехтуємо.

Дано: натуральне х.

Отримати: у, що є безпосередньо наступним для х, z, що є безпосередньо попереднiм для х.

Технiчнi вимоги: Здiйснюється введення х з клавiатури та виведення у та z на екран дисплею.

Приклади.

1. Якщо х = 121, то у = 211, z = 112;

2. Якщо х = 112, то у = 121, а безпосередньо попереднього числа для х не iснує;

3. Якщо х = 211, то z = 121, а безпосередньо наступного числа для х не iснує.

Мiкроорганiзми

(М.З.Грузман)

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

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

Дано: прямокутне фото розмiром m x n клiтинок, частину яких позначено.

Отримати: кiлькiсть органiзмiв на фотознiмку.

		*	*	*
	*	*	*	*	*	*	*	*
*								*
				*		*		*
		*		*				*
	*	*		*	*	*	*	*

Технiчнi вимоги: Введення розмiрiв m та n на фотознiмку здiйснюється з клавiатури за запитом програми. Саме фото у закодованому виглядi мiститься у файлi PHOTO.DAT. Кожному рядку клiтинок вiдповiдає запис у файлi. Позначенiй клiтинцi вiдповiдає символ "*", а непозначенiй – "0" (нуль).

Приклад. Фотознiмок 6 х 10 має вигляд, зображений на рисунку. На цьому знiмковi 4 мiкроорганiзми.

Шахiвниця

В квадратнiй дошцi розмiром n x n клiтинок вирiзали деякi двi клiтинки. Отже, дiстали дошку, що складається з n²–2 клiтинок. Маємо також (n²–2)/2 дощечки розмiром 1 х 2 клiтинок, кожну з яких дозволяється класти на дошку так, щоб накривались рiвно двi її клiтинки. Дощечки не можуть перекриватися.

Дано: n – довжину сторони дошки (в клiтинках)

(x₁,y₁), (x₂,y₂) – координати вирiзаних клiтинок,

1 <= x₁,y₁, x₂,y₂ <= n.

Отримати: вiдповiдь на питання – чи можна накрити дощечками розмiром 1 х 2 всi клiтинки заданої дошки? Якщо можна, то вказати, як це зробити.

Технiчнi вимоги:

1. Забезпечити введення з клавiатури за запитом програми:

а) n – довжину сторони дошки (в клiтинках),

б) координати вирiзаних клiтинок.

2. Вивести на екран дисплею повiдомлення: "можливо" чи "неможливо".

3. Якщо можливо, вивести на екран дисплею координати пар клiтинок, що вiдповiдають кожнiй дощечцi ( згiдно iз зразком ) в довiльному порядку.

Приклад: Для дошки 4 х 4 вiдповiдь може бути такою:

можливо

(1, 1) – (1, 2)

(3, 4) – (4, 4)

(3, 2) – (4, 2)

(2, 1) – (2, 2)

(2, 3) – (2, 4)

(3, 3) – (4, 3)

(3, 1) – (4, 1)

Мережа

Комп'ютерна мережа з'єднує комп'ютери в рiзних мiсцях. Не всi комп'ютери з'єднанi безпосередньо, але кожен комп'ютер може надсилати повiдомлення довiльному iншому, передаючи їх через нуль або бiльше промiжних комп'ютерiв. Мережа є деревом, тому завжди iснує лише один шлях мiж деякою парою комп'ютерiв.

Проходження повiдомлення вiд одного комп'ютера до iншого, безпосередньо з ним з'єднаного, потребує одну секунду (комп'ютери розташованi досить далеко один вiд одного), i комп'ютер не може вiдсилати повiдомлення кiльком комп'ютерам одночасно.

Протягом першої секунди початковий комп'ютер може надiслати повiдомлення одному з своїх сусiдiв. Протягом другої секунди вже два комп'ютери (початковий та його сусiд) можуть надiслати повiдомлення своїм сусiдам, i так далi.

Завдання: Визначити мiнiмальний час, за який можна передати повiдомлення вiд вказаного комп'ютера всiм iншим комп'ютерам в мережi.

Вхiднi данi: Опис мережi мiститься в файлi NET.DAT i має такий формат:

рядок 1: кiлькiсть N комп'ютерiв в мережi (1<= N <=100)

рядок 2: номер початкового комп'ютера

рядок 3: кiлькiсть сусiдiв комп'ютера 1, потiм їх номери, вiдокремленi пропусками

. . .

рядок N+2: кiлькiсть сусiдiв комп'ютера N, потiм їх номери, вiдокремленi пропусками

Вихiднi данi: Результат треба вивести до файлу NET.SOL.

Технiчнi вимоги: Ваша програма повинна мати назву NET.*, де розширення залежить вiд мови програмування

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

NET.DAT NET.SOL

5 3

2

1 2

3 1 3 4

1 2

2 2 5

1 4

Шляхи

В однiй з клiтинок сторiнки зошита знаходиться фiшка. Горизонталь, на якiй ця фiшка мiститься спочатку, будемо називати стартовою. Фiшку можна пересувати лiворуч, праворуч, вгору або вниз. За один хiд фiшку можна пересунути на одну клiтинку .

Дано: кiлькiсть ходiв n, якi дозволяється зробити.

Отримати:

а) кiлькiсть шляхiв, що повертають фiшку на стартову горизонталь;

б) перелiк всiх шляхiв, що повертають фiшку на стартову горизонталь; кожен шлях представити у виглядi послiдовностi ходiв (L - лiворуч, R - праворуч, U - вгору, D - вниз );

в) дати графiчну iлюстрацiю шляхiв фiшки, що повертають її на стартову горизонталь; кожен наступний шлях має з'являтись на екранi при натисненнi на будь-яку клавiшу;

г) доступ до завдань а), б), в) здiйснити через меню.