Завершилась Седьмая командная олимпиада. Ссылка на задачи. Как решать B, D и F. Заранее спасибо.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 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
Время на сервере: 24.11.2024 13:49:48 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Подскажите почему в Н (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 год!