切換
舊版
前往
大廳
主題

ZeroJudge - e623: PPAP 解題心得

Not In My Back Yard | 2020-04-08 01:23:48 | 巴幣 0 | 人氣 337

題目連結:


題目大意:
現在要根據人們的編號依序發放 Pen 、 Pineapple 、 Apple 、 Pineapple pen 四種物品,第一輪每種物品給一個、第二輪依序給兩個、第三輪給三個……以此類推。

因此編號一號的人得到 Pen 、第二個人得到 Pineapple 、 第三得到 Apple 、第四個拿到 Pineapple pen 、第五第六人得到 Pen 、第七和第八給予 Pineapple ……

現在給定一正整數 N (1 ≦ N ≦ 10000),求編號 N 的人拿到的物品為何?



範例輸入:
範例輸入一:
87

範例輸入二:
4076


範例輸出:
範例輸出一:
Pen

範例輸出二:
Apple


解題思維:
因為 N 很小所以可以直接用雙重迴圈去跑,外迴圈控制每種物品的發放數,內迴圈(可以分成四個,也可以合併成一個)則是控制要發放的物品。跑到第 N 個就可以知道物品是何物。



但是也可以觀察一下發放物品的序列。第一輪有四個物品、第二輪有八個物品、……、第 K 輪有 4K 個物品。所以可以找到最小的某一輪 K 使得 4 + 8 + …… + 4K ≧ N ,此即代表第 N 個人得到的物品必定坐落於第 K 輪之中。

然後再做一些計算,因為每種物品佔該輪的四分之一, N 扣除掉前面 K - 1 的數量後除以 K 的商數即可知道其對應到的物品為何了。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作