Всем привет!
Совсем скоро, 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: Добавил Могилевскую область.