UVa 107 The Cat in the Hat
解題策略
這題的關鍵其實就是找N (廢話...)，每隻貓都可以從帽子中變出N隻小貓，小貓的高度是 1/(N+1) ，所以有N一切的謎底就都解開了。我的做法也很簡單，就是用個for迴圈去代 n ，然後比對最後工作的小貓數量，直到符合為止。一個可能蠻有用的測資
483736625 481890304
0 0
答案是 615441 1931252289，找出來的N應該是784。
注意
官網論壇上面很多亂七八糟的測資，像是(3 1), (5 1), (7 1) 等等除不盡的測資，請 完 全 不 要 管 這些東西。所有合法測資都是剛剛好整除的整數，貓的初始高度也一定是某數的完全次方。閒聊
開心，終於達成100~113連號答題，整排都是綠色的AC看起來就很爽。雖然不是用很數學的方式，但是這個解法是我自己想出來的，相當有成就感。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * UVa 107 The Cat in the Hat | |
| * Author: chchwy | |
| * Last Modified: 2010.02.28 | |
| * Tag: Math, Recursion | |
| */ | |
| #include<cstdio> | |
| void find (int initHeight, int kitten) | |
| { | |
| /* iterate n to fit the answer */ | |
| for (int n = 2; n <= initHeight; ++n) | |
| { | |
| int curHeight = initHeight; | |
| int nowCat = 1; | |
| int totalCat = 0, notWorkCat = 0; | |
| while ((curHeight % n) == 0) | |
| { | |
| totalCat += curHeight * nowCat; | |
| notWorkCat += nowCat; | |
| curHeight = curHeight / n; | |
| nowCat = nowCat * (n - 1); | |
| } | |
| if (nowCat == kitten) // got Answer! | |
| { | |
| totalCat += nowCat; | |
| printf("%d %d\n", notWorkCat, totalCat); | |
| break; | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| #ifndef ONLINE_JUDGE | |
| freopen("107.in", "r", stdin); | |
| #endif | |
| int initHeight, kitten; //initial height, number of kitten | |
| while (scanf("%d %d", &initHeight, &kitten) == 2) | |
| { | |
| if (initHeight == 0 || kitten == 0) | |
| break; | |
| /* special case */ | |
| if (initHeight == 1 && kitten == 1) | |
| printf("0 1\n"); | |
| else if (initHeight == 1) | |
| printf("1 %d\n", kitten); | |
| /* find n */ | |
| find(initHeight, kitten); | |
| } | |
| return 0; | |
| } |
留言
張貼留言