НОВ  БЪЛГАРСКИ  УНИВЕРСИТЕТ

Департамент Информатика

INF297 Програмиране за напреднали ІІ, Състезание_1, 30.03.2006

    Задача B. Числа на Фибоначи

    Всички знаем редицата на Фибоначи: F(0) = F(1) = 1 и F(i) = F(i -1) + F(i - 2) за i > 1.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

    Ще дефинираме обобщена редица на Фибоначи по следния начин: F(i) = F(i - k1) + F(i - k2), където  k1 < k2 са цели положителни числа. Разбира се, за да получим редица при дадени k1 и k2 трябва да зададем първите й k2 члена (положителни числа), т.е. F(0), F(1), ..., F(k2 -1). За да пресметнем  член на редицата със зададен номер, не винаги е необходимо да знаем всички елементи на тази редица. Например при k1 =3 и  k2 = 5, елементът с номер 10 можем да пресметнем, ако са известни  F(0), F(2) и F(4). Да се напише програма b.exe, която определя дали дадено число е член на обобщена редица на Фибоначи със зададени k1 и k2.

    От стандартния вход се въвеждат числата k1 и k2 на един ред, отделени с поне един интервал. На следващия ред е числото n, което задава броя на членовете на редицата, намиращи се на следващите n реда. Тези членове са във формат: номер, интервал, стойност. На следващия ред е число m - брой на числата, за които трябва да се определи дали са членове (до петдесети) на така дефинираната обобщена редица на Фибоначи. Следват самите числа,  разделител интервал. Така описаната структура на входа се повтаря и входът завършва с 0 0.

    На стандартния изход да се изведат m реда, съответващи на m-те числа от входа. Всеки ред трябва да бъде yes, ако съответното число е от обобщената редица на Фибоначи (до петдесетия член), no - ако не е и unknown - ако не може да се определи (поради надостиг на данни за редицата). Между примерите се оставя по един празен ред.

    Пример.

Вход
1 2
2
0 1
1 1
3
21 55 10
3 5
3
0 1
2 2
4 4
5
6 3 10 1 5
0 0

Изход
yes
yes
no

yes

yes
unknown
yes
unknown