### problem-solved's blog

By problem-solved, 7 years ago, , 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

By problem-solved, 7 years ago, , T_T....

By problem-solved, 7 years ago, , recently , I'm learning the KM algorithm , after read some resources on the internet,I still can't fully understand ,do you guys have any paper or some useful information to help me ..many thanks

By problem-solved, 7 years ago, , By problem-solved, 7 years ago, , 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 ） By problem-solved, 7 years ago, , Recently I suffered alot of problems about java,so can anyone give me some good websites to learn by myself?

By problem-solved, 8 years ago, , http://www.codeforces.com/contest/59/problem/E mother always tell me when you fail , just try again and again ,but i'm keep failing — -

By problem-solved, 8 years ago, , By problem-solved, 8 years ago, , By problem-solved, 8 years ago, , kawatea's solution http://codeforces.com/contest/246/submission/2621642 i think it's brute force because this solution uesd a "for" loop to find distinct names of k sons

By problem-solved, 8 years ago, , By problem-solved, 8 years ago, , By problem-solved, 8 years ago, , #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);
} By problem-solved, 8 years ago, , # include

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); } By problem-solved, 8 years ago, , I can't understand the solutions of the accepted code

By problem-solved, 8 years ago, , 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;
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;
} 