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

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

Post by pc5971 » Tue Jan 21, 2003 8:58 am

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
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

Post by pc5971 » Tue Jan 21, 2003 9:00 am

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
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden

Post by Astrakan » Tue Jan 21, 2003 11:19 am

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
New poster
Posts: 5
Joined: Fri Nov 01, 2002 12:12 pm

Post by 25258FM » Tue Jan 21, 2003 5:31 pm

[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
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden

Post by Astrakan » Tue Jan 21, 2003 5:57 pm

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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Wed Jan 22, 2003 7:58 pm

pc5971 wrote: 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
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

Post by pc5971 » Tue Jan 28, 2003 8:35 am

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

10025 - WA

Post by Almost Human » Fri Aug 01, 2003 8:21 am

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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sat Aug 02, 2003 5:51 am

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

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

nikhil
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

10025 WA unwanted...

Post by nikhil » Thu Oct 09, 2003 3:04 am

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
New poster
Posts: 7
Joined: Sun Sep 14, 2003 8:09 am
Location: bangladesh
Contact:

10025 why wrong ans????

Post by bayzid » Tue Nov 04, 2003 9:05 am

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

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sat Feb 14, 2004 3:10 pm

bayzid

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

prince

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Feb 15, 2004 12:17 pm

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. :-?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Feb 24, 2004 3:44 pm

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
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

Post by 20717TZ » Fri May 28, 2004 5:35 am

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
I Believe I Can - leestime.com

Post Reply

Return to “Volume 100 (10000-10099)”