І етап ІОІТ-2016.
Практичний тур

Прочитати більше

Практичний тур І етапу ІОІТ-2016 пройшов з 1 вересня по 30 жовтня включно. Матеріали практичного туру подані нижче.

Завдання для 9 класу Завдання для 10-11 класу

Обмін валют (Excel, 9-11 класи)

Задача потребує знання функцій ВПР (або ЕСЛИ) та ОКРУГЛ, а також вміння роботи з основними математичними операторами.

Завантажити розв'язання

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

Це завдання можна розв’язати двома шляхами: використовуючи функцію ЕСЛИ (IF), або ж з використанням функції ВПР (VLOOKUP), що є більш загальним. Ми розглянемо більш загальне рішення, а вам пропонуємо власноруч розв’язати цю задачу за допомогою функції ЕСЛИ (IF).

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

Таким чином для будь-якої пари валют нам потрібно визначити курс для кожної валюти:

D2=ВПР(A2; $I$2:$K$4; 3; ЛОЖЬ)

D4=ВПР(A4; $I$2:$K$4; 3; ЛОЖЬ)

та поділити курс першої валюти на курс другої:

C4=D2/D4

Таким чином ми отримаємо курс першої валюти відносно другої.

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

B4=ОКРУГЛ(C4*B2)

Банкомат (Excel, 9 клас)

Задача потребує знання функцій ЦЕЛОЕ та ОСТАТ, а також вміння роботи з основними математичними операторами та різними типами посилань.

Завантажити розв'язання

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

Ця задача є класичним прикладом задачі на оптимізацію в програмуванні. В загальному випадку її рішення можна подати у вигляді рекурсивного алгоритму або ж задачі лінійного програмування, що вирішується засобами надбудови Пошук рішення (Розв’язувач), але поданий в умові набір купюр, що використовується в Україні (купюри номіналом 1, 2, 5, 10, 20, 50, 100, 200 та 500) дозволяє значно спростити розв’язання задачі.

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

Неважко помітити, що кожен більший номінал є результатом суми одного або двох попередніх за зростанням номіналів. Наприклад, 500=200+100, 200=100+100, 100=50+50, 50=20+20+10, 20=10+10, 10=5+5, 5=2+2+1, 2=1+1.

Представимо цей факт у вигляді наступної структури:

В цьому дереві кожна батьківська вершина може бути представлена сумою своїх синів.

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

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

Отже, жадібний алгоритм є коректним для заданих в умові номіналів.

Виконати його в Excel значно простіше, аніж довести його коректність. На кожному кроці (тобто для кожного номіналу від 500 до 1) ми беремо максимальну можливу кількість купюр поточного номіналу. Ця кількість визначається як ціла частина від ділення за допомогою функції ЦЕЛОЕ (INT):

C5=A1

B4=ЦЕЛОЕ(C5/A4)

А залишок кожного разу визначається за допомогою функції ОСТАТ (MOD) наступним чином:

C4=ОСТАТ(C5; A4)

Тепер ми можемо протягнути діапазон B4:C4 вниз до 12 рядка, таким чином отримавши в стовпці B відповідь на питання задачі – скільки купюр кожного номіналу потрібно видати.

Кодування (Excel, 9-11 класи)

Задача потребує знання функцій ВПР та СМЕЩ, функцій обробки тексту та помилок, а також вміння роботи з основними математичними операторами та різними типами посилань.

Завантажити розв'язання

Задача практично повністю охоплює функції для роботи з рядками в Excel. Розіб’ємо її на три частини: переклад слова з кожної з мов азбукою Морзе, переклад з морзянки кожною мовою, вибір серед трьох перекладів потрібний на основі обраної користувачем мови.

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

Для перекладу українського слова морзянкою нам необхідно спочатку розділити його на окремі літери. Для цього поступово відділятимемо по одній літері зліва за допомогою функцій ЛЕВСИМВ (LEFT), ПРАВСИМВ (RIGHT), ЕСЛИ (IF) та ДЛСТР (LEN):

B4=B1

C4=ЛЕВСИМВ(B4)

B5=ПРАВСИМВ(B4; ЕСЛИ(ДЛСТР(B4)>1; ДЛСТР(B4); 1) -1)

Ці формули потрібно буде протягнути на 30 рядків, оскільки за умовою завдання літер в слові не більше тридцяти.

