Произведение (multiply)



Скачати 56.17 Kb.
Дата конвертації23.01.2018
Розмір56.17 Kb.

Одеська літня школа олімпійського резерву 2006, група № 1


Закріплення теми „Теорія графів та потоки”

Годинник Механікуса (MECHANIS)

Вхідний файл: MECHANIS.DAT

Вихідний файл: MECHANIS.RES

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

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

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

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

Вхідні дані:

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

Якщо шестерня А дотикається до шестерні B, то при русі ці дві шестерні обов’язково обертаються у протилежні боки.

Вихідні дані:

Перший рядок вихідного файлу має містити відповідь на запитання: „Чи працюватиме годинник?” у форматі YES або NO.

Якщо відповідь YES, то другий рядок файлу має містити послідовно номери усіх шестерень, які обертаються при роботі годинника, причому через один проміжок після кожного номеру вкажіть, у який бік обертається відповідна шестерня (CW – за годинниковою стрілкою; CCW – проти годинникової стрілки).

Якщо ж відповідь NO, то другий рядок файлу має містити через один проміжок послідовно номери усіх заблокованих шестерень (тобто шестерень, які не рухаються ЛИШЕ тому, що перша шестерня не може рухатись).



Приклади:

MECHANIS.DAT

MECHANIS.RES

7

1 2


2 4

3 4


1 3

4 7


5 4

5 6


6 7

YES

1 CCW 2 CW 3 CW 4 CCW 5 CW 6 CCW 7 CW



11

1 2


1 3

3 4


2 4

7 4


7 5

4 5


6 11

8 9


9 10

10 8


NO

1 2 3 4 5 7




Збирання мита (TALLAGE)

Вхідний файл: TALLAGE.DAT

Вихідний файл: TALLAGE.RES

Король країни Аріїв завоював N міст на території сусідніх держав.

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

Вхідні дані:

Перший рядок вхідного файлу містить натуральне число N – кількість міст у країні, а також цілі числа X та Y – координати столиці.

Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст.

Вихідні дані:

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

Наступні рядки мають містити у довільному порядку список побудованих доріг у форматі:

<номер міста> => <номер міста>

При цьому столицю позначте номером 0.

Якщо відповідей декілька, виведіть одну довільну з них.

Приклади:


TALLAGE.DAT

TALLAGE.RES

6 0 0

1 1


-1 1

0 2


1 -1

-1 -1


0 -2

8.485

2 3


3 1

1 0


0 4

4 6


6 5


Сірники (MATCHES)

Вхідний файл: MATCHES.DAT

Вихідний файл: MATCHES.RES

Втомившись від нудьги та самотності один математик вирішив пограти сам із собою у гру.

На листок у клітинку він висипав вміст кількох коробок сірників. Математик поламав їх і склав із них чудернацьку фігуру, причому:

сірники, з яких вона складалася, мали різну довжину;

сірники сполучали деякі вузли клітинок листка;

сірники могли дотикатися між собою лише кінцями.

Після цього почалася гра.

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

Визначте, скільки сірників залишиться на столі, коли гра припиниться.

Вхідні дані:

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

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

Вихідні дані:

Єдиний рядок вихідного файлу має містити кількість сірників, що залишилися наприкінці гри.



Приклади:

MATCHES.DAT

MATCHES.RES

8

0 2


1 1

1 -1


0 0

0 -1


1 -2

-1 -2


6


Самогон (HOMEBREW)

Вхідний файл: HOMEBREW.DAT

Вихідний файл: HOMEBREW.RES

Герої відомого за радянських часів (і актуального в наш час) фільму „Самогонники”, Георгій Віцин, Моргунов та Юрій Нікулін, змайстрували самогонний апарат.

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

Хлопці вирішили „гнати” самогон якнайбільшим напором, проте у трубок апарату обмежена пропускна спроможність.

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

Вхідні дані:

Перший рядок вхідного файлу містить натуральне число N – кількість точок, у яких сполучаються трубки самогонного апарату. Пронумеруємо усі такі точки натуральними числами від 1 до N. Позначимо точку прикріплення до скороварки числом 0, а точку витоку до каструлі – числом N+1.

Кожен наступний рядок містить три числа – номери точок, між якими прокладено трубку, а також пропускну спроможність цієї трубки.

Вихідні дані:

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



Приклади:

HOMEBREW.DAT

HOMEBREW.RES

4

0 1 4


0 2 4

1 3 1


1 4 2

2 3 1


2 4 3

3 5 3


3 4 1

4 5 3


6


Поділіться з Вашими друзьями:


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка