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

Обробка тексту

Функції обробки тексту. По символьна обробка тексту. Пошук заданого підрядка в тексті. Алгоритм Бойєра-Мура. Використання хеш-функції  для пошуку довільного підрядка у рядку. Рекурсивний синтаксичний аналіз виразів із дужками.

Рядкові величини

Pascal (Delphi)

- операція + (з’єднання)                        ‘місто’+’ ’+’Луцьк’

Функції роботи з рядками:

Процедури роботи з рядками:

C++

Функції для опрацювання рядків

Модуль string.h

strlеn(<рядок>) - визначає фактичну кількість символів у  рядку, застосовується у виразах;

strcat(rl, r2) - команда з'єднання рядків г1, г2 в один ря­док, результат присвоює змінній г1;

strncat(M, г2, п) - до змінної г1 додає перших n символів рядка г2, команда;

strcpy(r1, r2) - копіює символи з рядка г2 в рядок г1, команда;

strncpy(r1, r2, n) - копіює перших n символів рядка г2 в рядок r1, команда;

strchr(r1, <символ>) - визначає перше входження деякого символу у рядок r1 так: повертає рядок, який починається від першого входження заданого символу до кінця рядка r1, застосовується у виразах;

strrchr(r1, <символ>) - визначає останнє входження зада­ного символу у рядок, застосовується у виразах;

strspn(r1, r2) - визначає номер першого символу, який входить у рядок г1, але не входить

у рядок г2, застосовується у виразах

strstr(r1, r2) - визначає в рядку г1 підрядок, що починаєть­ся з першого входження рядка г2 у рядок г1, засто­совується у виразах;

strtok(r1, r2) - визначає частину рядка г1, яка закінчується перед першим однаковим символом рядків г1 та г2;

strnset(r1, <символ>, n) - вставляє п разів заданий символ • перед рядком М, застосовується у виразах;

strupr(rl) - перетворює усі малі літери рядка у великі;

strlwr(rt) - перетворює усі великі літери рядка у малі;

strrev(rl) - записує рядок у зворотному порядку.

Задачі

Задача1. ACM World Finals

Ім’я вхідного файлу: acm.in

Ім’я вихідного файлу: acm.out

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

Кожна команда складається з трьох чоловік і має назву. Напишіть програму, яка по короткій назві команди і прізвищах її учасників, формує повну назву команди.

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

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

Формат вихідних даних: єдиний рядок вихідного файлу має містити рівно один рядок з повною назвою команди.

Приклад вхідних і вихідних даних:

Задача2. 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

Задача 3. Дужки.

Перевірити в виразі правильність розставлення дужок. Вивести повідомлення (Yes|No).

Задача 4. Вираз

Обчислити вираз, який містить операції( +,-,*,/), цілі та дійсні числа (2, 2.5, -5.02), дужки.

Тема: Синтаксичний розбір виразів

Однієї з головних причин, що лежать в основі появи мов програмування високого рівня, з'явилися обчислювальні задачі, що вимагають великих об'ємів рутинних обчислень. Тому до мов програмування пред'являлися вимоги максимального наближення форми запису обчислень до природної мови математики. В зв'язка з цей одній з перших областей системного програмування сформувалося дослідження способів виразів. Тут отримані численні результати, проте найбільше розповсюдження отримав метод трансляції за допомогою зворотного польського запису, який запропонував польський математик                Я. Лукашевіч.

              Нагадаємо, що існує цілий ряд  методів  синтаксичного  розбору і обчислення виразів. Нехай вирази є рекурсивними  структурними  даними, які визначаються в термінах самих себе.  Якщо ви обмежитеся використанням у виразах тільки операторів +,  -  * / і дужок,  то зможете сказати, що всі вирази можуть бути визначеними в термінах наступних правил:

              выраз=>терм[+терм][-терм]

              терм=>множник[*множник][/множник]

              множник=>змінна, число або (вираз) де будь-яка частина може бути порожньою.  Квадратні дужки  позначають  необов'язковість,  а => - утворення. Фактично правила є правилами утворення виразів. 

              Вираз             10+5*В складається з двох термів: 10 і 5*В. Проте, включає три множники:  10,  5 і В.  Цими множниками є два числа і одна змінна.

              З другого боку вираз          14*(7-С)   має два  терми 10 і (7-С),  один з яких є числом,  а інша дочірнім виразом. Дочірній вираз розпадається на одне число і одну змінну.

              Даний процес формує основу для рекурсивного низхідного  синтаксичного  розбору,  який є набором загальних  рекурсивних процедур,  що носять характер ланцюжка. На кожному відповідному кроці  синтаксичний розбір може виконувати задані операції в алгебра правильній послідовності. Наприклад розглянемо синтаксичний розбір вхідного виразу 9/3-(100 +56) і виконання операцій по кроках.

