`Всеукраїнський центр проведення олімпіад в мережі Інтернет
  1. Traveller

Міністерство освіти і науки України
Управління освіти і науки Вінницької обласної державної адміністрації
Вінницький обласний інститут післядипломної освіти педагогічних працівників.
Завдання III етапу XXIV Всеукраїнської олімпіади з інформатики 2010-2011 н. р.
 

Задача Traveller

На території країни Координатії, що, само собою, знаходиться на координатній площині, протікає N річок .
Всі річки протікають у напрямку, який строго паралельний осі абсцис Ox так, що їх правий берег задається прямою y = ai, а лівий – прямою y = bi, де ai, bi – задані цілі числа (ai < bi).
Зрозуміло, що жодна з річок не може протікати там, де протікає інша, тому ніякі два відрізки [ ai; bi] не перетинаються.
Кожна з річок має по одному мосту. Всі мости розміщені строго перпендикулярно до річок (тобто паралельно осі Oy).
Таким чином міст через i -ту річку з’єднує точки (ci; ai) і (ci ; bi), де сі – задане ціле число.

Мандрівнику необхідно потрапити з міста А, що має координати (xA ; уA), в місто B з координатами (xB ; yB).
Зрозуміло, що міста лежать на суші. Знайдіть найкоротшу відстань, яку треба пройти мандрівнику, що б потрапити з A в B .
Річки він переходить, звичайно, тільки по мостах.

Технічні умови. Програма Traveller читає з клавіатури число річок N <=100 , а далі N трійок цілих чисел аi, bi, ci (по модулю не більші 106), далі чотири цілих числа xA, уA, xB, yB (теж по модулю не більші 106). Всі числа розділені пропусками. Програма виводить на екран без округлення єдине дійсне число – шукану величину.

Приклади

Введення 3 1 2 10 6 10 5 -5 -2 1 7 12 2 -10

Виведення 3.1817403856E+01

Введення 1 3 7 10 6 3 4 7

Виведення 1.4000000000E+01


Задача Prime 3

Назвемо число трипростим, якщо з будь-яких трьох його цифр, що йдуть підряд, можна скласти просте число.
Трипросте число може починатись з одного або двох нулів. Наприклад, 302 і 700 трипрості, а 212 – ні.
Числа 0 та 1 не прості. Знайдіть кількість трипростих чисел заданої довжини n.

Технічні умови. Програма читає з клавіатури єдине число n (3<= n <=1000) і виводить на екран остачу від ділення кількості трипростих чисел на 1000000009.

Приклад

Введення

3

Виведення

459

Задача Noleft
Лабіринт являє собою прямокутник m*n клітинок, в якому деякі клітинки замуровані. В одній з незамурованих клітинок знаходиться сало, а в іншій, також незамурованій – кульгавий пацюк. За один хід пацюк може перейти у сусідню клітинку, але він не може повертати ліворуч (розвертатись може). Наприклад, якщо пацюк пройшов з клітинки (3,1) на (3,2), то далі він може піти у клітинки (3,3), (4,2) або (3,1) (див. малюнок ). Звичайно, пацюк не може заходити до замурованої клітинки. За скільки ходів пацюк зможе з’їсти сало?


  1 2 3 4 5 6 y
1   r   f      
2              
3              
4              
5              
x              


Технічні умови. Програма читає з клавіатури розміри лабіринту m та n (2<=m , n<=100) , далі координати пацюка xr , yr та сала xf ,yf (1<=xr , xf <= m , 1<= yr , yf <= n ), далі кількість замурованих клітинок k , далі k пар чисел xk , yk – їх координати. Клітинки не повторюються. Вс і числа вводяться в один рядок через пропуск. Програма виводить на екран шукану кількість ходів пацюка. Якщо пацюк не з’їсть сало, необхідно вивести –1.

Приклад

Введення

5 6 1 2 1 4 3 1 3 2 3 4 4

Виведення

10

Увага!

Додаткова інформація з моменту початку олімпіади доступна на сайті olymp.vinnica.ua в розділі “Третій (обласний) етап Всеукраїнської олімпіади з інформатики (Вінницька область 2010-2011 н.р.»

© LIKT 1998-2024