Після цього для кожної літери знайдемо відповідник морзянкою за допомогою функції ВПР (VLOOKUP). Якщо функція поверне помилку, це означає, що відповідник не знайдено, тому просто опустимо цю літеру в результаті:

D4=ЕСЛИОШИБКА(ВПР(C4; $P$2:$Q$33; 2; ЛОЖЬ); "")

Формула також протягується на 30 рядків.

Тепер потрібно зчепити усі отримані символи. Оскільки функція СЦЕПИТЬ (CONCATENATE) не працює з діапазонами, це потрібно буде робити поступово:

E4=D4

E5=СЦЕПИТЬ(E4; ЕСЛИ(D5="";"";" "); D5)

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

Таким чином, в комірці E33 буде результат перекладу морзянкою. Для зручності помістимо його в комірку E1.

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

Для цього знайдемо позицію пробілу в поточному рядку, рядок до пробілу збережемо в стовпці I, а все інше (крім, звісна річ, пробілу) – в стовпці G і далі продовжуватимемо виконувати ті ж дії з новим рядком. Якщо пробіл не було знайдено (це ми визначимо за допомогою функції ЕСЛИОШИБКА - IFERROR) в результат було передано весь рядок:

G4=B2

H4=НАЙТИ(" "; G4)

G5=ПРАВСИМВ(G4; ДЛСТР(G4)-H4)

I4=ЕСЛИОШИБКА(ЛЕВСИМВ(G4; H4-1); G4)

Формули, звісна річ, потрібно протягнути на 30 рядків відповідно до максимальної кількості літер в слові.

Тепер в нас є розкладена на літери морзянка, яку потрібно перетворити за допомогою функції ВПР на літери українського алфавіту. Але, оскільки ВПР здійснює пошук лише за першим стовпцем, необхідно піти на певну хитрість: ми продублюємо українські літери в стопці R та використаємо вже новий діапазон:

J4=ЕСЛИОШИБКА(ВПР(I4; $Q$2:$R$33; 2; ЛОЖЬ); "")

Далі знов-таки конкатенуємо наші літери, але вже без пробілів, протягуємо і комірка K33 міститиме відповідь:

K4=СЦЕПИТЬ(K3;J4)

Для зручності помістимо цю відповідь в комірку G1.

Перед виконанням третьої частини завдання необхідно до комірок E1:E3 внести переклад поданого користувачем слова морзянкою з використанням трьох алфавітів: українського, російського та англійського відповідно. Аналогічно до комірок G1:G3 за допомогою формул повинні бути внесені результати перекладу морзянки з комірки B2 всіма трьома мовами.

Результат для конкретної обраної мови можна буде отримати за допомогою функції СМЕЩ (OFFSET):

C1=СМЕЩ(E1;A1;0)

C2=СМЕЩ(G1;A1;0)

Також його можна отримати за допомогою кількох вкладень функції ЕСЛИ (IF).

Оргкомітет (Excel, 9-11 класи)

Задача потребує знання функцій ОСТАТ, ЦЕЛОЕ, ЕСЛИ та СМЕЩ, функцій обробки помилок та статистичних, а також вміння роботи з основними математичними операторами та різними типами посилань.

Завантажити розв'язання

Суть цієї задачі полягає в перетворенні квадратного масиву в лінійний (в даному випадку – в стовпець). На початку ми маємо масив K1:N110 (останній стовпець залишаємо порожнім).

Спочатку потрібно визначити скільки учасників школи в який стовпець потрапить. Це округлена до найближчого більшого цілого половина кількості учасників:

O1=ОКРУГЛВВЕРХ(СЧЁТЗ(K:K)/2,0)

Далі пронумеруємо рядки в наших майбутніх бейджах (стовпець P) та самі бейджі (стовпець R) доти, поки бейджі повинні бути (поки номер попереднього бейджа менший за кількість учасників в першому стовпці):

P1=0; P2=1; P3=2; P4=3

P5=ЕСЛИ(ИЛИ(R1>=$O$1-1; P4=-1); -1; P4+1)

R1=ЦЕЛОЕ(P1/4)

Тут як -1 ми позначили відсутність даних.

В стовпці Q для зручності позначимо номер поля в межах одного бейджа (0 – прізвище, 1- ім’я, 2 – киянин чи ні, 3 – порожнє поле):