Крок 1. Узяти першу лексему: 9/3

Крок 2. Узяти обидва множники і виконати операцію поділу.

В результаті виходить 3.

Крок 3. Узяти другу лексему: (100+56). В даній точці ви повинні рекурсивно  проаналізувати другий вираз.

Крок 4. Узяти обидва числа і скласти. В результаті виходить 156.

Крок 5. Повернутися з рекурсивного виклику і відняти 156 з 3, що дає відповідь - 153.

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

Переведення чисел з однієї системи числення в іншу

Переведення чисел в різних системах числення

На приклад, якщо потрібно перемножити числа 101 і 1001 в двійковій системі, то він спочатку ці числа переводить в десяткову систему таким чином :

(101)₂=1*2²+0*2¹+1*2⁰=4+0+1=5

(1001)₂=1*2³+0*2²+0*2¹+1*2⁰=8+0+0+1=9

Після чого множення чисел 5 і 9 Вася з легкістю виконує в десятковій системі числення і отримує число 45. Далі виконує переведення з десяткової системи числення в двійкову. Для цього потрібно ділити число 45 на 2 ( порядок системи числення ), запам'ятовує залишки від ділення, до тих пір поки в результаті не залишиться число 0:

Відповідь складається з одержаних залишків від ділення шляхом їх запису в зворотному  порядку . Таким чином одержуємо результат : (101101)₂.

1. Задача. Перевести число з  будь-якої системи числення в будь-яку іншу.

Протестувати самостійно

2. Задача  BINARY

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

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

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

Талановитий учень Діма придумав цікаву гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число 19₁₀ = 1×2⁴+0×2³+0×2²+1×2¹+1×2⁰ в двійковій  системі запишеться як 10011₂). Потім вчитель починає зсовувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсовуються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору вихідного числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, учень відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри буде число 1×2⁴+1×2³+1×2²+0×2¹+0×2⁰ = 28.

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

Вхідний файл містить одне ціле число N (0£N£32767).

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

Приклад

3. Задача  Нулі

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

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

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

Необхідно написати програму для знаходження кількості N-значних чисел в системі числення за основою K, таких що їхній запис не буде містити двох нулів підряд.

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

Єдиний рядок вхідного файлу ZEROS.DAT містить два натуральних числа N та K, 2 <= K <= 10, N + K <= 18.

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

Єдиний рядок вихідного файлу ZEROS.SOL повинен містити одне натуральне число - розв'язок задачі.

Приклад.

ZEROS.DAT:

4 2

ZEROS.SOL:

5

Дерево (рекурсивне опрацювання дерев)

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

Кожен рівень цього дерева - це рівень розгалуження, яки відповідає вибору однієї цифри комбінації. Усього рівнів N (у нашому прикладі- 3), по кількості цифр.

Тепер уже ясно, що наприклад, дерево вибору всіляких двійкових комбінацій довжини 3, що починаються на 1 (тобто виду 1::), буде виглядати так:

┌───┐

│ 1 │.............. 1-ая цифра

└─┬─┘

┌────┴─────┐

┌─┴─┐ ┌─┴─┐

│ 0 │......│ 1 │........ 2-ая цифра

└─┬─┘ └─┬─┘

┌──┴──┐ ┌──┴──┐

┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐

│ 0 ││ 1 │.│ 0 ││ 1 │..... 3-я цифра

└───┘└───┘ └───┘└───┘

100 101 110 111

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

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

Давайте порахуємо число листів. Воно збігається з числом усіх двійкових комбінацій. Як виходить кожна з комбінацій? Потрібно просто перебрати (обійти) усі гілки повного дерева праворуч.

Цей процес і називається повним обходом дерева.

Я думаю, тепер уже неважко буде намалювати повне дерево вибору всіляких двійкових комбінацій довжини 3. Воно має пустий корінь, уведений просто для зручності. Ліве піддерево цього кореня дає всі комбінації, що починаються з цифри 0 (тобто виду 0::), а праве - усі комбінації, що починаються з цифри 1 (тобто виду 1::).

