| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
Кто их сделал, поясните решение. Я так полагаю, тут какое-то хитрое решение с помощью теории вероятности.
Задачу E я решил, отправляя различные случайные алгоритмы. Прошел следующий:
Дотрагиваться до клеток с 1 по n. Затем обратно с n до 1.
Очень интересно решение задачи F.
F) отметим точками на прямой места где может быть этот многогранник и после каждого хода будем обновлять эти отмеченные точки. Дальше вкратце я делал так: есть два типа отрезков - 1) полностью заполненные точками 2) заполненные точками через 1 (типа 1, 3, 5,...). После каждого хода мы обновляем эти отрезки они увеличиваются в обе стороны на 1 (нужно следить за краями чтобы не вылезли за пределы 1 и n), потом пытаемся обработать соседние отрезки т.е. сделать так чтобы они не пересекались (по возможности объединяем соседние отрезки в один отрезок), а потом удаляем точку которую выбрал маг текущем ходом т.е. выбираем соотвествующий отрезок и делим его пополам если нужно. Самое главное то, что всегда отрезков будет не много. Изначально всего 1 отрезок первого типа.
Если куб находится на постаменте с нечетным номером, то достачно проверять:
1, 2 , 3, ... , n - постаменты.
Если же за первые N проверок так и не нашли куб, то он находился на постаменте с четным номером, тогда если после N проверок мы уже знаем четный или нечетный номер постамента, где находится куб.
Если нечетный, то снова проверяем от 1 до n, иначе проверяем от 2 до n.
Задача F:
Я хранил два множества, где может находится куб на текущий момент.
Одно множество для тех позиций, в которой мог оказаться куб, если он находится на четной позиции в самом начале, а другое множество если куб находился в начале на нечетной позиции.
При каждом касании постамента, изменял эти множества. Т.е. удалял из нужного множества номер постамента. Т.к. множества хранил отрезками, то еще для каждого отрезка нужно увеличить правую на границу на 1, а левую на 1 уменьшить. Если отрезки склеивать, то кол-во отрезков для множества, не превышает 2, если я не ошибаюсь :) Отрезок хранит множество всегда с шагом 2.
Если в конце оба множества пустые, то YES иначе NO
http://codeforces.me/blog/entry/292
там вроде как оптимальное решение за (n-2)*2 ходов (для n>2)
например
2,3 .. n-1, n-1, n-2, .. 2
Кто нить может объяснить алогритм для задачи J.
Что придумывали - ломалось на 6 тесте (
пусть i - номер ученика в круге. a[i] - кем он хочет стать. Тогда надо начинать с ученика с номером (i-a[i]+1+n)%n.
i от 0 до n-1.
кстати людей которые сдали E, но не сдали F полно, а вот наоборот ни одного :)