USACO Contest Feb2012 Bronze Moo 翻譯+題解

翻譯（質量不高，將就看吧）：
USACO Contest Feb2012 Bronze
Problem 3. Moo
奶牛們迷上了一個名為“Moo”的新的單詞遊戲。
在玩該遊戲時，奶牛們站成長長的一排，在隊列中的每一頭
奶牛都有責任盡可能快的大聲說出一個特定的字母。

在Moo遊戲中，這個單詞序列嚴格上說是無窮的，它是這樣開始的：
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

這一串最好由遞歸表示：令S(0)為三個字符的序列“moo”
那麼更長的字符串S(k)由三部分組成，第一部分是S(k-1)，第二部分是"m o...o"(k+2個'o')，第三部分又是S(k-1)。例如：
S(0)="m o o"
S(1)="m o o m o o o m o o"
S(2)="m o o m o o o m o o m o o o o m o o m o o o m o o"

正如你所看到的，這個過程最終將會產生一個無窮的長字符串，並且
這個長字符串正是被玩Moo遊戲的奶牛一個一個說出。

Bessie這頭奶牛，自我感覺很聰明，他想要預測第N頭奶牛將會說出m還是o。請你幫助他！



輸入：
11
輸出 :
m


【分析】
拿道這題，我首先想到了比這個題更難的『產生01串』
   不要去考慮模擬，O(n)都已經到了10^9的境界......
=========為了敘述方便，以下把S(1)當作"moo"，以此類推。==========
由於S(k)=2*S(k-1)+k+2，所以logN是一個可行的時間複雜度。

1 3
2 10
3 25
4 56
5 119
6 246
7 501
8 1012
9 2035
10 4082
11 8177
12 16368
13 32751
14 65518
15 131053
16 262124
17 524267
18 1048554
19 2097129
20 4194280
21 8388583
22 16777190
23 33554405
24 67108836
25 134217699
26 268435426
27 536870881
28 1073741792

可以看出，只用開30個整型變量就能存下了。
然後就是找到N所在的位置，看N是介於在哪兩個串長度之間，然後把那個串分成三部分，如果處於兩邊，則遞歸下去，如果在中間直接輸出就可以了，就這樣，循環往復……

【我的代碼】
下載的測試數據自評滿分
裸代碼RawCode

C++语言: Codee#25478

01 /*
02 *Problem: USACO Feb12 Bronze Moo
03 *Author: Yee-fan Zhu
04 *Email: zyfworks@gmail.com
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 using namespace std;
09 int S[1000];
10 int N;
11 void CreateSequence()
12 {
13     S[1]=3;
14     for(int i=2;S[i-1]<=1000000000;i++)
15     {
16         S[i]=S[i-1]*2+i+2;
17         //printf("%d %d\n",i,S[i]);
18     }
19 }
20
21 void end()
22 {
23     exit(0);
24     return;
25 }
26
27 int GetPos(int x)
28 {
29     int pos=0;
30     for(;S[pos]<x;pos++);
31     if(S[pos]==x)
32     {
33         printf("o\n");
34         end();
35     }
36     return pos-1;
37 }
38
39 void work()
40 {
41     int pos=GetPos(N)+1;
42     int now;
43     int mid;
44     while(pos>1)
45     {
46         //pos=GetPos(N);
47         now=N-S[pos-1];
48         if(now==0)
49         {
50             printf("o\n");
51             end();
52         }
53         if(now<0)
54         {
55             pos--;
56             continue;
57         }
58         mid=pos+2;
59         if(now==1)
60         {
61             printf("m\n");
62             end();
63         }
64         if(now<=mid)
65         {
66             printf("o\n");
67             end();
68         }
69         N=now-mid;
70         pos--;
71     }
72     if(N==1)
73         printf("m\n");
74     if(N>1)
75         printf("o\n");
76     end();
77 }
78
79 int main()
80 {
81     freopen("moo.in","r",stdin);
82     freopen("moo.out","w",stdout);
83     scanf("%d\n",&N);
84     CreateSequence();
85       work();
86     return 0;
87 }