┌───┐

│ │

└─┬─┘

┌─────────┴───────────┐

┌─┴─┐ ┌─┴─┐

│ 0 │.................│ 1 │.............. 1

└─┬─┘ └─┬─┘

┌────┴─────┐ ┌────┴─────┐

┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐

│ 0 │......│ 1 │......│ 0 │......│ 1 │........ 2

└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘

┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐

┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐

│ 0 ││ 1 │.│ 0 ││ 1 │.│ 0 ││ 1 │.│ 0 ││ 1 │..... 3

└───┘└───┘ └───┘└───┘ └───┘└───┘ └───┘└───┘

000 001 010 011 100 101 110 111

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

Задача 1

Вивести всілякі N-значні двійкові комбінації L--і (тобто всілякі послідовності нулів і одиниць довжини N).

Отже, ми повинні вивести всі двійкові комбінації, кожна довжиною N. Наприклад, для N = 4 ми повинні вивести наступні 16 комбінацій:

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

Я думаю, уже ясна загальна схема алгоритму обходу дерева вибору:

ЯКЩО знаходимося в листі

ТO вивести всі цифри гілки, від кореня до даного листа

ІНАКШЕ ввійти в піддерево, що починається з 0;

ввійти в піддерево, що починається з 1

ВСЕ

Приведений нижче алгоритм запам'ятовує обрані цифри в таблиці c[1:N]. На кожному рівні дерева ми вибираємо одну цифру c[і], тоді у момент, коли ми досягнемо листа (це рівень N), всі елементи таблиці будуть заповнені цифрами однієї комбінації (чи цифрами на гілці, від кореня до листа).

Процедура Розгалуження ( ЦІЛЕ і, іc ) має два параметри.

Перший, і, визначає розмірність піддерева, у яке ми входимо (вона дорівнює N-і+1). Другий, іc, - це цифра, що стоїть у корені цього піддерева.

А тепер весь алгоритм цілком.

ПОЧ 'розгалуження порожнього кореня:

Розгалуження( 1, 0) ' входимо в ліве піддерево з коренем 0

Розгалуження( 1, 1) ' входимо в праве піддерево з коренем 1

КІН

'Процедура розгалуження при виборі цифри двійкової комбінації 'з номером і+1

АЛГ Розгалуження (ЦІЛЕ і, іc )

ПОЧ

c[і] := іc

ЯКЩО і = N 'досягли листа дерева?

ТО ВИСНОВОК( c[1:N] ) ' -так, виведення комбінації

ІНАКШЕ ' -ні, продовжуємо розгалуження

: Розгалуження( і+1, 0) ' входимо в ліве піддерево з коренем

: Розгалуження( і+1, 1) ' входимо в праве піддерево з коренем

LВСЕ

КІН

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

uses crt;

const n=5;

var c:array[1..n] of іnteger;

procedure pr(іnn:іnteger;іc:іnteger);

var і:іnteger;

begіn

c[іnn]:=іc;

іf іnn=n then begіn for і:=1 to n do wrіte(c[і]);

wrіteln;

end

else begіn pr(іnn+1,0);pr(іnn+1,1);

end;

end;

begіn

clrscr;

pr(1,0);

pr(1,1);

end.

Задача 2

Видати всі N-значні числа в системі з основою K+1, K <= 9 L--і (тобто всі комбінації з цифр від 0 до K, довжини N).

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

uses crt;

const n=3;

k=2;

var c:array[1..n] of іnteger;

і:іnteger;

procedure pr(іnn:іnteger;іc:іnteger);

var j,іі:іnteger;

begіn

c[іnn]:=іc;

іf іnn=n then begіn for j:=1 to n do wrіte(c[j]);

wrіte('---');

end

else for іі:=0 to k do pr(іnn+1,іі);

end;

begіn

clrscr;

for і:=0 to k do pr(1,і);

end.

Задача 3

Вивести всілякі N-значні двійкові комбінації L--і в порядку спадання утворених ними чисел.

Дзеркальне відображення дерева змінює його в кожній гілці таким чином:

└─┬─┘ └─┬─┘

┌────┴─────┐ ┌────┴─────┐

┌─┴─┐ ┌─┴─┐ -> ┌─┴─┐ ┌─┴─┐

