Задача №1 Ця задача є простою, але містить "підводний камінь". Якщо учасник представляє вхідний файл як текстовий, то його програма не проходить тест номер 8, так як цей тест містить у собі символ з кодом 26 який функцією eof() сприймається як кінець файлу. Учасники, які представляли файл, як типізований файл (file of char) і читали цей файл посимвольно, не проходили тест номер 9 за часом, так як не встигали НАВІТЬ прочитати дані. Для проходження обох тестів потрібно було представити файл як нетипізофаний (file) та читати файл функцією BlockRead. Деякі учасники пішли iншим шляхом: вони об'являли вхідний файл як File of char, далі за допомогою функції FileSize взнавали розмір файлу, об'являли вхідний файл як текстовий, і читали цей файл у циклі for i:=1 to Розмір_Файлу do ... Не використовуючи при цьому функції eof. ----------------------------------------------------------------------- Задача №2 Розглянемо два можливих розв'язки цієї задачі: Одним з методів розв'язку цієї задачі є переклад арифметичного виразу у Зворотній Польский Запис (ЗПЗ). У ЗПЗ оператори (+,-,*,...) йдуть після своїх операндів: | ЗПЗ ----------------------- 2+3 | 2 3 + 2+4*5 | 2 4 5 + * 2*(3-1)/4 | 2 3 1 - * 4 / У ЗПЗ немає дужок, і обчислення проходять дуже просто: 2 3 1 - 2 2 * 4 4 / 1 Але як перекласти даний вираз у ЗПЗ? По-перше нам потрібна функція/процедура, яка буде по порядку розбирати наш вираз на оператори та операнди (змінні та числа). Нам потрібно: Стек операторів (SA), та стек операндів(SB). (Стек - це структура даних, елементи якої зберігаються у порядку їх надходження, і видалення елементу дозволя.ться лише з вершини стеку, тобто видалити можна елемент, який надійшов останнім). Діємо за такими правилами: a) ЯКЩО на черзі операнд, ТО переміщуємо його у SB. б) ЯКЩО на черзі оператор (OP), ТО 1) ЯКЩО SA пустий, ТО переміщуємо OP у SA 2) ЯКЩО OP = '(' , ТО переміщуємо OP у SA 3) ЯКЩО OP = ')' , ТО ПОКИ на вершині SA не '(' , "виносимо" оператор з вершини SA. Виділяєм '(' з SA 4) ЯКЩО OP = (+,-,*,/) ТО ПОКИ (SA не пустий) та (пріорітет оператора на вершині SA >= пріорітету OP), "виносимо" оператор з вершини SA. переміщуємо OP у SA в) ЯКЩО кінець виразу, ТО ПОКИ SA не пустий, "виносимо" оператор з вершини SA. Оператори мають такий пріорітет: ( 0 +,- 1 *,/ 2 Процедура "виносимо" , бере оператор на вершині SA та у SB проводить арифметичну дію, відповідно до цього оператору, після чого видаляє оператор з вершини SA. Розглянемо приклад: 2*(3+4*5-7)/8 ---------- Крок1 Початок SA: SB: ---------- Крок2 Правило а SA: SB: 2 ---------- Крок3 Правило б1 SA: * SB: 2 ---------- Крок4 Правило б2 SA: * ( SB: 2 ---------- Крок5 Правило а SA: * ( SB: 2 3 ---------- Крок6 Правило б4 SA: * ( + SB: 2 3 ---------- Крок7 Правило а SA: * ( + SB: 2 3 4 ---------- Крок8 Правило б4 SA: * ( + * SB: 2 3 4 ---------- Крок9 Правило а SA: * ( + * SB: 2 3 4 5 ---------- Крок10 Правило б4 * та + були "винесені" (4*5=20, 3 + 20 = 23 SA: * ( - SB: 2 23 ---------- Крок11 Правило а SA: * ( - SB: 2 23 7 ---------- Крок12 Правило б4 - був "винесений", ( видалена з SA SA: * SB: 2 16 ---------- Крок13 Правило б4 * був "винесений", / SA: / SB: 32 ---------- Крок14 Правило а SA: / SB: 32 8 ---------- Крок14 Правило в SA: SB: 4 Відповідь: 2*(3+4*5-7)/8 = 4 Особливого випадку потребують такі вирази як: -7*5 3*(-23) У них використовується так званий, унарний мінус, він діє лише для одного операнду а не для двох! Мінус унарний, якщо він стоїть на початку виразу, або після відкриваючої дужки) Унарний мінус має приорітет вищий за '*','/' тобто 3. При "винесенні" унарний мінус лише змінює знак операнду на вершині SB. Опрацювання змінних не складне, у SB заноситься її значення. Другим методом є рекурсивний синтаксичний аналізатор: Усі вирази мови CALC описуються граматикою, яка у формі Бекуса-Наура (БНФ) має наступний вигляд Expr := Term { ('+' | '-') Term } Term := Factor { ('*' | '/' ) Factor } Factor := Var | Number | '(' Expr ')' Var := 'A' | 'B' | 'C' | ... | 'Z' Number := Digit | Digit Number Digit := '0' | '1' | ... | '9' {} - означає повторення 0 або більше разів | - означає АБО Відповідно до вищенаведеної граматики дуже просто написати програму обчислення виразів мови CALC. У другому випадку програма буде меншою ніж у першому, але й перший спосіб має певні свої переваги. ---------------------------------------------------------------------- Задача №3 Можливо декому з учасників відома гра "Нім". У ній є N купок, в кожній міститься деяка кількість камінців. На кожному ході, гравець може обрати певну купку, і забрати з неї будь-яку ненульову кількіть каміння. Виграє той хто забере останній камінь. Наша задача, є частковим випадком гри "Нім". Є N купок, по N-2 камінців в кожній. У грі "Нім", позиції де A1 xor A2 xor A3 xor ... xor An-1 xor An = 0 є програшними для того, хто робить хід. На кожному кроці, потрібно перевести суперника у позицію, де вищенаведений вираз = 0. Але те, що у нашій грі на початку кожен рядок (купка) має однакову кількість клітинок(камінців), то можливо ця задача є простішою ніж гра "Нім" (принаймні не складнішою, так як вміючи грати в "Нім" ми зможемо грати й в "Крижинки") Якщо уважно придивитись на ігрове поле, то можна помітити симетрію: Якщо N парне, то даємо супернику право першого ходу, та "копіюємо" його ходи, тобто граємо симетрично відносно центральної вертикалі ігрового поля. Якщо N непарне, то робимо перший хід у середньому стовпчику, та "копіюємо" ходи суперника відносно цього стовпчика. Отже якщо суперних походив на P клітино у першому рядку, ходимо на P клітинок в останньому, якщо в другому, то ходимо в передостанньому, і т.д. Для того, щоб укластися у часове обмеження, потрібно ефективно визначати кінець гри. Є принаймні 2 підходи: 1) Зберігати положення крижинок ICE та Діда Мороза у масивах, та після кожного ходу, який призводить до "зустрічі" крижинки ICE та Діда Мороза, зменшувати лічильник вільних рядків. 2) Після кожного ходу зменшувати лічильник вільних клітинок (їх всього N*(N-2)) Обидва методи вкладуються в часове обмеження, але 2-й простіший та елегантніший. Програма має вийти дуже маленькою. Значна частина учасників не проходила тести 6,7,8 за однієї причини: у цих тестах розмір дошки 301, 998, 999. І загальна кількість вільних клітинок на початку гри виходить за межі integer. Тому в даному випадку потрібно було використовувати тип даних longint. --------------------------------------------------------------------