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

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Форма входу
 Розбір задач
Задача В
Рішення на 15-30 балів: Щоб знайти мінімальний час виходу із супермаркету, необхідно визначити, в які каси краще всього стати в чергу. Через невеликі обмеження тестів можна використати перебір. Розглянемо усі можливі комбінації із К кас (нам вигідно використати максимально допустиму кількість). Для кожного набору вже нескладно визначити шуканий час: чергове тістечко вигідніше за все пробити через ту касу, яка на даний момент звільняється раніше. Якщо таких кас кілька, то можна вибрати довільну. Відповіддю буде мінімальне із отриманих чисел.
Рішення на 30-60 балів: Так як хлопців у цьому випадку не менше чим кас, то достатньо розподілити тістечка по усіх касах. Ідея проста: добавляти тістечко в чергу тої каси, яка на даний момент звільняється раніше.
Розглянемо масив а із N елементів, де a[i] рівне часу, в який звільняється і-а каса на даний момент. Спочатку a[i] = Ai + Bi. Щоб рішення проходило великі тести другої групи, організуємо на а кучу, яка дозволяє брати мінімум за О(1) і змінювати елементи за O(log N). Добавляючи поточне тістечко в чергу мінімальної каси (можна вибрати довільну, якщо таких кілька), необхідно збільшити відповідний час. Після добавляння по одному P тістечок максимальне із a[i] і буде відповіддю. За рахунок використання кучі це рішення працює за O(Р log N), що допустимо при обмеженнях N, P ≤ 100 000.
Рішення на 100 балів:  основна ідея  рішення – двійковий пошук по відповіді.
Нехай пройшло рівно t одиниць часу. Навчимось визначати, чи зможуть школярі придбати до цього моменту часу Р товарів.
Спочатку для кожної каси підрахуємо кількість тістечок, які можна купити в ній по закінченню t одиниць часу (вся ця процедура займе O(N) операцій). Далі відсортуємо підрахунком каси по знайденій кількості товарів. Це сортування працює за час, пропорційний максимально можливому із значень, що сортуються. Але, в нашому випадку, не має сенсу розглядати числа, більші за Р-1. Дійсно, якщо в якійсь із кас можна купити не менше Р тістечок, то за час t хлопці гарантовано успіють. Тому сортування буде працювати за O(P). Залишилось вибрати К максимальних значень, просумувати їх, і якщо отримана сума буде більша чи рівна Р, то хлопці успіють купити усі тістечка до моменту часу t, інакше – ні. Сумарна складність цієї перевірки рівна O(N+P).
Для рішення залишається знайти мінімальний час, при якому хлопці успіють купити Р тістечок, методом бінарного пошуку. Таке рішення працює за O((N+P) log T), де Т – максимально можлива відповідь.
Можливі помилки:
- Використання LongInt замість Int64
- Ділення на 0: слід врахувати, що час обробки одного товару може бути рівним 0.

Задача С
Повний перебір набирав приблизно 20-30 балів. Дане рішення елементарне та не потребує пояснень.
Спеціальний набір тестів в приблизно 50 балів: тести в яких трикутники лежать на координатних осях. Дане рішення можна зробити зі складністю O((K + M) ∙ lg K).
Перше, треба знайти точки які належать опуклій оболонці та є «видимими» з точки (0,0). Ми можемо відповідати на кожен запит за час O(lg K), для цього будемо використовувати тернарний пошук (для пошуку перетину опуклої фігури і трикутника).
Повний розв’язок.
Авторський розв’язок використовує ідею «поділяй та володарюй». Спочатку відсортуємо точки за полярним кутом. Заведемо збалансоване бінарне дерево по всім точкам. В кожній вершині дерева будемо підтримувати інформацію про опуклу оболонку точок в вершині. Кожен трикутник буде розбитий на O(lg K) трикутників, кожен із яких охоплює вузол двійкового дерева. Таким чином, усередині кожного вузла потрібно лише порівняти точки з третьої стороною трикутника (та яка не містить початку координат). Для цього ми можемо використовувати бінарний пошук рішення з особливим випадком. Загально розв’язок працює O((K + M) ∙ lg2K.
Copyright MyCorp © 2017
Пошук
Календар
«  Жовтень 2017  »
ПнВтСрЧтПтСбНд
      1
2345678
9101112131415
16171819202122
23242526272829
3031
Архів записів
Друзі сайту
Обдаровані діти

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

НМЦ ІКТ і ДН

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

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