ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1133. Последовательность Фибоначчи

wa15
Послано Experimenter 9 сен 2008 21:04
i use binsearch and have wa 15..

i found this test
1 1 5 1 2
what's answer? is this test correct?
Re: wa15
Послано Denis Koshman 9 сен 2008 23:50
My AC solution replies 1. I don't know if this test is correct as I solved this problem loooong ago.
Re: wa15
Послано Sandello 1 ноя 2008 04:05
this test is incorrect because answer for it is -(1/3), it's not integer number

1st elem - 1
2nd elem - -1/3
3rd elem - 2/3
4th elem - 1/3
5th elem - 1

Edited by author 01.11.2008 04:06
Re: wa15
Послано Erko 3 янв 2009 19:03
i use binsearch and have wa 15..
any hints plz
Re: wa15
Послано Petar 1 апр 2011 15:09
The sequence is {1 0 1 0 1}

Edited by author 01.04.2011 15:39
Re: wa15
Послано Tranvick 31 янв 2012 14:53
It's wrong. If f[2]=0, the sequence is {1 0 1 1 2}.
Re: wa15
Послано Alexey Dergunov [Samara SAU] 15 май 2012 23:02
How to avoid WA 15
While calculating f[n] during another iteration of binary search, every time check if f[i] is out of [-2*10^9, 2*10^9]. If it is, immediately break calculation cycle, update binary search interval and start another its iteration.
Re: wa15
Послано Chitanda Eru 4 ноя 2013 22:07
I used formula and a C++ type long long, but still somehow managed to get WA 15. Even though i got around it by calculating in Zp (where p is a prime number bigger than 4 * 10^9), it still blows up my mind how it's possible to overflow long long without violating the statement. Such a tricky test, i'd like to see it.
Re: wa15
Послано Leonid 5 ноя 2013 18:43
Some tests:

test: -36 1680987685 37 1439530908 1
ans: 12

test: 42 1330344015 -38 -1330344015 30
ans: 4131543

test: -459 0 245 0 999
ans: 0

Edited by author 05.11.2013 18:43

Edited by author 05.11.2013 18:47