asyan.org
добавить свой файл
1 2 3

Олімпіада школярів з програмування

  1. Автобусна екскурсія

Ім'я вхідного файлу:

а.in

Ім'я вихідного файлу:

а.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

Оргкомітет Московської міської олімпіади вирішив організувати оглядову екскурсію по Москві для учасників олімпіади. Для цього був замовлений двоповерховий автобус (учасників олімпіади достатні багато і в звичайний вони не уміщаються) заввишки 437 сантиметрів. На екскурсійному маршруті зустрічаються N мостів. Жюрі і оргкомітет олімпіади дуже стурбовані тим, що високий двоповерховий автобус може не проїхати під одним з них. Їм вдалося з'ясувати точну висоту кожного з мостів. Автобус може проїхати під мостом тоді і тільки тоді, коли висота моста перевершує висоту автобуса. Допоможіть організаторам дізнатися, чи закінчиться екскурсія благополучно, а якщо немає, то встановити, де відбудеться аварія.

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

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

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

У єдиний рядок вихідного файлу потрібно вивести фразу "No crash", якщо екскурсія закінчиться благополучно. Якщо ж відбудеться аварія, то потрібно вивести повідомлення "Crash К", де К - номер моста, де відбудеться аварія. Фрази виводити без лапок рівно з одним пропуском усередині.

Приклади

а.in

а.out

1

763

No crash

3

763 245 113

Crash 2

1

437

Crash 1

  1. Сапер

Ім'я вхідного файлу:

b.in

Ім'я вихідного файлу:

b.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

Хлопчикові Васе дуже подобається відома гра "Сапер" ("Minesweeper").

У "Сапер" грає одна людина. Гра йде на клітчастому полі (далі називатимемо його картою) N*M (N рядків, M стовпців). У K клітках поля коштують міни, в решті кліток записано або число від 1 до 8 — кількість мін в сусідніх клітках, або нічого не написано, якщо в сусідніх клітках мін немає. Клітки є сусідніми, якщо вони мають хоч би одну загальну крапку, в одній клітці не може стояти більш за одну міну. Спочатку всі клітки поля закриті. Гравець за один хід може відкрити яку-небудь клітку. Якщо у відкритій ним клітці опиняється міна — він програє, інакше гравцеві показується число, яке стоїть в цій клітці, і гра продовжується. Мета гри — відкрити всі клітки, в яких немає мин.

У Васи на комп'ютері є ця гра, але йому здається, що всі карти, які в ній є, непривабливі і нецікаві. Тому він вирішив намалювати свої. Проте фантазія у нього багата, а часу мало, і він хоче встигнути намалювати якомога більше карт. Тому він просто вибирає N, M і K і розставляє міни на полі, після чого решта всіх кліток може бути однозначно визначені. Проте на визначення решти кліток він не хоче витрачати свій дорогоцінний час. Допоможіть йому!

По заданих N, M, K і координатам мін відновите повну карту.

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

У першому рядку вхідного файлу містяться числа N, M і K (1N200, 1M200, 0KN*M). Далі йдуть K рядків, в кожній з яких міститься по два числа, задаючих координати мин. Перше число в кожному рядку задає номер рядка клітки, де знаходиться міна, друге число — номер стовпця. Ліва верхня клітка поля має координати (1,1), права нижняя — координати (N,M).

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

Вихідний файл повинен містити N рядків по M символів — відповідні рядки карти. j-й символ i-й рядка повинен містити символ ‘ *‘ (зірочка) якщо в клітці (i,j) стоїть міна, цифру від 1 до 8, якщо в цій клітці стоїть відповідне число, або ‘.‘ (крапка), якщо клітка (i,j) порожня.

Приклад

b.in

b.out

10 9 23

1 8

2 3

3 2

3 3

4 3

5 7

6 7

7 1

7 2

7 3

7 4

7 5

7 6

7 7

7 8

8 1

8 3

8 5

8 7

9 3

9 5

9 6

9 7

.111..1*1

13*2..111

1**3.....

13*2.111.

.111.2*2.

233335*41

********1

*6*7*8*41

13*4***2.

.1122321.

  1. Робот K-79

Ім'я вхідного файлу:

з.in

