Вроде ещё не было создано темы. Предлагаю здесь обсудить задачи.
№ | Пользователь | Рейтинг |
---|---|---|
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 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Вроде ещё не было создано темы. Предлагаю здесь обсудить задачи.
Название |
---|
Меня интересует задача C. Какой ответ будет для теста?
-1 я так понимаю.
А Вы сдали эту задачу? А то, кажется, я тогда могу апеллировать, ибо с моей точки зрения, в условии двусмысленность.
Я задал клар жюри по этому поводу (уже после своего отыгрыша, где мне повезло угадать). Никто так и не ответил.
Тут просят не обсуждать, сейчас отвечу в личку.
Ошибся, я, видимо, тоже правильно угадал.
Как решать D,E?
Я не решил E, но кажется это просто взлом RSA.
Я вот так решал: http://acm.timus.ru/forum/thread.aspx?id=6067&upd=632776183310665000 :D
D — отсортируем точки по углу и динамика — какие 2 последние точки являются вершинами, в итоге куб
Е — разложим на множетели, найдем private key, возведем в степень
А как в задачах типа D "замыкать" эту динамику? Нам же первая точка вроде бы тоже важна? Или мы ее просто перебираем?
UPD. Расскажите все равно, как надо это правильно кодить, если бы у точек были возможны любые координаты.
Там y ≥ 1, а точка 0, 0 — вершина
Okay
Если я не ошибаюсь, то неважна. Там Y во входных данных строго положительный, так что все выбранные точки лежат в одной полуплоскости. Так как нам еще обязательно надо взять (0, 0), то стоимость взятия конечных точек не зависят от взятия первой, только от последней взятой.
Можете выложить код по Д или поподробнее рассказать, как делать переход, если не сложно?
Подробнее: отсортируем точки по углу относительно (0, 0). Динамика dp[i][j] (j < i) — максимальная стоимость, которую можно получить, если взяты i-ая точка, j-ая точка, какие-то из точек до j и не взята никакая точка между i и j. То есть i и j — две последние взятые точки. Внешний цикл — перебираем i. Обозначим i-ую точку как А. Внутри этого цикла есть два варианта:
Ответом будет max(dp[i][j])
Насчет задачи C. Точно такая же задача идет на VIII Открытой олимпиаде школьников по программированию. Может не следует её обсуждать?
Когда она закончится?
15 января, если не продлят. Могу, кто захочет, решение в личку рассказать.
Да решение я вроде могу придумать. Просто для меня С — одна сплошная неоднозначность, что спрашивали-то? Фраза "действуют оптимально" при непонятных целях мне непонятна.
Мне интересно, а ты можешь придумать два различных (разумных) понимания фразы "действуют оптимально" таких, что для некоторого теста ответы будут отличаться?
Для диверсанта:
Оптимально 1: Если пройти не можешь, то бегать как можно дольше Оптимально 2: Просто бежать к выходу любым из кратчайших путей.
Уровень — замкнутая окружность достаточной длины. Единственный охранник начинает на выходе, диверсант — на противоположной точке круга.
Гарантированно пройти диверсант не может, потому что охранник уже у выхода и может просто ждать там. Охранник форсированно поймать диверсанта тоже не может, потому что можно бегать по кругу.
Действительно, надо было в условии вместо "Выведите одно целое число: -1, если активист будет пойман, и минимальное время, за которое активист выйдет с завода, в противном случае." написать что-нибудь в таком духе "Если активист сможет сбежать, выведите минимальное время, за которое активист выйдет с завода, в противном случае выведите -1."
Тогда вроде бы уже будет однозначно.
Спасибо за разъяснение, так действительно понятней, что спрашивали и как решать.
А почему же анонс никто не написал?:( Я вот забыл про раунд:(