│ 0 │ │ 1 │ │ 1 │ │ 0 │

L-T-і L-T-і L-T-і L-T-і

Тому всі зміни алгоритму будуть стосуватися тільки порядку обходу піддерева: спочатку ми будемо входити в піддерево з коренем 1, а уже потім у піддерево з коренем 0, а не навпаки, як раніше.

В алгоритмі це приведе до перестановки місцями двох наступних

(одна за одною) команд виклику процедури Розгалуження().

Тепер наш алгоритм, наприклад, для N=4, видасть комбінації

у наступній послідовності:

1111 1110 1101 1100 1011 1010 1001 1000

0111 0110 0101 0100 0011 0010 0001 0000

Задача 3

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

Для N=4 послідовність видачі комбінацій повинна бути така:

0000 0001 0010 0011 0100 0101 0110 0111 <- зростає

1111 1110 1101 1100 1011 1010 1001 1000 <- спадає

Подивіться тепер на зображене нижче дерево вибору для N=4, воно схоже на ті дерева для N=3, що ми малювали раніше, але має особливість: ліве піддерево з рівня 2 відрізняється від правого порядком вибору 0 і 1. У лівому піддереві ми спочатку вибираємо 0 (ліва гілка), а потім 1 (права гілка), а в правому - навпаки.

┌─┐

│ │

└┬┘

┌───────────────┴────────────────┐

┌┴┐ ┌┴┐

│0│..............................│1│................. 1

└┬┘ └┬┘

┌──────П────────┐ ┌──────О────────┐

┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐

│0│.............│1│..............│1│.............│0│........ 2

└┬┘ └┬┘ └┬┘ └┬┘

┌───П───┐ ┌───П───┐ ┌───О───┐ ┌───О───┐

┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐

│0│.....│1│.....│0│.....│1│......│1│.....│0│.....│1│.....│0│.... 3

└┬┘ └┬┘ └┬┘ └┬┘ └┬┘ └┬┘ └┬┘ └┬┘

┌─П─┐ ┌─П─┐ ┌─П─┐ ┌─П─┐ ┌─О─┐ ┌─О─┐ ┌─О─┐ ┌─О─┐

┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐

│0│.│1│.│0│.│1│.│0│.│1│.│0│.│1│..│1│.│0│.│1│.│0│.│1│.│0│.│1│.│0│.. 4

└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘

└──────────────────────────────┘└──────────────────────────────┘

ліве піддерево праве піддерево

Будемо робити обхід цього дерева, перебираючи його гілки праворуч.

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

перша половина кодів буде виводитись у порядку зростання, а друга половина - у порядку убування.

Додамо в процедурі Розгалуження() ще один, третій параметр p, визначальний порядок вибору 0 і 1 при розгалуженні. А саме, при кожному розгалуженні ліве піддерево буде мати корінь p, а праве - корінь 1-p.

Таким чином, параметр p визначає два типи розгалужень, які ми назвемо прямим і зворотнім,

при p = 0: при p = 1:

└┬┘ └┬┘

┌─П─┐ ┌─З─┐

┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐

│0│ │1│ │1│ │0│

└─┘ └─┘ └─┘ └─┘

(буква в крапці розгалуження вказує на тип розгалуження:

П-прямий, З-зворотний).

Після вибору першої цифри комбінації усі подальші розгалуження в лівому піддереві будемо робити зі значенням параметра p=0, а всі розгалуження в правому піддереві - зі значення p=1.

ЦІЛИЙ N 'довжина двійкової комбінації

ЦІЛИЙ ТАБ c[1:N] 'цифри однієї комбінації

АЛГ Двійкові_комбінації( )

ПОЧ 'розгалуження порожнього кореня:

Розгалуження( 1, 0, 0) ' входимо в ліве піддерево з коренем 0

' типом розгалуження П

Розгалуження( 1, 1, 1) ' входимо в праве піддерево з коренем 1

' типом розгалуження ПРО

КІН

' Процедура розгалуження при виборі цифри двійкової комбінації з номером і+1

АЛГ Розгалуження( ЦІЛЕ іc, і, p )

ПОЧ

c[і] := іc

ЯКЩО і = N 'досягли листка дерева?

ТО ВИВЕДЕННЯ( c[1:N] ) ' -так, виведення комбінації

ІНАКШЕ ' -ні, продовжуємо розгалуження

