網頁

2014年1月28日 星期二

UVa 10334 Ray Through Glasses

本題連結

想法:
   觀察圖,能造成下次數量變多的折線,其最右邊"尖點"都位在上面那條線或下面那條線,例如a2=3,有'2'個"尖點"位在上面那條線,因此能使得a3比a2多出'2'條摺線(a3=a2+2=5),在觀察a3,有'3'個尖點,因此能使a4比a3多出3個折線(a4=a3+3=8)。那麼尖點的產生方式在於前一個的折線數量,例如a2的尖點來自於a1的箭頭與上面那條線的交點,所以a2尖點的數量=a1,因此我們可得a3=a2+(a2尖點)=a2+a1。
  簡而言之,本題為費伯那西數列,a(n)=a(n-1)+a(n-2),而另外由於n可到1000,因此要自己寫大數加法。