Областная олимпиада в Беларуси 2016.
Difference between ru1 and ru2, changed 891 character(s)
Всем привет!↵

Ну что же, вот и пришел сезон личных олимпиад в Беларуси. Совсем скоро, 12-13 января по всей Беларуси будет проходить областная олимпиада по информатике.↵

Предлагаю в этом посте выкладывать условия, обсуждать задачи и прочее и прочее. Я же от себя после туров буду делиться своими идеями по задачам. ↵

В прошлом году тоже было что-то похожее, кому интересно — вот [ссылка](http://codeforces.me/blog/entry/15748).↵

Good luck && Have fun!


Day 1.↵

1. Тупая реализация! Главное, аккуратно чекать случай, когда есть ### и выстрел в центр.↵

2. A — массив ответ. A[1] = y. Дальше просто добавляем единичные биты в свободные позиции. Проверяем, что набралось N элементов — выводим ответ, иначе -1.↵

3. Дп F[pref] — ответ для префикса pref. left[x] — левая граница числа x, right[x] — правая соответственно, cnt[x] — количество. Пересчет↵
 ↵
   - f[pref] = f[pref — 1]↵
    - если pref == right[a[pref]], то f[pref] = max(f[pref], f[left[a[pref]] — 1] + cnt[a[pref]]↵

Ответ лежит в f[n].↵

4. Брут за N * K^2 довольно простой, фиксим позицию которая так и останется стоять (это N * K) а дальше смотрим как нужно повернуть минимально остальные диски. ↵

По ограничению из условия — это 60. ↵

Итого — 360 очень простых баллов.↵

Кто знает как решать 4-ую на сто?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian Yury_Bandarchuk 2016-01-13 15:11:07 947
ru2 Russian Yury_Bandarchuk 2016-01-12 15:31:49 891
ru1 Russian Yury_Bandarchuk 2016-01-11 17:02:31 501 Первая редакция (опубликовано)