С 13 по 16 января проходила областная олимпиада по информатике. Предлагаю здесь делиться резами и обсуждать задачи:)
№ | Пользователь | Рейтинг |
---|---|---|
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 |
С 13 по 16 января проходила областная олимпиада по информатике. Предлагаю здесь делиться резами и обсуждать задачи:)
Название |
---|
как решать 3 второго дня на 100?
Пусть мы нашли прямоугольник, в котором столько же деревьев, сколько в оптимальном ответе. Понятно, что сверху он упирается в какой-то прямоугольник, т.к. в противном случае, сдвинем его вверх и улучшим ответ. Аналогичные рассуждения проведем и для сдвига влево. Теперь переберем пару прямоугольников и предполагаем, что наш ответ упирается в первый сверху/снизу, а во второй справа/слева. То есть у нас есть O(K^2) кандидатов на ответ. Перебираем их все и за O(K) считаем сколько в них деревьев. Итоговая сложность O(K^3).
спасибо я понял.
Интересно, в каком-нибудь из регионов 45% участников удалось набрать не менее 50% баллов?
скорее всего нет.
сколько набрал?)
кто-нибудь выложите условия олимпиады пожалуйста
Вряд ли кто из участников выложит. Разве что жюри. Просто архива нет. 17 января должны на http://dl.gsu.by/ выложить.
Как решать 4 первого тура на 100?
тут есть 3 случая. Если из кого либо числа извлекается квадратный корень то он ответ. так же если мы разложим число на простые множители до 10^6 и степень одного из них больше 1 то ответ этот простой делитель. дальше смотрим все пары и их нод. если нод не 1 то ответ будет наш нод. Почему можно смотреть делитель до миллиона. Ну так как простых делителей больших кубического корня будет строго меньше 3.
Проверять на квадрат нужно после деления на простые до 10^6.
да ты прав.
Спасибо, разобрался
Вот тут есть немного про задачи и их решения: http://tooruichii.wordpress.com/2014/01/16/regionals-2014/