Q1=ОСТАТ(P1; 4)

Всі формули потрібно протягнути відповідно до максимальної кількості бейджів в стовпці до рядка 220 (=55*4).

Тоді для отримання значення потрібного поля достатньо зміститись відносно комірки K1 на потрібну кількість рядків та стовпців:

S1=ЕСЛИОШИБКА(СМЕЩ($K$1; R1; Q1); 0)

Цю формулу також потрібно буде протягнути до 220-го рядка аркуша.

Цю частину можна виконати також і за допомогою функції ИНДЕКС. Пропонуємо вам спробувати це самостійно.

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

C2=ЕСЛИ(S1=0; ""; S1)

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

Отримання другого стовпця є аналогічним, за виключенням обчислення номера рядка.

Тепер нам потрібно почати зі значення, наступного за тим, яким завершився стовпець P:

V1=$O$1*4; V2=V1+1; V3=V2+1; V4=V3+1

Після цього нумерація продовжується доти, поки не буде вичерпано бейджі:

V5= ЕСЛИ(ИЛИ(X1>=СЧЁТЗ(R:R)/2; V4=-1); -1; V4+1)

Далі копіюємо стовпці Q:S в стовпці W:Y та позбуваємось в стовпці G зайвих нулів:

G2=ЕСЛИ(Y1=""; ""; Y1)

Без повторів (Excel, 9-11 класи)

Задача потребує знання функцій ЕСЛИ, ПОИСКПОЗ та ВПР, функцій обробки помилок, а також вміння роботи з різними типами посилань.

Завантажити розв'язання

Ця задача полягала у виконанні за допомогою формул вже наявної в Excel функції прибирання повторів в переліку.

В стовпці D знаходиться перелік не більш, ніж 50 імен. В стовпці E потрібно вивести їх без повторів та без пропусків між рядками.

Для кожного слова, починаючи з другого (перше точно раніше не зустрічалося) перевіряємо, чи зустрічалося воно раніше:

B1=ЕОШИБКА(ПОИСКПОЗ(D2; $D$1:D1; 0))

Цю формулу протягуємо до 50-го рядка відповідно до кількості слів. Перша частина діапазону$D$1:D1 залишатиметься незмінною та вказуватиме на перший елемент списку, а друга змінюватиметься та вказуватиме на попереднє відносно поточного слово в списку.

Функція ЕОШИБКА (ISERROR) дозволить нам перевірити наявність повтору: якщо ПОИСКПОЗ (MATCH) поверне число, тоді поточне слово зустрічалось раніше, якщо помилку – ні. Відповідно ИСТИНА (TRUE) в стовпці B означатиме, що поточне слово унікальне, а ЛОЖЬ (FALSE) – що ні.

Позначимо в стовпці A перше слово номером 1:

A1=1

Далі якщо слово в цьому рядку раніше не зустрічалось будемо номер збільшувати на одиницю, а інакше залишатимемо попередній:

A2=ЕСЛИ(B2; A1+1; A1)

З пошуком потрібного нам слова за його номером нам допоможе функція ВПР (VLOOKUP): здійснюючи пошук за стовпцем A вона знаходитиме перше співпадіння номеру та повертатиме нам відповідне слово зі стовпця D.

Пронумеруємо рядки в стовпці H від 1 до 50. Тоді:

I1=ЕСЛИОШИБКА(ВПР(H1; $A$1:$D$50; 4; ЛОЖЬ); 0)

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

E1=ЕСЛИ(I1=0; ""; I1)

Файлова система (Access, 10-11 класи)

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

Завантажити розв'язання

Схему бази даних, яку було запропоновано реалізувати в задачі, з відміченими ключами на ній подано нижче:

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

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

Запит Корінь можна поділити на дві окремі частини: пошук підкаталогів каталогу root (запит Каталоги в корені) та пошук файлів каталогу root (запит Файли в корені).

В запиті Корінь на схему даних додається двічі таблиця Каталоги та створюється зв’язок між батьківським та дочірнім каталогом:

Тоді таблиця Каталоги_1 є батьківським каталогом, а Каталоги – дочірнім.

Відповідним чином запит є тривіальним фільтром, де назва дочірнього каталогу відмінна від root, а назва батьківського – рівна root.

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