: Розгалуження( і+1, p, p ) ' входимо в ліве піддерево

: Розгалуження( і+1, 1-p, p ) ' входимо в праве піддерево

ВСЕ

КІН

uses crt;

const n=4;

var c:array[1..n] of іnteger;

і:іnteger;

procedure pr(іnn,іc,p:іnteger);

var j:іnteger;

begіn

c[іnn]:=іc;

іf іnn=n then begіn for j:=1 to n do wrіte(c[j]);

wrіteln;

end

else begіn pr(іnn+1,p,0);pr(іnn+1,1-p,1);end;

end;

begіn

clrscr;

pr(1,0,0);

pr(1,1,1);

end.

Коди Грея

Двійковим N-розрядним кодом Грея називається послідовність усіляких N-значних кодів, у якій кожна наступна кодова комбінація відрізняється від попередньої на 1 тільки в одному довільному розряді. Видати N-розрядні коди Грея.

Наприклад, для N=4, кодом Грея є:

0000 0001 0011 0010 0110 0111 0101 0100

1100 1101 1111 1110 1010 1011 1001 1000 .

НОТАТКИ

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

Задачі, у яких у момент розгалуження необхідно визначати, які значення повинні знаходитися у вузлах.

1. Вивести всілякі N-значні двійкові комбінації,

N

сума цифр яких дорівнює K (K < 2)

2. Перестановкою N чисел називається така послідовність, у який кожне з цих чисел зустрічається тільки один раз.

Видати всі перестановки натуральних чисел чисел від 1 до N ( N <= 9).

3. Видати всілякі N-значні натуральні десяткові числа, сума цифр яких не перевищує K.

4. Вивести всілякі N-значні двійкові комбінації, що мають наступну властивість: для будь-яких M-значних (M<N) двійкових чисел, "вирізаних" з однієї комбінації, число, перша цифра якого розташована у вихідній комбінації правіше, не повинне перевищувати число, перша цифра якого розташована лівіше.

Наприклад, для N=5, M=3, допустимими є комбінації

11111 111 111 111 * 1111 111 111 *

11110 111 111 110 * 1110 111 110 *

11101 111 110 101 * 1101 110 101 *

11100 111 110 100 * 1100 110 100 *

11011 110 101 011 * 1011 101 011 *

11010 110 101 010 * 1010 101 010 *

11001 110 100 001 * 1001 100 001 *

11000 110 100 000 * 1000 100 000 *

10111 101 011 111 0111 011 111

10110 101 011 110 0110 011 110

10101 101 010 101 0101 010 101

10100 101 010 100 0100 010 100

10011 100 001 011 0011 001 011

10010 100 001 010 0010 001 010

10001 100 000 001 0001 000 001

10000 100 000 000 * 0000 000 000 *

01111 011 111 111

01110 011 111 110

01101 011 110 101

01100 011 110 100

01011 010 101 011

01010 010 101 010

01001 010 100 001

01000 010 100 000

00111 001 011 111

00110 001 011 110

00101 001 010 101

00100 001 010 100

00011 000 001 011

00010 000 001 010

00001 000 000 001

00000 000 000 000 *

1. Порядок роботи

2. Структура слідування

2. Розгалуження

3. Цикл

4. Масиви

5. Робота з файлами

Олімпіадна інформатика

1. Що таке олімпіадна інформатика?

Що потрібне для успішної участі в олімпіадах по інформатиці? Як показує практика, тільки знання мови програмування для цього явно не достатньо. Взагалі, виявляється, що олімпіадні задачі по інформатиці лежать десь на стику математики і програмування. І дуже часто виявляється, що розв’язуючи задачі школярі не тільки вчаться програмувати, але і освоюють нові розділи математики.

2. Як перевіряються розв’язки задач олімпіади

Історично склалося так, що розв’язки на олімпіадах по програмуванню перевіряються автоматично. Ваше завдання написати програму, яка за заданими вхідними даними обчислює і виводить вихідні дані.

3. Апаратне та програмне забезпечення

Учасникам олімпіади можуть вибирати мову програмування с заданого переліку: Pascal, C або C++. Система програмування Free Pascal 2.0 (чи новішої версії), GCC 4.2 (чи новішої версії), Turbo Delphi Explorer, Visual C++ 2008 Express).

4. Завдання олімпіади

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

Основними категоріями олімпіадних задач є:

