Всем привет!
Совсем скоро, 13-14 января, пройдут основные туры областной олимпиады в Беларуси.
Предлагаю после туров обсуждать задачи и делиться результатами здесь!
GL && HF!
UPD: Ну что, как вам задачки первого тура?
Краткие соображения по решению задач (SPOILER) :
1. Тут все ясно, просто массив на сто элементов.
2. Перебираем R до корня, затем бинарным поиском ищем максимальное C. Не забыть лонги.
3. Два указателя + добавить спереди нулей, чтобы числа были одной длины. Не забыть при выводе убрать лидирующие нули. Не забыть лонги [2].
4. Дп по дереву: dp[ver][0] — максимальный путь до какого-либо из листов + мы не снимали налог ни с одной дороги, за которые отвечает вершина ver. dp[ver][1] — то же самое, только мы уже сняли один налог. Затем просто два максимума по детям dp[ver][1] и dp[ver][0].
Надеюсь это должно работать =)
Условия первого дня здесь.
Второй тур завершен. Мне задачи понравились :)
Опять соображения :
1. Два указателя на концы строк и погнали.
2. Раскладываем на простые множители и каждый множитель доводим до степени, кратной трем. Это и будет ответ.
3. Посчитаем H[i][j] — количество спичек на одинаковых местах у чисел i и j.
Затем посчитаем такую динамику : dp[len][sum][eq], где len — длина префикса, который рассмотрели, sum — сумма спичек, которую набрали, eq — сколько на нормальных местах стоит, что не пришлось менять. Затем ответом будет просто сумма по всем dp[n][mySum][x], где mySum — x <= k. Ограничение по памяти не позволяло считать такую дп, поэтому считаем просто по слоям.
4. Первые 8 тестов — динамика за N^2 * K. Где dp[len][used] — минимальная стоимость, если мы уже набрали used групп, и последняя группа закончилась в позиции len. Предварительно нужно отсортить массив. 9-й тест — просто костыльный, там все тройки в инпуте. А в 10й написал жадность — сделал группы макс размера и следовательно остались ещё группы. Тогда уменьшаю самую большую группу и добавляю новую или добавляю в старую, но меньшего размера. Улучшаем пока улучшается.
Делитесь своими идеями и решениями, а я буду надеяться, что это все зайдет! =)
Кидайте резы по вашим областям мне в лс.
UPD: Есть резы Брестской, г. Минска, Гомельской области и Лицея БГУ и , скидывайте резы свои, жду!
Неполные результаты : Link.
UPD: Добавил Могилевскую область.
Всем Удачки ребзя!=)
Выложите задачки первого тура, пожалуйста, если он уже закончился.
Я думаю, ни у кого нет электронного варианта.
можно и фоточки, главное чтоб текст можно было разобрать
Уже добавил.
неправильная ссылка
Можете мою версию посмотреть ;)
UPD
Тур 1
Тур 2
спасибо)
ИМХО, это пустая трата времени. Но тоже работает =)
Тэги)
Больше, чем все задачи вместе взятые, мне понравилась наша любимая, дорогая Лицейская тестирующая система, которая во время 1-го тура принимала чтение данных с консоли, а после тура, естественно, перестала.
Обожаю её!
А ты ручками не тестил?
В следующем году будешь сдавать без нее
Ты скажи спасибо, что тебе на второй день за это баллы не сняли!
В 4 задаче 2 дня можно проще. Сначала отсортируем работников по возрастанию a[i]. После этого будем пытаться набрать максимум людей в очередной проект(это количество будет равно минимуму из a[i], участвующих в проекте) Далее, до тех пор, пока мы можем это делать, будем находить проект с наибольшим количеством людей (1) и проект с наименьшим(2). После этого отправим одного человека из 1 в 2. Это можно сделать т.к финальное количество людей в 2 не будет превосходить 1. Продолжим делать это до тех пор, пока разница между наибольшим и наименьшим количеством не знанет <=1. Это значит, что мы нашли ответ.
Решение работает примерно за n^2(10 тест считало 30сек) и берет 100 баллов.
Когда будут общие результаты по областям?
Когда все скинут =)
У кого какие значения минимальных площадей в 4-ой задаче 2-ого дня получились?
Сколько картошечки набрал автор? :)
Один балл — одна картофелина! :o)
Почти у всей Брестской области слетела 3 таска первого дня из-за лишнего пробела в конце. У кого-то еще была такая проблема?
В условии задачи не оговорено количество пробелов между (до и после чисел), более того в описании числа записаны через запятую (и согласно условию и такой вывод был бы правильным). Так что это повод для апелляции.
Писали аппеляцию по этому поводу ~7 человек. Все были отклонены.
в минской области та же фигня с тестами.
у нас допилили тестер, все прошло.
хотя у Сазановича и так проходило)
Известны ли результаты каких-нибудь областей(отдельно)?
В Могилеве нет 800( 795.
Юра, может скинешь результаты областей по отдельности, а потом, когда будут все, общие?
По Гомельской уже есть на dl-ке, вот
Юра, можешь выложить хотя бы то, что есть?
Если можно поправьте в результатах имя 13 места на "Камеко Валерий".