Всем привет!
9 ноября состоится интернет-тур Всероссийской Командной Олимпиады Школьников по Программированию.
Пробный тур проводится с 18-00, 5 ноября 2014 года до 18-00, 8 ноября 2014 года.
Предлагаю после контеста обсудить задачи.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:50:13
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:50:13
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 17:44:47 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Всё-таки это отборочный интернет-тур к ВКОШП
http://neerc.ifmo.ru/school/information/problems-spb-2014.pdf
ссылка на условия.
как решать С и К?
K -> http://pastie.org/9707251 C -> http://pastie.org/9707254
Спасибо. И еще, я один наркоман писал на F разложение на множители и 2 в степени количества множителей?
нет)) http://pastie.org/9707274
Нет.) Доказыватся, что делителей будет O(log N), а именно — по десять на число (2 * 3 * 5 * 7...)
Мы так прикинули, их всего 15 в сумме может быть, просто многие сдавали, при чем так-то не с неплохой скоростью сдавали, вот мы и подумали, мб есть решение полегче
(Делитель A) * (Делитель B) = (Делитель A * B)
А почему бы в К не написать нечто следующее.
1)Рассмотрим позиции, в которые может пойти второй игрок и победить. Если их хотя бы 2, то мы проиграли, если одна, то ходим туда, если их 0, то перебираем клетку, куда ходим.
2)Перебираем ход второго игрока, считая, что он ходит в некоторой окрестности позиции, куда мы поставили крестик.
3)Перебираем наш второй ход, опять же, в небольшой окрестности позиции, куда мы походили.
В качестве окрестности можно, видимо, взять квадратик 11*11, должно уложиться в ТЛ. Можно еще, пожалуй, соптимизировать так — перебирать только те позиции первым ходом, походив в которые мы сможем победить, если второй нам не будет мешать(делаем два хода подряд). Таких позиций не может быть уж слишком много
Если их хотя бы 2, то мы проигралиПочему? Мы ведь можем первым ходом походить и выиграть.
К. Добавляем по несколько клеток слева, справа, сверху и снизу (я добавил 20 клеток) и отмечаем их '.'.
Напишем функцию win(ch) => количество позиций что если в них поставить ch (X или 0), то можно выиграть.
Если win('X') > 0 то первый игрок может выиграть сразу, следовательно ответ равен win('X').
Иначе, смотрим win('0'). Если позиций, где второй игрок выиграет, больше одного, то мы проиграем в любом случаи. (мы закроем одну позицию, но следующий ход он выиграет).
Если win('0') равен одному, то мы закрываем эту позицию, а следующий ход второй игрок не может выиграть. Ему будет оптимальнее закрыть один наш выигрышный ход, следовательно ответ win('X') — 1.
Иначе, перебираем клетку куда мы ставим 'X'. Если после того, как мы поставили Х на эту клетку, на поле выигрышных клеток стало больше одного, то увеличиваем ответ.
P.S. Функию win(ch) надо реализовать не на всем поле, а на каком то подпрямоугольнике.
Эх...
Была такая идея, только все пытался решить "полегче" — динамикой, оказалось нифига не легче и нифига не правильно.
К 2 часам решили 7 задач, и остальные 3 часа пытался запихать такое решение. "WA 60". И почему-то сайт работал только через анонимайзер.
Вывод 1: Не зацикливаться на одной задаче. Вывод 2: Убогий интернет до добра не доводит.
Если win('0') равен одному, то мы закрываем эту позицию, а следующий ход второй игрок не может выиграть. Ему будет оптимальнее закрыть один наш выигрышный ход, следовательно ответ win('X') — 1.
Если win('0') равен одному, ответ-то единица: мы считаем первые ходы, а не вторые.
А как насчет результатов , кто куда прошел ????
Из Санкт-Петербурга прошло 11 команд (9 команд решили 7 задач (результаты Спб)). Логично предположить, что из интернет-тура прошли команды с 7 задачами, возможно несколько команд с 6.
Хотелось бы ссылку на официальные источники. Нашёл