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

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

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

Post by Cubist » Wed Jun 12, 2002 7:30 pm

The problem description doesn't say that the first input is the number
of items to process! Please fix this!

-Chris

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Wed Jun 12, 2002 7:48 pm

Calm down, - the problem is clearly marked as being multiple input by a blue checkmark.

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

Doh!

Post by Cubist » Wed Jun 12, 2002 11:20 pm

Many apologies - I'm new here, and hadn't realized the multiple input
condition at all! It'd be nice if this was mentioned in the problems
themselves, e.g. Note: multiple input (with link to the page describing
the multiple input condition). It's certainly a small thing, but it would
save people from wasting time, and all the input/output conditions would
be in the actual problem description. :roll:

-Chris

yan4546
New poster
Posts: 7
Joined: Fri Nov 15, 2002 4:17 am
Contact:

10025

Post by yan4546 » Wed Nov 20, 2002 3:11 am

Can you tell me if the following input and output datas are right?

Thank you!

Input Output
-----------------------------------------
1000000000 44723
43562436 9335
-235344 687
0 3
234387 685
------------------------------------------

Can you send some of your datas to me ?

Bye!
aaaaaaaaaaaaaaaaaaaaa

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

10025

Post by stcheung » Sun Nov 24, 2002 4:51 pm

Okay I have fixed 2 major bugs: (1)realizing multiple input and (2)recognizing output=3 for input=3. But I still get WA...any help folks?

[cpp]

#include <iostream.h>
#include <stdlib.h>
#include <math.h>

int main()
{
int numcases;
cin >> numcases;
for(int i=0; i<numcases; i++)
{
unsigned number, temp;
double root;
unsigned root2;
cin >> number;
number = abs(number);
if(number == 0)
root2 = 3;
else if(number == 1)
root2 = 1;
else
{
temp = 2 * number;
root = sqrt(temp);
root2 = (root == (int)root) ? (int)root : (int)root+1;
while(true)
{
if((root2*(root2+1)/2 - number)%2 == 0)
break;
root2++;
}
}
cout << root2 << "\n";
}
return 0;
}[/cpp]

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Mon Dec 09, 2002 2:00 pm

Input Output
-----------------------------------------
1000000000 44723
43562436 9335
-235344 687
0 3
234387 685
------------------------------------------

This output is correct. If you get WA, maybe you don't consider the multiple input.

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden

Post by Astrakan » Wed Dec 25, 2002 3:06 pm

Your program doesn't produce the correct output for k=3. Output should be 2 (1+2 = 3) but your program answered 5 when I tried it.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Dec 26, 2002 4:41 am

Incredible thanks. Turns out my program doesn't work not only for input=3, but for input=any triangular number (3, 6, 10, 15...).
Writing test cases is a skill I need to master.

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

Post by pc5971 » Wed Jan 15, 2003 7:01 pm

I solved the problem and it works for all inputs that I can find (here or in the problem...) but I still receive WA. Can you tell what can be wrong?


Carmen

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

Post by pc5971 » Thu Jan 16, 2003 11:36 am

I solved the problem and it works for all inputs that I can find (in board or in the problem...) but I still receive WA. Can you tell what can be wrong?

[c]
deleted
[/c]
Last edited by pc5971 on Tue Jan 21, 2003 7:49 am, edited 1 time in total.

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden

Post by Astrakan » Thu Jan 16, 2003 11:48 am

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.

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

Post by pc5971 » Thu Jan 16, 2003 2:11 pm

That was so useful hint for me. Thanks a lot because I was sure that the algorithm it's Ok but . . .

I was accepted now

25258FM
New poster
Posts: 5
Joined: Fri Nov 01, 2002 12:12 pm

10025

Post by 25258FM » Mon Jan 20, 2003 3:15 pm

[cpp]
#include <iostream.h>
#include <stdio.h>
void main(void){
int number,i,base,different,state;

while(1)
{

i=0;
base=0;
state=0;

cin>>number;
if (feof(stdin)) break;
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;
else
{
cout<<i<<endl;
}
}
}

[/cpp]
i get a WA, pls help help me....

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Tue Jan 21, 2003 5:27 am

pc5971 wrote:I was sure that the algorithm it's Ok
Can you show me how does your algorithm work?
My math is not good. Thanks.

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

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

I deleted the code, I think you can understend why... but I'll try to explain my algorithm...

1. You find the smallest n in that way that

1+2+...+n >= s (where s is the input)

For this you have to solve the equation in n:
n^2 + n 0 2s = 0
=> n= ceil( (sqrt(1+8s) -1)/2 )

2. Now your solution is n or n+1 or n+2, because
d=s-n*(n+1)/2 must be (even or odd I don't know very well english so I'm always in doubt wich is the word but ) d mod 2=0...



Good luck,

Carmen

Post Reply

Return to “Volume 100 (10000-10099)”