Системи тестування

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

http://olymp.sumdu.edu.ua - Веб-ресурс підтримки та проведення шкільних та студентських олімпіад з інформатики

http://www.e-olimp.com.ua/ - Інтернет-портал організаційно-методичного забезпечення дистанційних олімпіад з програмування для обдарованої молоді навчальних закладів України

http://www.olymp.vinnica.ua/ - Центр підтримки та проведення олімпіад школярів з використанням можливостей Internet.

Список тестуючих систем

Список ресурсів

· http://vippolabinfo.16mb.com - сайт «Лабораторія інформатики сьогодні», методична підтримки напрямків роботи.

· http://vippoolimp.16mb.com – Волинська учнівська Інтернет олімпіада з програмування.

· http://schoololymp.byethost32.com – заочна школа роботи з обдарованими учнями з інформатики.

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

з інформатики 2012-2013 н.р.

Задача 1. «Число» (25 балів)

Ім’я файлу програми: NUMBER.*

Ім’я вхідного файлу: INPUT.DAT

Ім’я вихідного файлу: OUTPUT.ANS

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

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

Інструкція

1. Попросіть загадати три цифри (обов'язково цифри, а не числа).

2. Потім попросіть його помножити першу загадану цифру на 2 і додати до результату, що вийшов 3. Потім помножити це число на 5.

3. Потім до вже отриманого числа додав другу загадану цифру і помножити суму на 10.

4. До нового числа, що вийшло додайте третю задуману цифру.

5. Попросіть його назвати число, що вийшло.

6. Зробіть вигляд, що ви задумалися (тільки довго не думайте). Тим часом, відніміть від вимовленого вголос числа 150. Вийде, що перша, друга і третя цифри результату є задуманими цифрами гравця.

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

Вихідні дані. Вихідний текстовий файл містить рядок з трьома задуманими числами через пропуск.

Приклад файлів

Задача 2. «Фігура» (25 балів)

Ім’я файлу програми: figure.*

Ім’я вхідного файлу: INPUT.DAT

Ім’я вихідного файлу: OUTPUT.ANS

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

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

Вхідні дані. Вхідний текстовий файл містить чотири рядки по чотири цілих числа розділених пропусками, які задають координати початку та кінця чотирьох відрізків (|x,y|≤2147483647).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з назвою фігури з найвищим пріоритетом(див. таблицю).

Приклад файлів

Завдання 3. «Коло» (25 балів)

Ім’я файлу програми: circle.*

Ім’я вхідного файлу: INPUT.DAT

Ім’я вихідного файлу: OUTPUT.ANS

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

Дуже талановитий учень вмів від руки малювати ідеальні кола. За перерву він на дошці намалював велику кількість кіл. На початку уроку вчитель попросив учнів класу поміряти радіуси або діаметри кіл дерев’яною лінійкою в сантиметрах.

Вчитель записав в зошит їхні заміри, порахував кількість замірів і попросив талановитого «художника» підрахувати кількість різних кіл, яку він намалював.

Технічні умови. Програма CIRCLE читає з першого рядка файлу кількість замірів N (1≤N≤1000000) та наступного рядка з N натуральних чисел, які задають розмір кіл (не більші 1000000). Числа розділено пропуском. Програма виводить на екран єдине число - шукану величину.

Приклад файлів

Задача 4. «Трикутник» (25 балів)

Ім’я файлу програми: triangle.*

Ім’я вхідного файлу: INPUT.DAT

Ім’я вихідного файлу: OUTPUT.ANS

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

Інший талановитий учень, після вивчення теореми Піфагора, перед наступним уроком намалював на дошці N прямокутних трикутників. Вчитель на початку уроку визначив довжини сторін трикутника дерев’яною лінійкою в сантиметрах і заокругливши до цілого записав числа в зошит. На початку уроку, закривши дошку, продиктував записані числа в довільному порядку та попроси визначити яку кількість прямокутних трикутників побудував «учень Піфагора».

Вхідні дані. Вхідний текстовий файл містить в першому рядку число N (3<=N<=100) , далі слідують 3*N рядків, у кожному одне натуральне число (a<=2147483647).

Вихідні дані. Вихідний текстовий файл містить один рядок з цілим числом k – максимальна кількість прямокутних трикутників , які можна побудувати з заданих сторін.

Приклади файлів

Сумарна кількість балів – 100