Сайт підготовки до олімпіади з інформатики

Задачі (20.05.2011)

Завдання 1

Є 10 мішків з монетами. Відомо, що в одному з мішків всі монети фальшиві і

кожна з них на 1 грам легша від нефальшивої. За одне зважування на терезах з

гирями визначити, в якому з мішків знаходяться фальшиві монети.

Завдання 2

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

подорожній долає міст за різний час: першому потрібна 1 хвилина, другому – 2 хвилини, третьому – 5 хвилин, а четвертому – 10 хвилин. Якщо подорожні йдуть мостом вдвох, то вони пересуваються з швидкістю найповільнішого з них (наприклад, якщо йтимуть перший і четвертий, то вони здолають міст за 10 хвилин)

Завдання 3

Є 12 монет, серед яких одна фальшива. За 3 зважування на терезах без гирок визначити фальшиву монету і відповісти на запитання: «Фальшива монета легша чи важча?» Скласти схему алгоритму, визначити його тип.

Рішення
Ділим монетки на 3 купки по 4 монети
1 2 3 4 5 6 7 8 9 10 11 12
1. Перше зважування 1 2 3 4 і 5 6 7 8
(один варіант)
Якшо 1 2 3 4 = 5 6 7 8 Переходим на крок 2
Якшо 1 2 3 4 > 5 6 7 8 (якшо менше теж підходить але порядок ваги є важливий) переходим на крок 4
2. Друге зважування
(один варіант)
7 8 = 11 12 тобто фальшива є серед 9 і 10, бо 7 і 8 - справжні
7 8 11 12 то фальшива є серед 11 і 12
Переходим на крок 3
3. Третє зважування
(один варіант)
8 = 9 тоді фальшива 9
(8 = 11 тоді фальшива 12)
(другий варіант)
8 10 тоді фальшива 10
(8 11 тоді фальшива 11)
Переходим на крок 12

4. (другий варіант)
1 2 3 4 > 5 6 7 8 (якшо менше теж підходить але порядок ваги є важливий)
Переходим на крок 5
5. Друге зважування
Відкладєм 1 2 3
важим
(Варіант 1)
6. 4 5 6 7 > 8 9 10 11 оскільки монетки 1 2 3 не впливають на зміну ваги - вони справжні, І фальшива є
або 7 або 8. Переходи на крок 9
(Варіант 2)
7. 4 5 6 7 < 8 9 10 11 фальшива монета є серед 4 5 6 і фальшива монета є лекша Переходи на крок 10
(Варіант 3)
8. 4 5 6 7 = 8 9 10 11 фальшива монетка є серед 1 2 3 і фальшива монета є важча Переходи на крок 11
Важим
9. 7 і 12 якшо рівні то фальшива 8, якшо не рівні - фальшива 7-ма
10. 4 і 5 якшо рівні то фальшива 6, якшо 4 лекше за 5 то фальшива 4, якшо 4 важча за 5 то фальшива є 5
11. 1 і 2 якшо рівні то фальшива 3, якшо 1 важче за 2 то фальшива 1, якшо 1 лекша за 2 то вальшиває є 2
12. Кінець

Завдання 4

Дано послідовність з N чисел, котра містить різні числа від 0 до N. Визначити, якого числа не існує в даній послідовності.

Завдання 5

В таблиці а[1..100)]всі елементи рівні 2,3,4 або 5. Написати програму, яка заміняє 2 на 5, 3 на 4, 4 на 3, 5 на 2.

Завдання 6

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

Завдання 7 DOMINO

Написати програму, яка буде підраховувати кількість варіантів покриття прямокутника 2хN прямокутниками 2х1. Покриття, які перетворюються одне в одне симетріями рахувати різними.

Вхідні дані. Вхідний файл DOMINO.DAT містить число N (0 < N < 65536).

Вихідні дані. Вихідний файл DOMINO.SOL повинен містити одне число: кількість варіантів.

Завдання 8

За квитками на прем'єру нового мюзиклу вишикувалася черга з N людей, кожний з яких хоче купити 1 квиток. На всю чергу працювала тільки одна каса, тому продаж квитків йшов дуже повільно, приводячи людей черги у відчай. Найкмітливіші швидко відмітили, що, як правило, декілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються поодинці. Тому вони запропонували декільком людям, які стоять підряд віддавати гроші першому з них, щоб він купив квитки на всіх.

Проте для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 підряд вартих людини.

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

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

Формат вхідних даних

У вхідному файлі записано спочатку число N — кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел Ai_, Bi_, Ci_. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

Формат вихідних даних

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

Приклади

Завдання 9

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

Необхідно по заданій послідовності координат руху обчислити суму штрафу.

Вхідні дані: В першому рядку вхідного файлу VIOLATION.DAT записано N - кількість зафіксованих координат руху деякого автомобіля та М - величина штрафу, в наступних рядках координати автомобіля в процесі руху - (х_i, у_i), і=1,2,...,М, де (х₁, у₁) - точка початку руху, (х_N,у_N) - остання точка маршруту автомобіля.

