problem-solved's blog

By problem-solved, 11 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By problem-solved, 11 years ago, In English
  • Vote: I like it
  • -4
  • Vote: I do not like it

By problem-solved, 11 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By problem-solved, 11 years ago, In English
  • Vote: I like it
  • +6
  • Vote: I do not like it

By problem-solved, 12 years ago, In English

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 )

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By problem-solved, 12 years ago, In English

Recently I suffered alot of problems about java,so can anyone give me some good websites to learn by myself?

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By problem-solved, 12 years ago, In English

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 — -

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By problem-solved, 12 years ago, In English
  • Vote: I like it
  • -7
  • Vote: I do not like it

By problem-solved, 12 years ago, In English
  • Vote: I like it
  • +9
  • Vote: I do not like it

By problem-solved, 12 years ago, In English

kawatea's solution http://codeforces.net/contest/246/submission/2621642 i think it's brute force because this solution uesd a "for" loop to find distinct names of k sons

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By problem-solved, 12 years ago, In English
  • Vote: I like it
  • +4
  • Vote: I do not like it

By problem-solved, 12 years ago, In English
  • Vote: I like it
  • +3
  • Vote: I do not like it

By problem-solved, 12 years ago, In English
#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);
}

Full text and comments »

  • Vote: I like it
  • -18
  • Vote: I do not like it

By problem-solved, 12 years ago, In English

include

include

include

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); }

Full text and comments »

  • Vote: I like it
  • -39
  • Vote: I do not like it

By problem-solved, 12 years ago, In English

I can't understand the solutions of the accepted code

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By problem-solved, 12 years ago, In English

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;
}

Full text and comments »

Tags stl
  • Vote: I like it
  • -21
  • Vote: I do not like it