`Всеукраїнський центр проведення олімпіад в мережі Інтернет
  1. Завданя 4 (Real Time) туру NetOI-2008
Задача  Newhanoy 
Жюрі не сумнівається в тому, що всі фіналісти NetOI-2008  уміють розв’язувати таку задачу:

Задача про Ханойські вежі  Є три стержні A, B, C і N кілець різних діаметрів, які можна надівати на стержні. Спочатку всі кільця знаходяться на одному стержні (А) в порядку зменшення їх діаметрів (діаметр верхнього кільця 1, а нижнього - N). Необхідно за мінімальну кількість ходів перемістити всю піраміду на  стержень С, використовуючи як допоміжний  стержень B,  дотримуючись при цьому таких правил:
-        за один хід можна перемістити лише одне кільце;
-        будь-яке кільце можна надівати або на порожній стержень, або на стержень з  верхнім кільцем більшого діаметру.
Завдання полягає у визначенні послідовності переміщень кілець для перенесення їх з A на С.
 
          Але цього разу після  розв’язку задачі  кінцевий стержень стає початковим, допоміжний - кінцевим, початковий - допоміжним і  гра продовжується без перерви. Потім допоміжний стержень стане початковим, початковий - кінцевим, кінцевий - допоміжним і так далі   Від початку гри з N дисками зроблено K ходів. Визначите, скільки разів перекладався диск  з діаметром T.
 Технічні умови
Програма Newhanoy читає з клавіатури  три натуральні числа  N - кількість дисків, (1 <= N< 64), T - діаметер  потрібного диска (1<=T<=N) та  K - кількість ходів  (1<= K <263)Програма виводить на екран єдине число – шукану величину
.
 Приклад
Введення:   3 3 10                                   

Виведення: 1 


 Задача  Dinner 

Журі, працюючи над завданнями 4 туру, вирішило зробити перерву на обід. У шкільній їдальні гомін - це 1-б клас обідає. Вчителька, побачивши шановане журі за столом, почала заспокоювати своїх галасливих учнів. Природно, чує її лише той першокласник, до якого вона звертається. Заспокоївши одного, вона починає заспокоювати наступного. Цікаво, чи зможе журі хоч хвилинку поїсти в тиші, якщо всіх першокласників  N (1<N <=103), кожного i-того потрібно заспокоювати ai, хвилин, після чого   bi  хвилин він буде їсти мовчки, і якщо так,  в якому порядку потрібно їх заспокоювати.(1<= ai , bi <=106 )  
Технічні умови
Програма Dinner читає з клавіатури число N, другий рядок  введення містить N чисел ai, третій N чисел bi . Програма виводить на екран N чисел - порядок, в якому потрібно заспокоювати першокласників. Якщо це зробити неможливо, виводить -1
Приклади 

Введення

2
1 10
10 20 
Виведення
2 1 		 Введення
2
10 10
10 10
Виведення
-1
         







Задача Minodd
    
Пан Дивак вирішив поїхати до своєї сестри. Плануючи поїздку, він дізнався  про вартість проїзду в усіх автобусних рейсах їхнього району. Але пан таки був дивак,  бо вирішив, що  вартість його проїзду до сестри повинна дорівнювати непарній кількості копійок. А з другого боку, він хоче  дістатися якнайдешевше, тобто знайти найдешевший серед тих маршрутів, в яких сумарна вартість поїздки є непарною. Пересадки Дивака не лякають. Окремі частини маршруту можуть коштувати парну кількість копійок; непарною має бути сума вартостей усіх використаних рейсів.
     Рейси виконуються між N населеними пунктами, серед яких село пана Дивака позначене як №1, сестри — як №2. Для кожної пари пунктів або взагалі не існує прямого сполучення, або вартість проїзду відома й однакова в обох напрямках. Із будь-якого пункту гарантовано можна дістатися до інших, але не виключено, що всі можливі способи коштуватимуть парну кількість копійок.

Технічні умови

Програма Minodd в першому рядку читає з клавіатури числа N та M — кількість населених пунктів та кількість рейсів. Далі зчитує  M рядків  по три натуральні числа i, j та cij — номери пунктів, які з’єднує рейс, та вартість проїзду. Серед цих M рядків жодного разу не повторюється одна й та сама пара пунктів (у т. ч., коли ті самі два пункти переставлені місцями). Ніякий рейс не з’єднує пункт сам із собою.   (4≤N,M ≤ 500,  1≤c≤1000).             Програма виводить на екран два числа через пропуск - мінімальну можливу сумарну вартість проїзду серед усіх «непарних» та мінімальну можливу вартість проїзду серед усіх можливих («парних» чи «непарних»). Якщо не існує жодного способу дістатися за «непарну» вартість, перше  число буде -1.

Приклад
Введення
4 5 
1 2 202
1 3 202
1 4 202
2 4 202
3 4 101
 Виведення
505 202   

 Задача  Triangles
 
У Країні Правильних Трикутників  (КПТ) міста розташовано у вузлах нескінченної сітки  доріг, що показана на малюнку. Довжина дороги між найближчими містами складає 1 УК (умовний кілометр), тобто кожне місто з'єднано дорогами з 6 іншими містами. Міста задаються своїми координатами, столиця країни – початок координат. Король КПТ планує відвідати деяке місто.
Звичайно, маршрут повинен починатись у столиці. Одначе Його Величності хочеться проїжджати тільки дорогами і тільки так, щоб кожне наступне місто знаходилося строго ближче до мети (в геометричному сенсі, тобто по прямій), ніж будь-яке раніше відвідане, включаючи столицю.   Щоб підрахувати кілкість різних маршрутів короля, радники Його Величності звернулись до Вас.
Допоможіть їм.


Технічні умови 
Програма Triangles читає з клавіатури через пропуск координати міста x,y – цілі числа, що не перевищують 200 за
абсолютною величиною.  Програма виводить на екран шукану кількість маршрутів по модулю 1000000007.

 Приклад
Введення
2 -2
Виведення
5 

Задача Maxsum  
         
Журі думає, що вам доводилося розв’язувати таку задачу:
«Є  прямокутна таблиця розміром M рядків на N стовпців. У кожній клітинці записано ціле число. По ній потрібно пройти згори  вниз, починаючи з якої-небудь клітинки  верхнього рядка, далі кожного разу переходячи в одну з «нижньо-сусідніх» клітинок  (іншими словами, з клітинки з номером (i, j) можна перейти або на  (i+1, j-1), або на  (i+1, j), або на  (i+1, j+1); в разі j=N можливі лише 1-й і 2-й з трьох перерахованих варіантів, в разі j=1 - лише 2-й і 3-й) і закінчити маршрут в якій-небудь клітинці нижнього рядка.
     Напишіть програму, яка знаходитиме максимально можливу суму значень пройдених клітинок серед усіх допустимих шляхів»
     Розв’яжіть   дану задачу при додатковому обмеженні: допускаються лише шляхи, які проходять (хоча б по одному
разу) через всі стовпчики.
 Технічні умови
Программа Maxsum читає з клавіатури M і N -  кількість рядків і кількість стовпців (2<= M<= 200,  2<= N<= 40,  M>=N), далі в кожному з подальших M рядків зчитується  рівно по N розділених пропусками цілих чисел (кожне не перевищує по модулю 1000000) - значення клітинок таблиці. Програма виводить на екран єдине число-  шукану величину.
Приклад 
Введення
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Виведення
28  
Завдання підготували Г.Кравець, Г.Непомнящий, І.Порубльов, Ю.Пасіхов

© LIKT 1998-2024