Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"
ІНФОРМАТИКА
     
  
29 апреля - 4 мая
2002 года

Завдання з інформатики

Задача TOWER. 

В комп'ютерній грі "Страшна помста 2" головному герою -безстрашному лицарю - потрібно піднятися з 1-го на N-й поверх високої вежі. Вежа має М драбин, причому k-а драбина веде з a[k]-го на b[k]-ий поверх (a[k]<b[k]). Герой витрачає 3 секунди на підйом по драбині на один поверх і 5*k+7 секунд на перебіжку від однієї драбини до іншої по k-ому поверху. На k-ому поверсі знаходяться k чаклунів, кожного з яких лицар вбиває за 5 секунд. За який найменьший час T герой зможе піднятися з першого на N-ий поверх?
Врахуйте, що лицар може залишити k-у драбину або стати на неї на будь-якому поверсі між a[k] і b[k] включно. Герой не витрачає часу на першому та на N-ому поверхах.
Ви маєте написати програму TOWER, яка читає вхідні данї з файла TOWER.DAT і записує відповідь у файл TOWER.SOL.

Формат файла TOWER.DAT:
N M
a[1] b[1]
a[2] b[2]
...
a[M] b[M]

Формат файла TOWER.SOL:
T

Обмежения:
1<N<1000000;
1<M<5000;
драбини розміщені так, що завжди можливо потрапити на N-ий поверх.

Приклад:
TOWER.DAT:
10 5
1 3
6 9
4 8
3 8
5 10
TOWER.SOL:
81

В цьому прикладі герою потрібно дістатися на 10-ий поверх вежі. В цій вежі є 5 драбин: перша простягається з 1-го по 3-ій поверх, друга - с 6-го по 9-ий і т.д. Спочатку лицар піднімається 1-ою драбиною на 3-ій поверх, затративши 3*2=6 секунд. Далі він перебирається на 4-у , вбиваючи 3-ох чаклунів за 5*3+7=22 секунди, і поднимається на 5-ий поверх за 3*2=6 секунд. На 5-ому поверсі герой переходить на 5-у драбину за 5*5+7=32 секунди, і, врешті-решт, досягає 10-го поверху за 3*5=15 секунд. Перемога! Затрачено часу: 6+22+6+32+15=81 секунда.

Задача STEPS. 

В комп'ютерній грі "Страшна помста 2" головному герою -безстрашному лицарю - потрібно спуститися по хиткій драбині, що має N сходинок, до темного підземелля. Герой може спуститися, ступаючи на кожну сходинку, перескакувати через одну або дві сходинки. Але злі чаклуни підпиляли деякі сходинки, тому на них ставати небезпечно. Скількома різними способами лицар може потрапити з першої сходинки на N-у?
Ви повинні написати програму STEPS, яка читає вхідні дані з файла STEPS.DAT 
та записує відповідь в файл STEPS.SOL
Формат файла STEPS.DAT:
N
c[1]
c[2]
...
c[N]

Формат файла STEPS.SOL:
X


Тут N - кількість сходинок, c[k]=1, якщо k-та сходинка неушкоджена, та c[k]=0, якщо k-а сходинка підпиляна.
Обмеження:
1<N<40;
c[1]=1; c[N]=1;
вхідні дані такі, що герой завжди може потрапити з першої на N-у сходинку хоча б одним способом.
Приклад:
STEPS.DAT:
6
1
0
1
1
0
1
STEPS.SOL:
3


В цьому прикладі драбина складається з 6-и сходинок, причому друга та п'ята сходинка підпиляні. 
Потрапити з 1-ї сходинки на 6-у можливо 3-ма способами. Перший спосіб: стрибок через одну сходинку, крок на наступну та стрибок через сходинку. Другий спосіб: стрибок через сходинку та стрибок через 2 сходинки. Третій спосіб: стрибок через 2 сходинки і стрибок через 1 сходинку.

Задача WALLS. 

В комп'ютерній грі "Страшна помста 2" головного героя -безстрашного лицаря - схопили злі та підступні чаклуни і сховали в темному підземеллі. Але, на щастя, у славного лицаря знайшлась карта підземелля та кілька ящиків динаміту. Кожний ящик динаміту може зруйнувати одну стіну. Яку наименшу кількість ящиків динаміту повинен витратити герой, щоб вибратися з підземелля?
Карта лабиринту - це аркуш паперу в клітинку з M рядків та N стовпців. Клітка може бути вільною або зайнятою стіною. 
Герой може рухатися вільними клітинками по горизонталі або вертикалі. Ящик динаміту руйнує стіну в одній клітинці. 
Щоб вибратися з підземелля, герою достатньо досягнути границі карти.
Ви повинні написати програму WALLS, яка читає вхідні дані з файла WALLS.DAT та записує відповідь в файл WALLS.SOL.

Формат файла WALLS.DAT:
M N
p[1,1] p[1,2] ј p[1,N]
p[2,1] p[2,2] ј p[2,N]
ј
p[M,1] p[M,2] ј p[M,N]


Формат файла WALLS.SOL:

X

Тут M та N - число рядків та стовпців на карті підземелля. p[i,j]=0, якщо в цьому місці підземлля відсутня стіна, p[i,j]=1 - якщо стіна є, p[i,j]=2 позначає початкове положення героя, X - мінімальна кількість ящиків динаміту, яку потрібно витратити, щоб вибратися із підземелля.

Обмеження:
2<M<100;
2<N<100.

Приклад:
WALLS.DAT:
6 7
1 1 1 1 1 1 1
1 0 1 1 1 0 1
1 1 0 2 1 1 1
1 0 1 0 1 0 1
1 0 0 1 1 0 1
1 1 1 1 1 1 1
WALLS.SOL:
2

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

Пам'ятка учасникам.

Розв'язання задач - файли з текстами програм, мають бути записані на диск під іменами tower.pas, steps.pas, walls.pas (або tower.c, steps.c, walls.c). Програми повинні читати дані з текстових файлів с розширенням dat і записувати результати до файлів з розширенням sol.
Програма не повинна нічого виводити на екран і не повинна очікувати вводу з клавіатури!
Програми перевіряються шляхом виконання набору тестів.
В текст програм зміни не вносятся, і сам він не оціиюється!



 

© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"