Yury_Bandarchuk's blog

By Yury_Bandarchuk, 10 years ago, In Russian

Всем привет!

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

  • Vote: I like it
  • +58
  • Vote: I do not like it