ОЛІМПІАДА КИЇВСЬКОГО

НАЦІОНАЛЬНОГО УНІВЕРСИТЕТУ

ІМЕНІ ТАРАСА ШЕВЧЕНКА:

ФАКУЛЬТЕТ КІБЕРНЕТИКИ

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

Олімпіада проходитиме в два тури. Перший  -- заочний, другий – очний.

Переможці першого туру запрошуються до участі в другому турі.

Пільги переможців другого туру визначаються правилами прийому до університету.

Усі учасники олімпіади повинні надіслати поштою  або передати особисто до факультету кібернетики (проспект академіка Глушкова, 2, корпус 6, кімн.29) не пізніше 1 березня 2008 року розв’язки задач першого туру у зошиті, а також поштовий конверт із маркою та своєю зворотною адресою. Анкета учасника наклеюється на обкладинку зошита.

АНКЕТА УЧАСНИКА ОЛІМПІАДИ

Прізвище _____________________________________

Ім’я   _________________________________________

По-батькові  ___________________________________

Область  ______________________________________

Місто, село ___________________________________

Номер школи, клас ______________________________

Адреса школи, телефон _________________________

Домашня поштова адреса_________________________

Контактний телефон ____________________________

Електронна адреса (E-mail) ________________________

Зошити надсилаються за адресою:

01033, Київ-33,

Володимирська, 64,

Київський національний університет імені Тараса Шевченка,

журі олімпіади 2008, 

факультет кібернетики, кімн.29

телефон для довідок (044) 521-35-54

Олімпіада факультету кібернетики 2008 року

Заочний тур

Задачі групи А.

1.     Продовжить послідовність чисел одним числом: 1, 10, 12, 21, 100, 102, 111, ... Відповідь обґрунтуйте.

2.     Розглянемо гострокутний  і точку , що лежить на стороні . Позначимо  – точки перетину висот  та . Для яких точок  трикутники  і  будуть подібними.

3.     Дорога між містами А і Б  спочатку йде з гори, а потім ще половину цієї відстані в гору. В гору мотоцикліст їхав з постійною швидкістю від 30 до 40 км/год, а з гори вдвічі швидше ніж в гору. Коли він проїхав весь шлях, то виявилось, що на перші 100 км шляху він витратив на 1 годину менше, ніж на останні 100 км. Скільки часу тривала його подорож від А до Б?

4.     Плем’я людожерів узяло у полон красуню білявку. Відпустити її чи з’їсти має вирішити зібрання 100 старійшин, які дуже полюбляють банани. «Доброму» вождю людожерів білявка дуже сподобалась і він хоче прийняття зборами рішення про її звільнення, але «зла» дружина вождя проти цього. При вирішенні долі білявки кожен старійшина віддасть свій голос за ту пропозицію, за яку одержить більше бананів. Якщо старійшина одержує однакову кількість бананів від протилежних сторін, то при голосуванні він утримується. Щоб будь-яке рішення було прийняте необхідно, щоб «ЗА» проголосував  принаймні 51 старійшина. Вождь знає, що дружина може роздати старійшинам не більше 1000 бананів. Яку мінімальну кількість бананів і по скільки повинен роздати вождь, щоб гарантувати прийняття рішення на свою користь, не зважаючи на те, у який спосіб роздасть банани його дружина.

5.     Розв’язати рівняння: .

6.     Розв’язати систему рівнянь: .

7.     З точки  кола проведені три хорди , ,  таким чином, що . Знайти радіус кола.

8.     При яких значеннях параметру  рівняння  має не більше двох розв’язків на проміжку ?

9.     У трикутника  задані сторона  та . В яких межах може змінюватися висота  цього трикутника?

10.                       У трикутника  точка , точки  мають однакову абсцису , при цьому точка  розташована на графіку функції , а точка  – на графіку . При якому значенні параметру  площа трикутника  буде а) найбільшою; б) найменшою?

Задачі групи В.

1. Сортуюча машина. Є машина для сортування цілих чисел. Вона має лише одну команду MOVE з одним аргументом. Ця команда переносить число, задане в аргументі, в кінець послідовності. Наприклад, для сортування масиву чисел {19, 7, 8, 25} у зростаючому порядку слід виконати дві команди:

1. MOVE 19, отримаємо {7, 8, 25, 19}.

2. MOVE 25, отримаємо {7, 8, 19, 25}.

Вхід. Масив чисел a.

Вихід. Найменша кількість команд MOVE, необхідних для сортування масиву а за зростанням.

Обмеження: -1000  a[i]  1000.

2. Загублені дужки. Є арифметичний вираз, що містить додатні числа, знаки ‘+’, ‘-‘ та дужки. Потім дужки стерли. Необхідно визначити найменше значення, яке могло мати вихідний арифметичний вираз.

Вхід. Рядок e, що містить арифметичний вираз без дужок.

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

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

Вхід. Три рядки a, b та c.

Вихід. Кількість спільних підпослідовностей трьох рядків a, b та c.

4. Щасливе число. Нехай n – натуральне число. Піднесемо в k - у степінь кожну його цифру і просумуємо отримані результати. Позначимо отриманий результат через S_k(n). Наприклад, S₂(65) = 6² + 5² = 61. Побудуємо послідовність n, S_k(n), S_k(S_k(n)), … . Щастям числа n по відношенню до k будемо називати найменше число в цій послідовності.

Вхід. Три числа a, b, k.

Вихід. Знайти щастя кожного числа між a та b включно по відношенню до k і повернути їх суму.

Обмеження: 1  a, b  10⁶, 1  k  6.

5. Паралельне програмування. Існує складна система, що містить в собі декілька паралельно працюючих процесорів. Але деякі процесори можуть почати роботу лише тоді, коли інші закінчать свою роботу. i - ий елемент масиву time містить час виконання роботи  i - им процесором (в мілісекундах). Інформація про залежність виконання робіт міститься в масиві prec: prec[i][j]  містить ‘Y’, якщо процесор j може почати роботу лише по завершенню роботи процесора i, та ‘N’, якщо час роботи i - го та j - го процесорів не залежать один від іншого.

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

Вихід. Найменший час (в міліисекундах), необхідний для виконання робіт усіма процесорами. Якщо роботи виконати неможливо, повернути -1.

{"NNN",

"NNN",

{"NNN",

"YNN",

{"NYN",

"NNY",