It was a disaster for me. After 14 minutes, I solved A and moved on to B.
Since then, I got stuck on problem B because I was sure of my answer but I kept failing to pass pretest 3.
After the contest, I found out that I didn't put "End of Line" character AT THE END of the output.
It was a dumb mistake.
I looked at C, and found out it was a rather easy problem if you are familiar with "area under velocity - time graph.'
Here are my solutions. I added explanations in comments.
A - Wizards and Demonstration
Source Code
1: int main()
2: {
3: ios_base::sync_with_stdio(false);
4:
5: int N,X,Y;
6: cin>>N>>X>>Y;
7:
8: int up = Y*N;
9: if( (up % 100) > 0 )
10: {
11: up -= (up % 100);
12: up += 100;
13: }
14: up /= 100;
15: cout<< max(0, up - X) <<endl;
16:
17: return 0;
18: }
B - Wizards and Minimal Spell
Source Code
1: bool isSpell(string);
2: void printBuf(string);
3:
4: int main()
5: {
6: ios_base::sync_with_stdio(false);
7: string emp = "" + char(15);
8: string buf = emp;
9:
10: string str;
11: while(getline(cin,str))
12: {
13: if(isSpell(str))
14: {
15: if(buf != emp) printBuf(buf);
16: cout<<str<<endl;
17: buf = emp;
18: }
19: else
20: {
21: if(buf == emp) buf = str;
22: else buf += str;
23: }
24: }
25:
26: if(buf != emp)
27: printBuf(buf);
28:
29: return 0;
30: }
31:
32: bool isSpell(string str)
33: {
34: stringstream ss(str);
35: string test;
36: ss>>test;
37: return (test[0] == '#');
38: }
39:
40: void printBuf(string buf)
41: {
42: stringstream ss(buf);
43: string cur;
44: while(ss>>cur)
45: cout<<cur;
46: cout<<endl;
47: }
48:
C - Wizards and Trolleybuses
Source Code
1:
2: int main()
3: {
4: ios_base::sync_with_stdio(false);
5:
6: int N;
7: double A,D;
8: cin>>N>>A>>D;
9:
10: double prev = 0.0;
11:
12: cout<<fixed;
13: cout.precision(9);
14: for(int i=1; i <= N; i++)
15: {
16: double t, v;
17: cin>>t;
18: cin>>v;
19: double t_stop = sqrt(2.0*D/A); //time when train arrives at the destination
20: double t_max = v / A; //time when train reaches full allowed speed
21:
22: double t_ans = t; //train starts at time t
23: //Arrive at the destination before reaching full speed, or not.
24: if(t_stop < t_max) t_ans += t_stop;
25: else t_ans += t_max + D/v - v/(2.0*A);
26:
27: t_ans = max(prev, t_ans); //cannot arrive before the previous train
28: cout<<t_ans<<endl;
29: prev = t_ans;
30: }
31:
32: return 0;
33: }
D - Wizards and Huge Prize
Note
The problem statement was a bit confusing to me.
I initially thought that "player" cannot gain a huge prize if "the current bag size" is not big enough.
What the question really meant was that "player cannot bring "all huge prizes" if "the bag size at the end of the entire tour" is not big enough.
For example, at example 1,
the player starts with no bag, and the first and second round has huge prizes.
I thought it was impossible for him to earn any of the prizes.
However, he can earn those "huge prizes" first, and then win a bag at the third round.
So we are only interested at the bag size at the end of the entire tours.
Source Code
1: const int maxN = 210;
2:
3: /*
4: dp[i][j][k]
5: = probability of winning j tours in first i days
6: with bag capacity k and carrying all won prizes
7: */
8: double dp[maxN][maxN][maxN];
9:
10: int main()
11: {
12: ios_base::sync_with_stdio(false);
13:
14: int N,L,K;
15: cin>>N>>L>>K;
16:
17: double p[N+1];
18: int a[N+1];
19:
20: p[0] = 1.0;
21: for(int i=1; i <= N; i++)
22: {
23: cin>>p[i];
24: p[i] /= 100.0;
25: }
26:
27: a[0] = K;
28: for(int i=1; i <= N; i++)
29: {
30: cin>>a[i];
31: a[i]++;
32: }
33:
34: //base case
35: dp[0][0][K] = 1.0;
36:
37: for(int i=0; i < N; i++)
38: for(int j=0; j <= i; j++)
39: for(int k=0; k <= 200; k++)
40: if(dp[i][j][k] > 0.0)
41: {
42: dp[i+1][j+1][min(200, k+a[i+1])] += dp[i][j][k] * p[i+1];
43: dp[i+1][j][k] += dp[i][j][k] * (1.0 - p[i+1]);
44: }
45:
46:
47: double ans = 0.0;
48: for(int j=L; j <= 200; j++)
49: for(int k=j; k <= 200; k++)
50: ans += dp[N][j][k];
51:
52: cout<<fixed;
53: cout.precision(9);
54:
55: cout<<ans<<endl;
56:
57: return 0;
58: }
No comments:
Post a Comment