Всі числа цілі та знаходяться в межах від -1000 до 1000.

Вихідні дані: Єдиний рядок вихідного файлу VIOLATION.SOL має містити суму штрафу.

Приклад:

Завдання 10

Міжнародна конференція

Вас найняли для того, щоб визначити мiсця дипломатiв за столом обговорень мiжнародної конференцiї. На конференцiю запрошенi по одному дипломату з N рiзних країн свiту. Кожен дипломат знає вiд однiєї до М мов. Дипломати, якi не знають спiльної мови, не можуть розмовляти один з одним. До того ж, деякi країни проголосили, що не будуть пiдтримувати дипломатичних стосункiв з деякими iншими, тобто представники цих країн не будуть розмовляти один з одним. Ваше завдання полягає в розробцi програми DIPLOMAT.*, що визначає мiсця за столом для дипломатiв таким чином, щоб кожен мiг розмовляти з обома своїми сусiдами, якi сидять лiворуч та праворуч вiд нього.

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

Вхiднi данi:

В першому рядку текстового файлу DIPLOMAT.DAT – число N. Далi – N рядкiв, по одному рядку на дипломата. Кожен рядок – послiдовнiсть слiв. Сусiднi слова вiдокремленi пропуском. Кожне слово – це послiдовнiсть великих латинських лiтер. Перше слово – код країни – складається з 3 лiтер. Друге слово має довжину вiд 1 до 5 лiтер i представляє перелiк мов, на яких може спiлкуватись дипломат. Кожна мова позначена однiєю лiтерою. Далi iде список з не бiльш як N трилiтерних слiв – кодiв країн, з якими уряд дипломата пiдтримує стосунки.

Вихiднi данi:

До файлу DIPLOMAT.SOL треба вивести список дипломатiв в порядку розмiщення за столом (по одному дипломату в рядку). Кожен рядок складається з 3 слiв: перше – код мови, якою дипломат може спiлкуватись з сусiдом лiворуч, друге – код країни дипломата, третє – код мови для спiлкування з сусiдом праворуч. Можливе iснування декiлькох розв'язкiв. Вам потрiбно знайти один. Якщо розв'язку не iснує, Ваша програма повинна видати таке повiдомлення: NO SOLUTION EXISTS.

Завдання 11 GoTo.

Учні, недавно що почали програмувати, вживають дуже багато операторів GOTO, що є майже неприпустимим для структурованої програми. Допоможіть викладачу інформатики написати програму, яка оцінюватиме ступінь структурованості відладженої програми школяра на мові Pascal, спершу просто підраховувавши кількість операторів GOTO в ній.

В синтаксично вірній програмі ключове слово оператора переходу GOTO може стояти або на початку рядка або після пропуску або після одного з символів — ‘;’, ‘:’, ‘}’, а після нього може стояти або пропуск або переклад рядка або символ ‘{‘ (табуляцію як роздільник розглядати не будемо).

Нагадаємо, що окрім позначення дійсно оператора переходу, слово GOTO може зустрічатися в тексті програми в рядкових константах, укладених в апострофи, або в коментарях, причому для простоти вважатимемо, що коментар завжди починається з символу ‘{‘, а закінчується першим що зустрівся після цього символом ‘}’, при цьому символ ‘{‘ повинен знаходитися не усередині рядкової константи. В цих випадках слово GOTO підраховувати не потрібно. Рядкові і прописні букви в Pascal не помітні.

У вхідному файлі goto.in знаходиться текст програми без синтаксичних помилок на мові Pascal. Розмір програми не перевершує 64К. У вихідному файлі goto.out повинне виявитися одне число – кількість операторів GOTO в цій програмі.

Приклад вхідного файлу:

label 1,2;

var I:byte;

begin

1: I:=I+1;

if I>10 then goto 2 else

writeln(¢ goto ¢); GoTo 1;

2: if I<10 then goto 1 {else { goto 2;}

end.

Вихідний файл для наведеного приклад

3

Завдання 12 «Циліндр»

Із аркушу паперу ножицями Ви можете вирізати дві поверхні, з яких можна скласти циліндр наступним чином:

1. Розрізати папір горизонтально (паралельно короткій стороні), отримавши дві прямокутні частини.

2. З першої частини вирізати круг максимального радіуса. Він буде лежати в основі циліндра.

3. Скрутіть другу прямокутну частину у трубочку так щоб її периметр дорівнював довжині кола, що обмежує круг. Прикріпіть трубочку до основи циліндра. Відмітимо, що трубочка може містити накриваючу частину паперу, так як її радіус підганяли до довжини радіуса основи циліндра.

За заданими розмірами паперу необхідно побудувати подібним чином циліндр максимального об'єму.

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

Вхідні дані

Вхідні дані містять декілька тестів. Кожен тест містить два числа w і h (1 ≤ w ≤ h ≤ 100), які позначають ширину та висоту аркуша паперу. Останні тест містить два нулі і не опрацьовується.

Вихідні дані

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

Приклад

10 10

10 50

10 30

0 0

54.247

785.398

412.095