Понеділок, 18.12.2017, 02:28
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Меню сайту
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Форма входу
 Розбір задач
Задача А
Ця задача може бути розв'язана пошуком в ширину.
Почнемо з заданого стану. Якщо кубик (квадратик) уже складений, то відповідь 0. Інакше знайдемо всі стани квадратика, які можна утворити з заданого за 1 хід. Це не більше 12-ти різних станів. Розмістимо їх в чергу.
Тепер розглянемо по черзі утворені стани. Якщо котрийсь з них є фінальним (квадратик складено), то відповідь 1. Якщо ні, і ми ще не розглядали такого стану, то утворимо з нього 12 нових станів і розмістимо їх в новій черзі (черзі другого покоління). В результаті в черзі другого покоління опиниться не більше 144-х різних станів.
Тепер розглянемо по черзі стани другого покоління. Якщо отримано фінальний стан, то відповідь 2. Інакше будуємо стани третього покоління і т.д.
Для того, щоб не розглядати кожен з станів більше одного разу, у випадку, коли ми можемо прийти до нього різними шляхами, введемо множину розглянутих станів. Будемо додавати до неї стан, коли він розглядається вперше (був відсутній у множині), та не будемо розглядати новоутворений стан, якщо він вже присутній у цій множині.
Для прискорення порівняння та утворення станів, вони представлені в програмі як 18-тибітні числа, по 2 біти на одну кольорову клітинку. Утворення нових станів представлено у вигляді 12-ти функцій, що виконують бітові операції над 18-тибітними числами.

Задача В
Візьмемо одну з точок (x0, y0). Для всіх інших точок (xi, yi) знайдемо нахил прямих, що проходять через точки (x0, y0) та (xi, yi). Якщо (x0, y0) та деякі з точок (xi, yi) лежать на одній прямій, то й нахил відповідних прямих буде однаковим. Щоб визначити, яка найбільша кількість точок серед (xi, yi) лежить на одній прямій, що проходить через них та точку (x0, y0), достатньо визначити, яка найбільша кількість відповідних прямих має однаковий нахил.
Нахил прямої можна представити у вигляді одного числа, наприклад -- котангенса кута утвореного прямою та віссю X. Відповідне значення дорівнює (xi - x0) / (yi - y0). Таким чином задача зводиться до знаходження максимальної кількості однакових чисел у заданому масиві. Це можна зробити відсортувавши массив. Таким чином однакові числа опиняться поруч одне з одним. Потім достатньо переглянути масив один раз, щоб знайти найдовшу послідовність з однакових чисел.
Тепер ми маємо розв'язок за умови, що маршрут проходитиме через точку (x0, y0). Оскільки це не обов'язково так, потрібно послідовно взяти в якості точки (x0, y0) кожну з заданих точок і виконати над нею усі наведені вище дії.
Задля уникнення помилок, пов'язаних з точністю обчислень, нахил прямої представлений у вигляді двох цілих чисел: чисельника та знаменника, а не у вигляді числа з плаваючою комою. Для того, щоб у всіх прямих з однаковим нахилом чисельник та знаменник дробу були однаковими, дріб повинен бути нескоротним, з додатним знаменником. Якщо знаменник дорівнює 0, то чисельник повинен бути додатнім. Тому для отримання нахилу прямої береться (xi - x0) в якості чисельника, (yi - y0) в якості знаменника, отриманий дріб ділиться на їх найбільший спільний дільник та домножується на -1 за необхідності.
Додатково слід врахувати, що точки, які співпадають з точкою (x0, y0), завжди лежать на одній прямій з точкою (x0, y0) та будь-якою з точок (xi, yi). Такі точки дають прямі з нахилом 0 / 0.

Задача С
Ця задача може бути розв'язана шляхом виконання ряду операцій над множинами.
Спочатку знайдемо батьків заданої особи. Потім знайдемо їх батьків. Це чотири особи. Тепер знайдемо дітей цих чотирьох осіб. Це будуть дядьки, тітки та батьки заданої особи. Заберемо з цієї множини батьків. Знайдемо всіх дітей тих, що лишилися. Це й будуть двоюрідні брати та сестри.
Cousins(P) = Children(Children(Parents(Parents(P))) - Parents(P))

Copyright MyCorp © 2017
Пошук
Календар
«  Грудень 2017  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728293031
Архів записів
Друзі сайту
Обдаровані діти

Хмельницькі олімпіади

НМЦ ІКТ і ДН

Портал ХОІППО

Безкоштовний конструктор сайтів - uCoz