link I use the link's code, but generate code like this Your text to link here... I don't know why? The DEFAULTMAIN seems unused and the testcode is c++ style

# | User | Rating |
---|---|---|

1 | Benq | 3539 |

2 | tourist | 3532 |

3 | wxhtxdy | 3425 |

4 | Radewoosh | 3316 |

5 | ecnerwala | 3297 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | Um_nik | 3260 |

9 | yutaka1999 | 3190 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 192 |

2 | Radewoosh | 179 |

3 | tourist | 173 |

4 | Vovuh | 167 |

4 | antontrygubO_o | 167 |

4 | PikMike | 167 |

7 | rng_58 | 160 |

8 | majk | 157 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

T_T....

Cows and Cool Sequences maybe this proof is easy for you ,but for me .... hehe....so I wrote this ... my english is so poor,so i can't understand the Tutorial I think most of you can come up with the idea of DP,but be confused with the proof of how to judge whether a cool sequence can begin with a[i] and ends with a[j] . Proof: first : a conclusion

```
if(x,y) is cool
if(y is odd) then x%y=0
else (2*x%y==0 && x%y!=0)
```

proof : provided that the first number of the sequence is t ,so

```
x = y*(y-1)/2 + y * t
```

if y is odd, ( y — 1) is even ,so x = y*((y-1)/2+t),so if (x,y) is cool x must be divided by y if y is even, y-1 is odd so

```
2*x = y*(y-1) + 2*y*t ;
2*x = y*( (y-1)+2*y*t );
```

so 2*x must be divided by y ,but another x can't be divided by y(because 2*y*t is odd)

and there is also another important conclusion when y is even ,that is m[y] = m[x] + 1; (m[n] denote the exponent of the largest power of 2 that divides n.) this is also easy to prove :

```
a[i] = 2^a * p
2*a[i] = 2^(a+1)*p
a[j] = 2^b*q
(p,q are the biggest odd factor )
since a[j] can divided 2*a[i] and a[j] can't divided a[i],we can conclude b = a + 1;
```

we can solve the problem , no matter what's the parity of a[j] , there's a big condition must be fullfilled:

```
the max odd factor of a[i] must be divided by the max odd factoe of a[j]
```

if a[j] is odd ,and a[i]%a[j]==0,we can always construct the sequence

```
,for example a[i]=12 a[j] = 3,we can construct the sequence like
12 3 ...3 3 3 3 3 3 3 3.
```

if a[j] is even , given that m[u] = m[u-1] + 1. so m[j] = m[i] + j — i; it's the situation that all of the numbers in the cool sequence(except a[i]) are even

```
for example :a[i] = 3,a[j] = 36 ,the sequence is : 3 6 12 24 36
```

the last situation is there are some odd numbers in the left part of the sequence ,and then even numbers ..

what's the condition of this situation that ensures there's a cool sequence ? it's easy now :

```
m[j] <= j -i - 1;
```

```
for example : a[i] = 6,a[j] = 24; cool sequence : 6 3 3 3 3 6 12 24
```

if m[j] > j — i — 1,there can't be any cool sequence begins with a[i],ends with a[j]. because m[i+1] = m[j] — (j — i -1) > 0 since a[i],a[i+1] must be cool and a[i+1] is even ,so

```
m[i+1] = m[j] - j - i - 1
m[i] < m[i+1] , m[i]+1 >= m[j]-(j-i-1)
so m[i] == m[j] - (j-i) -> m[i] + j - i = m[j]
(so here coms a contradiction ，it's already judged in the case up ）
```

rt

```
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int inf = ~0u>>2;
int c3,c4,c5,k3,k4,k5;
int F(){
return abs(c3*k3-c4*k4)+abs(c4*k4-c5*k5);
}
int main()
{
int n,s,i,j,k;
scanf("%d%d",&n,&s);
for(c3=c4=c5=0;n;n--)
{
scanf("%d",&j);
if(j==3) c3++;
if(j==4) c4++;
if(j==5) c5++;
}
int ans=inf,x,y,z;
for(k3=s/(c3+c4+c5);k3>=0;k3--)
{
int up=inf;
for(k4=(s-k3*c3)/(c4+c5);k4>=k3;k4--)
{
k5=(s-c3*k3-k4*c4);if(k5%c5) continue;
k5/=c5;
if(k5<k4 ) continue;
int tmp=F();
if(tmp<up)
{
up=tmp;
if(up<ans)
{
ans=up;
x=k3;y=k4;z=k5;
}
}
else break;//where is the monotonicity
//why can we use break here,I can't understand
}
}
if(ans==inf) printf("-1\n");
else printf("%d %d %d\n",x,y,z);
}
```

using namespace std; const int inf = ~0u>>2; int c3,c4,c5,k3,k4,k5; int F(){ return abs(c3*k3-c4*k4)+abs(c4*k4-c5*k5); } int main() { int n,s,i,j,k; scanf("%d%d",&n,&s); for(c3=c4=c5=0;n;n--) { scanf("%d",&j); if(j==3) c3++; if(j==4) c4++; if(j==5) c5++; } int ans=inf,x,y,z; for(k3=s/(c3+c4+c5);k3>=0;k3--) { int up=inf; for(k4=(s-k3*c3)/(c4+c5);k4>=k3;k4--) { k5=(s-c3*k3-k4*c4);if(k5%c5) continue; k5/=c5; if(k5<k4 ) continue; int tmp=F(); if(tmp<up) { up=tmp; if(up<ans) { ans=up; x=k3;y=k4;z=k5; } } else break;//where is the monotonicity //why can we use break here,I can't understand } } if(ans==inf) printf("-1\n"); else printf("%d %d %d\n",x,y,z); }

I can't understand the solutions of the accepted code

CF 191B

```
#include<cstdio>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 lld;
multiset<int> Q;
int a[100010];
int main()
{
int n,k,i;
lld sum=0,b;
scanf("%d%d",&n,&k);
scanf("%I64d",&b);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=n;
for(i=n-k+1;i<n;i++)
{
sum+=a[i];
Q.insert(a[i]);
}
for(i=n-k;i>=1;i--){
sum+=a[i];
if(sum>b) ans=i;
Q.insert(a[i]);
int tmp=*Q.begin();
sum-=tmp;
Q.erase(Q.begin());//it's wrong if I erase the key number like Q.erase(tmp),it may erase many numbers
}
printf("%d\n",ans);
return 0;
}
```

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/15/2019 01:54:54 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|