Закончился очередной этап.
Хотелось бы узнать решения задач A, D, E .
Хотелось бы узнать решения задач A, D, E .
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 10:27:02 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Если третий параметр 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.