Завершилась Седьмая командная олимпиада. Ссылка на задачи. Как решать B, D и F. Заранее спасибо.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.09.2024 12:10:21 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
Подскажите почему в Н (http://pastebin.com/Z7UQ0UiK) я ошибся.
Контрпример: k = 40 Ваш ответ 6 6 Правильно 5 8
А как же тогда решать?
перебрать
спасибо, та я подумав понял. Почему-то на контесте не захотел перебирать)
задача В: полный перебор , кажется проходит...
задача F: если сделать два одинаковых хода то ничего не изменится, поэтому можно перебрать все возможные варианты (их 2^16=65536) так как влияет только четность...
задача D: не знаю см не решил((
какой перебор у тебя в B проходит? за (n + m) * kn ?
у меня за 0.8c прошло (n^k)*m. правда еще отсечение, что если где то уже 2 соединенные одного цвета, то дальше в рекурсии не идем. но может и так бы прошло.
не понимаю, а что ты перебираешь?
Можно еще сократить перебор (приблизительно в 8 раз) тем, что зафиксировать цвет первой вершины, а потом умножить ответ на количество цветов.
И еще, наверное, он kn, а не nk.
я сначала писал рекурсию на c++ не зашло по времени, потом что-то химичил, потратил 5 попыток, всё равно по времени летело, потом то же самое,что и посылал переписал на pascal зашло за 0.46. Я думал c++ работает быстрее паскаля, а тут такая лажа, кто может это объяснить?
вообще это вполне мог быть рантайм, он на этом сайте часто ловится как ТЛ.
В D, как я понимаю можно придумать правило что бы переходить от n к n+1(просто вставкой в какое то место и это как то связано со степенью 2ки ), но не додумал. Тоже интересно узнать решение.
Расскажите, пожалуйста, кто нибудь C и G. Как делать G с таким ограничением? я только за корень знаю и то не уверен, что верно.
D: пусть у нас есть корректная перестановка P с числами [0..n-1]. Тогда перестановка P*2 + P*2+1 тоже будет корректна. В каждой половине плохих троек нет, во всём же массиве тоже нет, т.к. если берём i и j слева, а k справа, то разнича p[i]-p[j] чётная, а p[j]-p[k] нет. Начинаем с массива P = [0], потом просто выводим элементы меньшие n.
Как решать 3ю и предпоследнюю???
А чего они задачи с Тимуса тырят?
это нормально для асмп, все об этом знают, и контест будет интересен, если ты до этого не решал задачи олимпиады, да и вообще, вроде задачи всех олимпиад на асмп берутся с других олимпиад
В H такая идея: идем по разности H-W(от 0 до k-1). Очевидно, что нужно взять максимальный h такой, чтобы h*(h+d)<=k. h находим бинпоиском. Или еще можно 2 указателя по разности h-w и h.
можно немного по другому, пусть h<=w. тогда h<=k^0.5. переберём все значения h, и для каждого h все допустимые значения w,и всегда будем пробовать улучшать ответ. Сложность где-то O(k).
А эти задачи где сейчас сдавать можно?В архиве нет.
нельзя(
повбивай в гугле, может найдёшь откуда они. Точно могу сказать, что последня есть на dl.gsu.by областная республиканчкая олимпиада 2006 год!