Закончился очередной этап.
Хотелось бы узнать решения задач A, D, E .
Хотелось бы узнать решения задач A, D, E .
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Если третий параметр 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.