Вступна робота



Скачати 50.29 Kb.
Дата конвертації30.12.2016
Розмір50.29 Kb.
ВОЛИНСЬКИЙ ІНСТИТУТ ПІСЛЯДИПЛОМНОЇ ПЕДАГОГІЧНОЇ ОСВІТИ

ЛАБОРАТОРІЯ ІНФОРМАТИКИ

Школа олімпійського резерву з інформатики

2006-2007 н.р.

Вступна робота


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

У всіх задачах вхідні дані повинні прочитуватися із стандартного потоку введення (з клавіатури), вихідні дані повинні виводитися в стандартний потік виведення (на екран). Дані повинні вводитися і виводитися строго у форматі, вказаному в умові задачі, ніяких додаткових повідомлень виводити не потрібно. Обмеження по пам'яті у всіх задачах — 64 Мб, обмеження за часом роботи на одному тесту – 2 секунди (постарайтеся, щоб ваші розв’язок були по можливості оптимальні).

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

Напишіть фрагмент програми, який для двох змінних n і m (відомо, що значення обох змінних — натуральні числа, самі змінні — цілого типу) виводить на екран 1, якщо N<=M, а якщо ж N>M, то на екран виводиться будь-яке число, відмінне від 1. При цьому заборонено користуватися умовним оператором.


Задача 2 (10 балів)

Задача: з рядка видалити всі символи пропуск. Розв’язок

procedure delspace(var s:string);

var i:integer;

begin

for i:=1 to length(s) do



if s[i]=' ' then delete(s,i,1);

end;


Придумайте приклад, на якому дана процедура стиратиме не всі пропуски. Поясніть, чому так відбувається. Наведіть правильний розв’язок поставленої задачі.
Задача 3 (15 балів)

В мішку у Діда Морозу лежать цукерки трьох видів: шоколадні, іриски і льодяники. Дід Мороз знає, що якщо вийняти будь-які 100 цукерок з мішка, то серед них обов'язково знайдуться цукерки всіх трьох видів. Яка найбільша кількість цукерок може бути в мішку у Діда Морозу?



Задача 4(15 балів)

Дано число N. Знайти число з діапазону від 1 до N з максимальною сумою дільників (включаючи непрості дільники, 1 і саме число). Якщо таких чисел декілька, то виведіть будь-яке з них.



Вхідні дані:

На вхід програмі подається одне натуральне число N, що не перевищує 2000.



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

Ваша програма повинна вивести число, що є відповіддю задачі.



Приклад введення

Приклад виведення

5

4


Задача 5 (20 балів)

Чи є число 23021377-1 простим? Крім відповіді, опишіть спосіб, яким ви цю відповідь отримали.



Задача 6 (25 балів)

Дана послідовність з N натуральних чисел. Потрібен в цій послідовності знайти три числа X, У, Z (не обов'язково різних — див. приклади), що X*Y=Z.



Вхідні дані:

Спочатку вводиться число N (1?N?100) — кількість елементів послідовності. Далі йде N натуральних чисел, кожне з яких не перевищує 10000.



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

Виведіть три шукані числа (спочатку X, потім У, потім Z). Якщо таких чисел немає, виведіть три рази (через пропуск) число 0. Якщо варіантів відповіді дещо, виведіть будь-який з них.



Приклад введення

Приклад виведення

5

2 4 8 1 3



2 4 8

2

1 2


1 2 2


Задача 7 (25 балів)

Вимагається порахувати (A^B) mod С, де ^ — піднесення до степеня, а mod — знаходження остачі від ділення першого числа на друге.



Вхідні дані:

На вхід програмі подаються числа А, B, С (1А2*109, 1B2*109, 1З30000).



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

Ваша програма повинна вивести число, що є відповіддю задачі.



Приклад введення

Приклад виведення

2 2 3

1

20 20 4

0

2005 2007 2006

2005


Задача 8 (40 балів) «Dobriy Vitya Strikes Back»

На літніх зборах 2006 року викладачі готові прочитати N різних лекцій. Але, на жаль, збори проходитимуть тільки в протягом M днів. З гуманістичних міркувань в день не можна прочитати більше однієї лекції. Викладачі приїжджають і виїжджають по ходу зборів, таким чином, деякі лекції не можуть бути прочитані в певні дні. Щоб якнайкраще підготувати збірну команду до виступу на міжнародній олімпіаді, було вирішено прочитати максимальну кількість лекцій.

Добрий Вітя передав учасникам зборів план, які лекції в який день можуть бути прочитаний. Учасники не знають, який з можливих планів зборів буде вибраний. Але вони зацікавилися, які лекції обов'язково будуть прочитані.

Вхідні дані: На вхід подаються спочатку два числа — N і M (1<=N<=200, 1<=M<=200). Наступні N рядків містять описи лекцій, по одній на рядку. Для кожної лекції, вказуються номери днів, в які може бути прочитаний дана лекція. Числа в рядку розділяються одним або декількома пропусками. Дні і лекції нумеруються з одиниці.

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

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


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

4 3

2

1 3



2

1 2 3


2 4



Задача 9 (50 балів)

В державі є N (0 компаній (компанії пронумеровані числами від 1 до K (0

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

Вхідні дані: Спочатку задаються числа N, К, M, далі задається M четвірок чисел Xi, Yi, Ci, Ti, де Ci і Ti – відповідно вартість проїзду (0K), якій належить автотраса, провідна від міста Xi в місто Yi. Далі йдуть числа А і B – номери початкового і кінцевого міст відповідно. Всі дороги односторонні, тобто наявність дороги з міста X в місто У не означає наявності дороги у зворотному напрямі, а якщо дорога з У в X існує, то вона не зобов'язана належати тій же компанії, що і дорога з X в У. Між будь-якими двома містами в одному напрямі може бути не більше однієї автотраси.

Вихідні дані: Ваша програма повинна вивести одне число — мінімальну суму грошей, які потрібні, щоб проїхати з міста А в B, або число –1 (мінус один), якщо проїхати неможливо.


Приклад введення

Приклад виведення

5 3 6

1 2 4 1


2 1 3 2

2 3 3 3


3 4 3 2

3 5 5 1


4 5 1 2

1 5


12

3 2 3

2 3 3 2


3 1 2 2

1 2 2 1


2 1

-1



База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

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