Alice and Bob
添加时间:2013-5-20 点击量:
Problem Description
Alice and Bob always love to play games， so does this time.
It is their favorite stone-taken game.
However， this time they does not compete but co-operate to finish this task.
Suppose there is a stack of n stones.
Each turn，
Alice can only take away stones in number pow of 2， say 1， 2， 4， 8， 16， ...
Bob can only take away stones in number pow of 3， say 1， 3， 9， 27， 81， ...
They takes stones alternately， and lady first.
Notice in each turn， Alice/Bob have to take away at least one stone， unless the stack is empty.
Now， the question is， what is the least number of operation for taking away all the stones.
Input
Multiple test cases. First line， there is an integer T （ 1 ≤ T ≤ 20 ）， indicating the number of test cases.
For each test case， there is a number n （ 1 ≤ n ≤ 10000 ）， occupying a line， indicating the total number of the stones.
Ouput
For each test case， output a line. It is an integer number k， indicating the least number of operation in need to finish the task.
Sample Input
5
1
2
3
4
5
Sample Output
1
1
2
1
2
1 ＃include <cstdio>
2 ＃include <algorithm>
3 using namespace std;
4 const int N = 10010;
5 const int inf = 999999999;
6 int dp[N][2];
7 int a[20]， b[20];
8
9 int main（）
10 {
11 a[0] = b[0] = 1;
12 for（int i = 1; i <= 16; i++） a[i] = a[i-1]2， b[i] = b[i-1]3;
13 int T， n;
14 scanf（％d， &T）;
15 while（ T-- ）
16 {
17 scanf（％d， &n）;
18 dp[0][0] = dp[0][1] = 0;
19 for（int i = 1; i <= n; i++）
20 {
21 int t = inf;
22 for（int k = 0; a[k] <= i; k++）
23 t = min（ t， dp[ i-a[k] ][1] ）;
24 dp[i][0] = t+1;
25 t = inf;
26 for（int k = 0; b[k] <= i; k++）
27 t = min（ t， dp[ i-b[k] ][0] ）;
28 dp[i][1] = t+1;
29 }
30 printf（％d\n， dp[n][0] ）;
31 }
32
33 return 0;
34 }
View Code（DP）
1 ＃include <cstdlib>
2 ＃include <iostream>
3 ＃include <cstdio>
4 ＃include <queue>
5 using namespace std;
6 ＃define INF 999999
7
8 int s[50022][2];
9 int in[50022];
10 int n;
11
12 int a[100]= {1，2，4，8，16};
13 int b[100]= {1，3，9，27};
14
15 int num2=4;
16 int num3=3;
17 queue <int> q;
18
19 void dabiao（）
20 {
21 while（a[num2-1] 2 <= 20099）
22 {
23 a[num2] = a[num2 - 1] 2;
24 num2++;
25 }
26
27 while（b[num3-1]3 < 20099）
28 {
29 b[num3] = b[num3-1] 3;
30 num3++;
31 }
32 }
33
34 void bfs（）
35 {
36 while（!q.empty（）） q.pop（）;
37
38 int j，f，t，v;
39
40 for（j=0; j<=14055; j++）
41 for（int k=0; k<2; k++）
42 s[j][k]=INF;
43
44 for（j=0; a[j]<=14011; j++）
45 {
46 s[a[j]][0] =1;
47 q.push（1）;
48 q.push（a[j]）;
49 }
50
51 while（!q.empty（））
52 {
53 f=q.front（）;
54 q.pop（）;
55
56 t=q.front（）;
57 q.pop（）;
58
59 if（f）
60 for（j=0; t+b[j]<=14011; j++）
61 {
62 v=t+b[j];
63 if（s[v][1] > s[t][0]+1）
64 {
65 s[v][1] = s[t][0] +1;
66 q.push（0）;
67 q.push（v）;
68 }
69 }
70 else
71 for（j=0; t+a[j]<14011; j++）
72 {
73 v=t+a[j];
74 if（s[v][0] > s[t][1] + 1）
75 {
76 s[v][0] = s[t][1] + 1;
77 q.push（1）;
78 q.push（v）;
79 }
80 }
81 }
82 }
83
84 int main（）
85 {
86 int t;
87 dabiao（）;
88 bfs（）;
89
90 scanf（％d， &t）;
91 while（t--）
92 {
93 scanf（％d， &n）;
94 printf（％d\n ，min（s[n][0]， s[n][1]））;
95 }
96
97 return 0;
98 }
View Code（BFS）
我俩之间有着强烈的吸引力。短短几个小时后，我俩已经明白：我们的心是一个整体的两半，我俩的心灵是孪生兄妹，是知己。她让我感到更有活力，更完美，更幸福。即使她不在我身边，我依然还是感到幸福，因为她总是以这样或者那样的方式出现在我心头。——恩里克·巴里奥斯《爱的文明》
Problem Description
Alice and Bob always love to play games， so does this time.
It is their favorite stone-taken game.
However， this time they does not compete but co-operate to finish this task.
Suppose there is a stack of n stones.
Each turn，
Alice can only take away stones in number pow of 2， say 1， 2， 4， 8， 16， ...
Bob can only take away stones in number pow of 3， say 1， 3， 9， 27， 81， ...
They takes stones alternately， and lady first.
Notice in each turn， Alice/Bob have to take away at least one stone， unless the stack is empty.
Now， the question is， what is the least number of operation for taking away all the stones.
Input
Multiple test cases. First line， there is an integer T （ 1 ≤ T ≤ 20 ）， indicating the number of test cases.
For each test case， there is a number n （ 1 ≤ n ≤ 10000 ）， occupying a line， indicating the total number of the stones.
Ouput
For each test case， output a line. It is an integer number k， indicating the least number of operation in need to finish the task.
Sample Input
5
1
2
3
4
5
Sample Output
1
1
2
1
2
1 ＃include <cstdio>
2 ＃include <algorithm>
3 using namespace std;
4 const int N = 10010;
5 const int inf = 999999999;
6 int dp[N][2];
7 int a[20]， b[20];
8
9 int main（）
10 {
11 a[0] = b[0] = 1;
12 for（int i = 1; i <= 16; i++） a[i] = a[i-1]2， b[i] = b[i-1]3;
13 int T， n;
14 scanf（％d， &T）;
15 while（ T-- ）
16 {
17 scanf（％d， &n）;
18 dp[0][0] = dp[0][1] = 0;
19 for（int i = 1; i <= n; i++）
20 {
21 int t = inf;
22 for（int k = 0; a[k] <= i; k++）
23 t = min（ t， dp[ i-a[k] ][1] ）;
24 dp[i][0] = t+1;
25 t = inf;
26 for（int k = 0; b[k] <= i; k++）
27 t = min（ t， dp[ i-b[k] ][0] ）;
28 dp[i][1] = t+1;
29 }
30 printf（％d\n， dp[n][0] ）;
31 }
32
33 return 0;
34 }
View Code（DP）
1 ＃include <cstdlib>
2 ＃include <iostream>
3 ＃include <cstdio>
4 ＃include <queue>
5 using namespace std;
6 ＃define INF 999999
7
8 int s[50022][2];
9 int in[50022];
10 int n;
11
12 int a[100]= {1，2，4，8，16};
13 int b[100]= {1，3，9，27};
14
15 int num2=4;
16 int num3=3;
17 queue <int> q;
18
19 void dabiao（）
20 {
21 while（a[num2-1] 2 <= 20099）
22 {
23 a[num2] = a[num2 - 1] 2;
24 num2++;
25 }
26
27 while（b[num3-1]3 < 20099）
28 {
29 b[num3] = b[num3-1] 3;
30 num3++;
31 }
32 }
33
34 void bfs（）
35 {
36 while（!q.empty（）） q.pop（）;
37
38 int j，f，t，v;
39
40 for（j=0; j<=14055; j++）
41 for（int k=0; k<2; k++）
42 s[j][k]=INF;
43
44 for（j=0; a[j]<=14011; j++）
45 {
46 s[a[j]][0] =1;
47 q.push（1）;
48 q.push（a[j]）;
49 }
50
51 while（!q.empty（））
52 {
53 f=q.front（）;
54 q.pop（）;
55
56 t=q.front（）;
57 q.pop（）;
58
59 if（f）
60 for（j=0; t+b[j]<=14011; j++）
61 {
62 v=t+b[j];
63 if（s[v][1] > s[t][0]+1）
64 {
65 s[v][1] = s[t][0] +1;
66 q.push（0）;
67 q.push（v）;
68 }
69 }
70 else
71 for（j=0; t+a[j]<14011; j++）
72 {
73 v=t+a[j];
74 if（s[v][0] > s[t][1] + 1）
75 {
76 s[v][0] = s[t][1] + 1;
77 q.push（1）;
78 q.push（v）;
79 }
80 }
81 }
82 }
83
84 int main（）
85 {
86 int t;
87 dabiao（）;
88 bfs（）;
89
90 scanf（％d， &t）;
91 while（t--）
92 {
93 scanf（％d， &n）;
94 printf（％d\n ，min（s[n][0]， s[n][1]））;
95 }
96
97 return 0;
98 }
View Code（BFS）
我俩之间有着强烈的吸引力。短短几个小时后，我俩已经明白：我们的心是一个整体的两半，我俩的心灵是孪生兄妹，是知己。她让我感到更有活力，更完美，更幸福。即使她不在我身边，我依然还是感到幸福，因为她总是以这样或者那样的方式出现在我心头。——恩里克·巴里奥斯《爱的文明》
