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

**Moderator:** Board moderators

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

The problem description doesn't say that the first input is the number

of items to process! Please fix this!

-Chris

of items to process! Please fix this!

-Chris

### Doh!

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.

-Chris

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.

-Chris

### 10025

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!

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

### 10025

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]

[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]

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

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]

[c]

deleted

[/c]

Last edited by pc5971 on Tue Jan 21, 2003 7:49 am, edited 1 time in total.

### 10025

[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....

#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....

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