Закончился очередной этап.
Хотелось бы узнать решения задач A, D, E .
Хотелось бы узнать решения задач A, D, E .
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 06:30:57 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Если третий параметр 0--ожерелье ещё цикл, то мы ничего не можем сделать кроме как разрезать его--переходим в f[i,3-j,1]. Иначе мы можем либо взять все алмазы и перейти из f[i,j,1] в f[i+1,j,0], либо взять из текущей ленты все кроме четырех, а потом четыре алмаза поделить пополам(это поможет нам закончить ход и вынудит противника закончить ход разрезом следующего ожерелья), то есть переход в f[i+1,3-j,0]
Ожерелья сортим по их длине по возрастанию(точно не могу доказать почему так, так выгодней для первого :) )
http://www.codeforces.ru/blog/entry/337
Решение простое, но главное правильно понять условие. Вот код:
http://pastebin.com/C1Mad9bx
В O - здесь надо для каждого отрезка найти уравнение прямой - коэффициенты a,b,c и нормазиловать их (поделить на общий НОД). Далее все точки разделить на открывающие отрезок и закрывающие отрезок. Запихаем их в отдельный массив и отсортируем по возрастанию x, y, а если точки равны, то первой идет закрывающая точка.
Заведем map, где будем хранить кол-во текущих открытых отрезков с соотв. коэффициентами. Я это сделал в виде:
map<pair<long long,pair<long long,long long> >,long long> mp;
Паиры - это a,b,c.
Далее идем по массиву. Получаем координаты a,b,c отрезка, к которому принадлежит данная точка.
Если точка открывающая, то прибавляем к итоговому ответу текущее кол-во отрезков с данными коэффициентами и увеличиваем кол-во отрезков в мапе на 1.
Если закрывающая, то уменьшаем кол-во отрезков в мапе на 1.
Все хранить в long long' ах.
Вот код:
http://pastebin.com/PKmX55vt
Вот на этой ссылке написано что-то про некие секторы и координаторов секторов. Это такие люди, ответственные за участников конкретного географического региона, и они посылают заявки непосредственно организаторам, я правильно понял? Где их найти, в таком случае?
Координатором может быть преподаватель кружка, если он есть. Координатор сектора нужен, например, чтобы все команды были в равных условиях (получили распечатанные условия вовремя, пользовались ровно одним компьютером, ...).
e-maxx, видимо, под впечатлением, даже добавил соответствующий пункт в конец статьи:
http://e-maxx.ru/algo/segment_tree
Т.е. надо придумать оффлайн-решение и навесить такую конструкцию. Как делать оффлайн вы же знаете, да?
Для каждого места создадим массив отрезков в течении которых данное место было свободно. Также в каждом таком массиве удалим отрезки которые содержатся в других отрезках из этого массива, и отсортируем все отрезки по возрастанию их начал. Теперь чтобы узнать можно ли проехать от станции a до b, сидя на месте s нужно в s-ом массиве найти (бинарным поиском) отрезок у которого начало самое близкое слева от a, а потом проверить, что b левее правого конца найденного отрезка (иначе проехать на месте s нельзя).
Чтобы решить исходную задачу т.е находить минимальное s можно создать дерево интервалов в вершинах которого будут массивы отсорченых отрезков (и лишние удалены) из массивов детей данной вершины. А в листьях просто массивы для соотв. мест. Ну и потом спуск по дереву, чтобы находить ответ. Сложность будет (log(s + m))^2 на 1 запрос.
Интересно, что такие посты не вызывают общественного раздражения)
Задача H кстати -- это задача H с Neerc 2006.