Завдання ІІ етапу Всеукраїнської учнівської олімпіади з інформатики

2023 р

1. Підмасив цілих чисел (5 балів).

Дано масив A послідовних натуральних чисел завдовжки N. Микола хоче перевірити, чи існує такий підмасив цього масиву, який містить М чисел (M £ N), і при цьому всі числа цього підмасиву різні.

Програма отримує на вході число N — довжина масиву; перший елемент масиву A; число М; перший елемент підмасиву завдовжки М і  виводить YES, якщо такий підмасив існує, або NO, якщо він не існує.

Приклад:

Вхід:

100

1

20

7

Вихід: YES

 Тест:

Вхід:

100

5

30

80

Вихід: NO

2. Балансування дужок (5 балів).

Напишіть програму, яка перевіряє, чи правильно розставлені дужки у заданому рядку. Рядок може містити круглі (), квадратні [] та фігурні {} дужки. Програма отримує на вході послідовність дужок і виводить — TRUE, якщо дужки розставлені правильно, і FALSE — якщо неправильно.

 Приклад:

Вхід: {[()]}

Вихід: TRUE

 Тест:

Вхід: {[()]}

Вихід: TRUE

Вхід: {[(])}

Вихід: FALSE

3. Криптографія (10 балів).

Шифр Цезаря полягає в заміні кожного символу вхідного рядка на символ, що знаходиться на кілька позицій ліворуч або праворуч його в алфавіті. Напишіть програму, яка шифрує текст шифром Цезаря. Використовуваний алфавіт - пропуск і малі літери англійського алфавіту. На першому рядку вказується зміщення шифрування: ціле число. Додатне число відповідає зміщенню вправо. На другому рядку вказується непорожній рядок-фраза для шифрування. Результатом роботи програми має бути записана зашифрована послідовність.

 Приклад:

Вхід:

3

i am caesar

Вихід: lcdpcfdhvdu

Тести:

Вхід:

3

i am caesar

Вихід: lcdpcfdhvdu

Вхід:

26

abc

Вихід: abc

Вхід:

5

олімпіада

Вихід: gdeehesws

Вхід:

3

привіт

Вихід: fgysci

4. Пошук прямої, яка проходить через вершини (10 балів).

Дано N вершин, кожна з яких має цілі координати (x; y). Максим хоче знати, чи існує така пряма, яка проходить через всі ці вершини.

Програма отримує на вході число N — кількість вершин. У наступних N рядках вводяться координати вершин у вигляді пар чисел через пробіл. Якщо така пряма існує виводимо YES, якщо ні то NO.

Приклад:

Вхід:

2

1 3

4 6

Вихід: YES

 Тести:

Вхід:

3

1 4

5 6

7 9

Вихід: NO

 Вхід:

4

1 1

2 2

3 3

4 4

Вихід: YES

5. Кількість перестановок (20 балів).

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

Програма отримує на вході  кількість квадратних полів і виводить кількість можливих комбінацій

Приклад:

Вхід: 3

Вихід: 2

 

Тести:

Вхід: 4

Вихід: 3

 

Вхід: 10

Вихід: 55