TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

98.6% (70/71)

Submission's AC Ratio

40.4% (111/275)

Tags

Description

冒險由此開始
在一個雨疏風驟的夜晚,妁艷吃著棒棒糖撐著傘準備過馬路。
吸著棒棒糖的妁艷吸阿吸的~忽然一道炫目的閃光閃入了他的眼中。抬起頭往右一看,只見貌似車頭燈的東西發出了無比耀眼的光芒。
妁艷立即以反射的速度按出了”↑↑↓↓←→←→BA”!
可惜閃光越來越近,仍不見有英雄來相救,妁艷就這樣仆街了……

「吃東西囉~來妁艷起來吃東西囉~」甜美的聲音在妁艷耳邊繚繞著。
「唔…唔…唔……」妁艷勉強的睜開了眼睛,想說自己到底是在天堂還是哪裡……

吃完東西後,妁艷的HP跟MP回復了滿點!這時他才知道原來剛剛他根本沒被撞到,而是因為過於驚嚇而昏倒了……雖然妁艷覺得在吃完東西之後他已經完全康復了,可是護士姊姊依然堅持要做些檢查……

只見護士拿出了一疊卡片,分別寫著「1、2、3、5、8……」各有一張。
妁艷一看,毫不猶豫就說「這不就費氏數列嗎!?」
原來護士是想測試看看控制傳說中的(咳~)的大腦運作是否正常,所以要測試看看妁艷是否因為過度的驚嚇導致腦部的受創,更甚者……不再是妁艷了。
現在護士會說出一個數字K,想問究竟妁艷必須要至少拿幾張卡片,才能使得這些卡片的和為K呢?亦或者根本無法用這些卡來湊出這個數字K呢?

Input Format

第一行為一個正整數N,代表共有幾筆輸入
N<=100000
之後2~N+1行每行有一個數字K(K保證可用有號int儲存)

Output Format

請針對每組輸入,輸出妁艷最少要拿出幾張卡片才有辦法湊出K?
如果說無法湊出K,請輸出"iyada~"(不含雙引號)
(詳細輸出情參考Sample Output)

Sample Input 1

5
1
2
3
5
8

Sample Output 1

1
1
1
1
1

Hints

可用點數學歸納法驗證自己的猜想

Problem Source

原TIOJ1751 / problem setter:jeremy89183

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2