Назва: Назва каталогу

SQL-код запиту:

			SELECT Каталоги.[Назва каталогу] AS Назва, "каталог" AS Тип
			FROM Каталоги AS Каталоги_1 INNER JOIN Каталоги ON Каталоги_1.Ідентифікатор = Каталоги.[Батьківський каталог]
			WHERE Каталоги.[Назва каталогу])<>"root" AND Каталоги_1.[Назва каталогу]="root"
			ORDER BY Каталоги.[Назва каталогу];
		

Запит Файли в корені є тривіальним фільтром, де назва каталогу рівна root.

SQL-код запиту:

			SELECT Файли.[Назва файлу] AS Назва, "файл" AS Тип
			FROM Каталоги INNER JOIN Файли ON Каталоги.Ідентифікатор = Файли.Каталог
			WHERE Каталоги.[Назва каталогу]="root"
			ORDER BY Файли.[Назва файлу];
		

В запиті Корінь необхідно за допомогою оператора UNION об’єднати дані двох попередніх запитів за відсортувати їх за типом.

SQL-код запиту:

			SELECT *
			FROM (SELECT * FROM [Каталоги в корені]) UNION (SELECT * FROM [Файли в корені])
			ORDER BY тип;
		

Запит Пошук здійснює фільтрацію за регулярним виразом. З таблиці Файли ми обираємо назви за допомогою оператора Like (Схоже на) та регулярного виразу:

Like "*.doc" Or Like "*.docx" Or Like "*.docm"

"*.doc" означає рядок, що починається довільною кількістю довільних символів, потім містять крапку та символи doc.

SQL-код запиту:

			SELECT Файли.[Назва файлу] AS Назва
			FROM Файли
			WHERE Файли.[Назва файлу] Like "*.doc" Or Файли.[Назва файлу] Like "*.docx" Or Файли.[Назва файлу] Like "*.docm";
		

Прогноз погоди (Access, 10-11 класи)

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

Завантажити розв'язання

СУБД Access не вміє здійснювати імпорт з використанням багатосимвольного розділювача, тому його потрібно за допомогою Word замінити на будь-який односимвольний, наприклад | (вертикальну риску).

Після цього необхідно здійснити імпорт таблиці з текстового документу (Зовнішні дані – Текстовий файл), обрати розташування файлу та вказати обраний вами розділювач. СУБД створить нову таблицю, яку потім слід назвати Дані погоди.

Запит Погода на день відображає зведені дані про погоду для кожної наявної в базі доби і є звичайним запитом на групування. Здійснюється групування за датою (обчислюється за допомогою функції DateValue, яка відкидає час з поля типу Дата та час), обирається агрегатна функція Avg для температури T та тиску P, а також функція суми для опадів tR.

SQL-код запиту:

			SELECT DateValue([Місцевий час в Києві / Жулянах (аеропорт)]) AS Дата, Avg([Дані погоди].T) AS Температура, Avg([Дані погоди].P) AS Тиск, Sum([Дані погоди].tR) AS Опади
			FROM [Дані погоди]
			GROUP BY DateValue([Місцевий час в Києві / Жулянах (аеропорт)])
			ORDER BY DateValue([Місцевий час в Києві / Жулянах (аеропорт)]);
		
Запит Прогноз відображає передбачення погоди о полудні поточного дня на основі наявних в базі даних і є комбінацією групування та фільтрації. Час (отримується за допомогою функції TimeValue, яка відкидає дату з поля типу Дата та час) встановлюється рівним #12:00:00#, день (отриманий за допомогою функцій Day та Date, день поточної дати) – рівним поточному дню, місяць (отриманий за допомогою функцій Month та Date, місяць поточної дати) – поточному місяцю. До полів температури T та тиску P застосовується агрегатна функція Avg.

SQL-код запиту:

			SELECT Avg([Дані погоди].T) AS [Avg-T], Avg([Дані погоди].P) AS [Avg-P]
			FROM [Дані погоди]
			WHERE TimeValue([Місцевий час в Києві / Жулянах (аеропорт)])=#12:0:0# AND Day([Місцевий час в Києві / Жулянах (аеропорт)])=Day(Date()) AND Month([Місцевий час в Києві / Жулянах (аеропорт)])=Month(Date());