Solved Problem ID Title Ratio(Accepted / Submitted)
1001 小兔的棋盤 54.05%(20/37)
1002 連線游戲 70.00%(14/20)
1003 Train Problem II 40.00%(12/30)
1004 Buy the Ticket 35.71%(5/14)
小兔的棋盤
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 37 Accepted Submission(s) : 20
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小兔的叔叔從外面旅游回來給她帶來了一個禮物，小兔高興地跑回自己的房間，拆開一看是一個棋盤，小兔有所失望。不過沒過幾天發(fā)現(xiàn)了棋盤的好玩之處。從起點(0，0)走到終點(n,n)的最短路徑數(shù)是C(2n,n),現(xiàn)在小兔又想如果不穿越對角線(但可接觸對角線上的格點)，這樣的路徑數(shù)有多少?小兔想了很長時間都沒想出來，現(xiàn)在想請你幫助小兔解決這個問題，對于你來說應該不難吧!
Input
每次輸入一個數(shù)n(1<=n<=35)，當n等于－1時結束輸入。
Output
對于每個輸入數(shù)據(jù)輸出路徑數(shù)，具體格式看Sample。
Sample Input
1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024
Author
Rabbit
Source
RPG專場練習賽
#include using namespace std; typedef long long LL; const int maxn = 1e5+10; LL f[50]; int main(){ f[0] = f[1] = 1; for(int i = 2; i <= 35; i++) for(int j = 0; j <= i-1; j++) f[i] += f[j]*f[i-1-j]; int n; for(int i = 1; cin>>n&&n!=-1; i++){ cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
連線游戲
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 20 Accepted Submission(s) : 14
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
這是個古老的小游戲。
假設在地上按照順時針方向依次寫下2n個數(shù)字1,2,3,4…2n圍成一個圓，然后用n條直線連接這2n個數(shù)字，每個數(shù)字都和一個數(shù)字相連，并且僅僅和一個數(shù)字相連。要求所有的連線都不能有交點。
請計算一共有多少種不同的連線方式。
比如，當n等于2時，地上一共有4個數(shù)字，有2種不同的連線方式。
Input
輸入包含多組測試用例。
每行輸入數(shù)據(jù)包含一個正整數(shù)n（?1 <= n <=35），除了最后一行的-1，它表示輸入數(shù)據(jù)的結束。
Output
對于每組輸入數(shù)據(jù)的n，請計算2n個數(shù)字的不同的連線方式數(shù)目。
每組數(shù)據(jù)輸出一行。
Sample Input
2
3
-1
Sample Output
2
5
#include using namespace std; typedef long long LL; const int maxn = 1e5+10; LL f[50]; int main(){ f[0] = f[1] = 1; for(int i = 2; i <= 35; i++) for(int j = 0; j <= i-1; j++) f[i] += f[j]*f[i-j-1]; int n; while(cin>>n && n!=-1){ cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Train Problem II
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 30 Accepted Submission(s) : 12
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.
Input
The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.
Output
For each test case, you should output how many ways that all the trains can get out of the railway.
Sample Input
1
2
3
10
Sample Output
1
2
5
16796
Hint
The result will be very large, so you may not process it by 32-bit integers.
Author
Ignatius.L
//C[n] = C[n-1]*(4*n-2)/(n+1) #include using namespace std; struct BigInteger { typedef unsigned long long LL; static const int BASE = 100000000; static const int WIDTH = 8; vector s; BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;} BigInteger(LL num = 0) {*this = num;} BigInteger(string s) {*this = s;} BigInteger& operator = (long long num) { s.clear(); do { s.push_back(num % BASE); num /= BASE; } while (num > 0); return *this; } BigInteger& operator = (const string& str) { s.clear(); int x, len = (str.length() - 1) / WIDTH + 1; for (int i = 0; i < len; i++) { int end = str.length() - i*WIDTH; int start = max(0, end - WIDTH); sscanf(str.substr(start,end-start).c_str(), "%d", &x); s.push_back(x); } return (*this).clean(); } BigInteger operator + (const BigInteger& b) const { BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = g; if (i < s.size()) x += s[i]; if (i < b.s.size()) x += b.s[i]; c.s.push_back(x % BASE); g = x / BASE; } return c; } BigInteger operator - (const BigInteger& b) const { assert(b <= *this); // 減數(shù)不能大于被減數(shù) BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = s[i] + g; if (i < b.s.size()) x -= b.s[i]; if (x < 0) {g = -1; x += BASE;} else g = 0; c.s.push_back(x); } return c.clean(); } BigInteger operator * (const BigInteger& b) const { int i, j; LL g; vector v(s.size()+b.s.size(), 0); BigInteger c; c.s.clear(); for(i=0;i= v.size()) break; LL x = v[i] + g; c.s.push_back(x % BASE); g = x / BASE; } return c.clean(); } BigInteger operator / (const BigInteger& b) const { assert(b > 0); // 除數(shù)必須大于0 BigInteger c = *this; // 商:主要是讓c.s和(*this).s的vector一樣大 BigInteger m; // 余數(shù):初始化為0 for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return c.clean(); } BigInteger operator % (const BigInteger& b) const { //方法與除法相同 BigInteger c = *this; BigInteger m; for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return m; } // 二分法找出滿足bx<=m的最大的x int bsearch(const BigInteger& b, const BigInteger& m) const{ int L = 0, R = BASE-1, x; while (1) { x = (L+R)>>1; if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;} else R = x; } } BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;} BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;} BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;} BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;} BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;} bool operator < (const BigInteger& b) const { if (s.size() != b.s.size()) return s.size() < b.s.size(); for (int i = s.size()-1; i >= 0; i--) if (s[i] != b.s[i]) return s[i] < b.s[i]; return false; } bool operator >(const BigInteger& b) const{return b < *this;} bool operator<=(const BigInteger& b) const{return !(b < *this);} bool operator>=(const BigInteger& b) const{return !(*this < b);} bool operator!=(const BigInteger& b) const{return b < *this || *this < b;} bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);} }; ostream& operator << (ostream& out, const BigInteger& x) { out << x.s.back(); for (int i = x.s.size()-2; i >= 0; i--) { char buf[20]; sprintf(buf, "%08d", x.s[i]); for (int j = 0; j < strlen(buf); j++) out << buf[j]; } return out; } istream& operator >> (istream& in, BigInteger& x) { string s; if (!(in >> s)) return in; x = s; return in; } BigInteger a[110]; int main(){ a[0] = 1; for(int i = 1; i <= 100; i++){ a[i] = a[i-1]*(4*i-2); a[i] = a[i]/(i+1); } int n; while(cin>>n){ cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
Buy the Ticket
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 14 Accepted Submission(s) : 5
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
The “Harry Potter and the Goblet of Fire” will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?
Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).
Now the problem for you is to calculate the number of different ways of the queue that the buying process won’t be stopped from the first person till the last person.
Note: initially the ticket-office has no money.
The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
Input
The input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise, m, n <=100.
Output
For each test case, first print the test number (counting from 1) in one line, then output the number of different ways in another line.
Sample Input
3 0
3 1
3 3
0 0
Sample Output
Test #1:
6
Test #2:
18
Test #3:
180
Author
HUANG, Ninghai
//ans=(C(m+n,n)-C(m+n,m+1))*m!*n!=(m+n)!*(m-n+1)/(m+1) #include using namespace std; struct BigInteger { typedef unsigned long long LL; static const int BASE = 100000000; static const int WIDTH = 8; vector s; BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;} BigInteger(LL num = 0) {*this = num;} BigInteger(string s) {*this = s;} BigInteger& operator = (long long num) { s.clear(); do { s.push_back(num % BASE); num /= BASE; } while (num > 0); return *this; } BigInteger& operator = (const string& str) { s.clear(); int x, len = (str.length() - 1) / WIDTH + 1; for (int i = 0; i < len; i++) { int end = str.length() - i*WIDTH; int start = max(0, end - WIDTH); sscanf(str.substr(start,end-start).c_str(), "%d", &x); s.push_back(x); } return (*this).clean(); } BigInteger operator + (const BigInteger& b) const { BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = g; if (i < s.size()) x += s[i]; if (i < b.s.size()) x += b.s[i]; c.s.push_back(x % BASE); g = x / BASE; } return c; } BigInteger operator - (const BigInteger& b) const { assert(b <= *this); // 減數(shù)不能大于被減數(shù) BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = s[i] + g; if (i < b.s.size()) x -= b.s[i]; if (x < 0) {g = -1; x += BASE;} else g = 0; c.s.push_back(x); } return c.clean(); } BigInteger operator * (const BigInteger& b) const { int i, j; LL g; vector v(s.size()+b.s.size(), 0); BigInteger c; c.s.clear(); for(i=0;i= v.size()) break; LL x = v[i] + g; c.s.push_back(x % BASE); g = x / BASE; } return c.clean(); } BigInteger operator / (const BigInteger& b) const { assert(b > 0); // 除數(shù)必須大于0 BigInteger c = *this; // 商:主要是讓c.s和(*this).s的vector一樣大 BigInteger m; // 余數(shù):初始化為0 for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return c.clean(); } BigInteger operator % (const BigInteger& b) const { //方法與除法相同 BigInteger c = *this; BigInteger m; for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return m; } // 二分法找出滿足bx<=m的最大的x int bsearch(const BigInteger& b, const BigInteger& m) const{ int L = 0, R = BASE-1, x; while (1) { x = (L+R)>>1; if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;} else R = x; } } BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;} BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;} BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;} BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;} BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;} bool operator < (const BigInteger& b) const { if (s.size() != b.s.size()) return s.size() < b.s.size(); for (int i = s.size()-1; i >= 0; i--) if (s[i] != b.s[i]) return s[i] < b.s[i]; return false; } bool operator >(const BigInteger& b) const{return b < *this;} bool operator<=(const BigInteger& b) const{return !(b < *this);} bool operator>=(const BigInteger& b) const{return !(*this < b);} bool operator!=(const BigInteger& b) const{return b < *this || *this < b;} bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);} }; ostream& operator << (ostream& out, const BigInteger& x) { out << x.s.back(); for (int i = x.s.size()-2; i >= 0; i--) { char buf[20]; sprintf(buf, "%08d", x.s[i]); for (int j = 0; j < strlen(buf); j++) out << buf[j]; } return out; } istream& operator >> (istream& in, BigInteger& x) { string s; if (!(in >> s)) return in; x = s; return in; } int main(){ int n, m; for(int i = 1; cin>>m>>n; i++){ if(n==0 &&m==0)break; cout<<"Test #"<m){cout<<"0\n"; continue;} BigInteger a = 1; for(int i = 2; i <= m+n; i++)a *= i; a = a*(m-n+1)/(m+1); cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
5G游戲
版權聲明：本文內(nèi)容由網(wǎng)絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權內(nèi)容。
版權聲明：本文內(nèi)容由網(wǎng)絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權內(nèi)容。
