10025 - The ? 1 ? 2 ? ... ? n = k problem

[pc5971]

I can't see all bugs from your code... One that I found it is that the numbers must be "long" not "int" (n<=1000000000). I check your program with values -30..30 and 1000000000 and give the same result as my program wich was accepted...

Carmen

[pc5971]

I can't see all bugs from your code... One that I found it is that the numbers must be "long" not "int" (n<=1000000000). I check your program with values -30..30 and 1000000000 and give the same result as my program wich was accepted...

I use the same ideea...

Carmen

[Astrakan]

You should check the existing thread about this problem (http://acm.uva.es/board/viewtopic.php?t=1805).

It's a multiple input problem (blue check mark). You should read http://acm.uva.es/problemset/minput.html to find out what the input and output should look like. The first line of input contains the number of cases, and there should be a blank line between each output case.

[25258FM]

[cpp]
#include <iostream.h>
#include <stdio.h>
void main(void){
long number,i,base,different,state,times,k;
i=0;
base=0;
state=0;
cin>>times;
cout<<endl;
for (k=0;k<times;k++)
{
cin>>number;
if (number < 0)
number=-number;
while(1)
{
i++;
base+=i;
if (base>=number)
{
different=base-number;
if ((different==0)||(different % 2==0))
{
break;
}
}

}
if (number==0)
cout<<3<<endl<<endl;
else
{
cout<<i<<endl<<endl;
}
}

}
[/cpp]
i made my code become this in order to suit the mulit line problem.
However, it still get a WA..
why?

[Astrakan]

Try this input, and you'll see:

Code: Select all

3

1

1

1

Also, there should be no blank line before the first output case, and after the last output case. There should only be blank lines between the output cases.

[eloha]

2. Now your solution is n or n+1 or n+2, because
d=s-n*(n+1)/2 must be even.

Can you explain more for this? Thank you very much!

[pc5971]

so S1=n(n+1)/2 D1=S1-S
S2=(n+1)(n+2)/2 D2=S2-S
S3=(n+2)(n+3)/2 D3=S3-S
=> d1/2 < N+1
d2/2 < (2N+1)/2 < N+1
d3/2 < (3N+3)/2 <=2N+3=(N+1)+(N+2 )

a) if D1 is even => exist k between 0 and N so that D1/2 =k (we saw that D1/2 < N/2)

=> S1-S=2k
S1-2k=S
1+2+...+(k-1)+k+(k+1)+...+N-2k=S
1+2+...+(k-1)-k+(k+1)+...+N=S
=> solution is N

b) if D1 is odd
if D2 is even
=> in the same way we can prove that solution is N+1 and the sum of the terms which must be substracted is D2/2

c) id D2 is odd (D1 and D2 are odd)
D3=D1+(N+1)+(n+2)
D1 is odd
(N+1)+(N+2) is even
=> D3 is even

=> in the same way as a) that solution is N+2 and the sum of the terms that must be substracted is D3/2 ...

I hope this we'll help you . . .

Carmen

[Almost Human]

I got WA. Why ??? Any special input I should consider ???

Code: Select all

#include <math.h>
#include <stdio.h>

int main ( void )
{
  long NumOfCase , input , first , count ;

/*  freopen ( "10025.in" , "r" , stdin ) ;
  freopen ( "10025.out" , "w" , stdout ) ;*/

  scanf ( "%ld" , &NumOfCase ) ;

  while ( NumOfCase -- )
  {
	 scanf ( "%ld" , &input ) ;
	 if ( input < 0 ) input = - input ;

	 for ( first = ceil ( ( -1 + sqrt ( 1 + 8 * input ) ) / 2 ) , count = first / 2.0 * ( first + 1 ) ; ( count - input ) % 2 ; first ++ , count += first ) ;

	 printf ( "%ld\n" , first ) ;
	 if ( NumOfCase ) printf ( "\n" ) ;
  }

  return 0 ;
}

[Whinii F.]

Your program fails with large test cases, such as 987456167.

My program's output is 44441. But you have an integer overflow here: -2147483647.

[nikhil]

I can't realize what's wrong........
pls help


#include <math.h>
#include <stdio.h>

int main ( void )
{
long double a , b , c ;

while ( 1==scanf ( "%Lf" , &a ) ){

(a<0)? a = -a : 0;

for ( b = ceil ( (-1+sqrtl (1+8*a))/2 ) , c=b/ 2.0*(b+1) ;
(long)( c - a ) % 2 ;
b++ , c += b ) ;

printf ( "%.0Lf\n" , b) ;

}

return 0 ;
}

[bayzid]

I think this program is correct but judge reply wrong ans.plz help me?


/* @JUDGE_ID: xxxxxx 10025 C++ */

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<conio.h>
main()
{
long double i,k,m;
while(scanf("%Lf",&i)==1)
{
if(i<0)
i=-i;
m=ceil(sqrt(i*2));
k=fmod((m*(m+1)/2-i),2);
if(k)
printf("%.0Lf\n",m+2);
else
printf("%.0Lf\n",m);
}
}

[mohiul alam prince]

bayzid

i think u are getting WA for using conio.h because fmod is not valid in acm

prince

[shamim]

Bayzid, your code tries to access the header file <conio.h>

It is supposed to get Compile Error. I wonder how you can get WA.

[sohel]

bayzid

i think u are getting WA for using conio.h because fmod is not valid in acm

prince

Conio.h is not allowed - right , but I think fmod can be used.

[20717TZ]

take attention to:

The first line is the number of test cases

BTW:
Trick case Input:
1

0

Output should be:
3


but your code outputs:
0