Блог пользователя ShyngyS

Жаутыковская олимпиада 2011, Чет-нечет
Автор ShyngyS, 10 лет назад, По-русски

Здравствуйте , можете помочь с этой задачей (не могу решить) http://informatics.mccme.ru/mod/statements/view3.php?id=9170&chapterid=111879#1 Спасибо !!!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Формулка скорее всего. Попробуй найти закономерность

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Там есть закономерность.Я использовал длинку с бинпоиском.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Здесь можно найти информацию об этой последовательности.

→ Ответить
»
10 лет назад, # |
← Rev. 11   Проголосовать: нравится +3 Проголосовать: не нравится

Последовательность выглядит так:

a[0] = 0
if (a[id - 1] is square) a[id] = a[id - 1] + 1  
else a[id] = a[id - 1] + 2

Очевидно, что ответ это (2 * N — S), где S — количество квадратов до a[N].
S = X + 1, где X = максимальное X что X2 <  = a[N]

Надо найти X, делаем это бинпоиском.
Допустим у нас какое то X, хотим проверить X^2 <= a[N].
Если X подходит то X-1 тоже подходит, значит у нас ответ для X-1 это 2*N-(X-1)+1 (делаем + поскольку S=X-1+1).

X^2 <= 2*N-X
X^2+X <= 2*N
X(X+1) <= 2*N

Код маленький, если не учитывать длинную арифметику.

P.S. Было бы неплохо, если бы в редактировании был предпросмотр.

→ Ответить