Ім'я вихідного файлу:

з.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

Петя написав програму руху робота К-79. Програма складається з наступних команд:

  • S — зробити крок вперед

  • L — обернутися на 90 вліво

  • R — обернутися на 90 управо

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

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

У вхідному файлі записаний один рядок із заголовних латинських букв S, L, R, що описує програму для робота. Загальне число команд в програмі не перевищує 200, при цьому команд S — не більше 50.

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

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

Приклади

з.in

з.out

SSLSLSLSSRSRS

5

LSSSS

-1




  1. Багаточлен

Ім'я вхідного файлу:

d.in

Ім'я вихідного файлу:

d.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

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

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

У першому рядку вхідного файлу записаний многочлен у вигляді суми одночленів. Між одночленами знаходиться знак + або –. Перед першим одночленом може бути знак –. Одночлен записується як

[<Коеффіциент>*]x[^<Степень>]

або

<Коефіцієнт>

де <Коефіцієнт> — натуральне число, що не перевершує 100, x — символ змінної (завжди маленька латинська буква x), <Ступінь> — натуральне число, що не перевершує 4. Параметри, узяті в квадратні дужки, можуть бути опущені. У другому рядку записано одне ціле число — значення x.

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

У вихідний файл потрібно записати одне число — значення даного многочлена при даному значенні x.

Обмеження

Всі числа в початковому файлі по модулю не перевершують 100. Кількість одночленів не більше 10 (можуть бути одночлени однакового ступеня).

Приклади

d.in

d.out

8*x+5

7

61

-2+x^1-3*x^2+x^2+100*x^3-2*x

0

-2




  1. Головоломка

Ім'я вхідного файлу:

e.in

Ім'я вихідного файлу:

e.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

Петя розгадує головоломку, яка влаштована таким чином. Дана квадратна таблиця розміру N*N, в кожній клітці якої записана яка-небудь латинська буква. Крім того, даний список ключових слів. Пете потрібно, узявши чергове ключове слово, знайти його в таблиці. Тобто знайти в таблиці всі букви цього слова, причому вони повинні бути розташовані так, щоб клітка, в якій розташована кожна подальша буква слова, була сусідньою з кліткою, в якій записана попередня буква (клітки називаються сусідніми, якщо вони мають загальну сторону — тобто є сусідами по вертикалі або по горизонталі). Наприклад, на малюнку нижче показано, як може бути розташовано в таблиці слово olympiad.

P

O

L

T

E

R

W

Y

M

S

O

A

I

P

T

B

D

A

N

R

L

E

M

E

S

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

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

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

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

У першому рядку вхідного файлу записано два числа N (1Nі 10) M (0M200). Наступні N рядків по N заголовних латинських букв описують ребус. Наступні M рядків містять слова. Слова складаються тільки із заголовних латинських букв, кожне слово не довше 200 символів. Гарантується, що в таблиці можна знайти і викреслити по описаних вище правилах всі ключові слова.

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

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

Приклади

e.in

e.out

5 3

POLTE

RWYMS

OAIPT

BDANR

LEMES

OLYMPIAD

PROBLEM

TEST

ANSWER

3 2

ISQ

ABC

IQW

I

IS

ABCQQW




  1. Пошук прямокутників

Ім'я вхідного файлу:

f.in

Ім'я вихідного файлу:

f.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

16 мегабайт

На полі NXM кліток (N рядків і M стовпців) поклали K прямокутників один поверх іншого у випадковому порядку. Довжини сторін прямокутників виражаються цілим числом кліток. Прямокутники не виходять за межі поля. Межі прямокутників співпадають з межами кліток поля.

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

По вмісту таблиці потрібно визначити положення і розміри прямокутників.

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

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

У першому рядку вхідного файлу записані цілі числа N, M, K (1N200, 1M200, 1K255). Далі слідує N рядків по M чисел в кожній — вміст таблиці. Всі числа в таблиці цілі, знаходяться в діапазоні від 0 до K включно.

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

У

0

2

2

2

2

0

2

2

2

2

1

1

2

2

2

1

1

0

0

0




0

2

2

2

2

0

2

2

2

2

1

1

2

2

2

1

1

0

0

0



следующая страница >>