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.

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