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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Plz Hlp me in prob-10025.I've got TLE.

Here is my code.Plz tell me why I got TLE.
#include <stdio.h>
#include <math.h>

void main()
{
long k,n,test,s,i,d;
scanf("%d",&test);
while(test--)
{
scanf("%ld",&k);
k=labs(k);
n=sqrt(2*k);
for(i=n;1;i++)
{
s=((n*(n+1))/2);
if(s>=n)
{
d=s-n;
if(!(d%2))
{
printf("%ld\n",i);
break;
}
}
}
}
}

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

tienlex
New poster
Posts: 2
Joined: Thu Oct 11, 2007 10:01 am
Hi there,

I got WA of 10025 problem. i tested many test with some special cases and also output with blank line between each case.

Still get WA ?! why ?

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>

using namespace std;

void solve()
{
unsigned long long i,root;
int n;
int k;
unsigned long long sum;
bool found;
scanf("%d",&n);
while (n>0)
{
scanf("%d",&k);
k=abs(k);

//root = sqrt(1+8*k); //sqrt(*sqrt(k);
i=ceil((-1+sqrt(1+8*k))/2);

if (root==0 || k==0)i=1;
while(true)
{
sum = i*(i+1)/2;
if (k==sum || (sum>k && (sum-k)%2==0))
{
break;
}
i++;
}
if (n==1)
printf("%u", i);
else
printf("%u\n\n", i);
n--;
}
}

int main()
{
//freopen("btin.txt","rt",stdin);
//freopen("btout.txt","wt",stdout);
solve();
return 0;
}

Here some test cases and output i tested:
INPUT:
8

3

0

1

1

12

-3646397

1000000000

-1000000000

OUTPUT:
2

3

1

1

7

2701

44723

44723

Does i have any mistake ?

thanks.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
The identifier for 'unsigned long long' is '%llu'.
Ami ekhono shopno dekhi...
HomePage

tienlex
New poster
Posts: 2
Joined: Thu Oct 11, 2007 10:01 am
thanks Guru. but still got WA +_+

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Cheque this cases

Code: Select all

Input:
11
1000000000
-1000000000
999999999
-999999999
9999999
-999999
0
1
-1
2
-2
Output:
44723

44723

44721

44721

4473

1414

3

1

1

3

3
Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

Unioeste_Brazil
New poster
Posts: 2
Joined: Tue Aug 21, 2007 4:09 am

10025 - Wrong Answer

I tried severals entries. All answers are corrects. I thinking what may be wrong...

Code: Select all

#include <iostream>
#include <fstream>

using namespace std;

int main(void){
long long int num, soma;
int cases;
cin >> cases ;
cout << cases<<endl;

for(int k=0; k<cases; k++){
cin>> num;
long long int soma = 0;
long long int i= 0;
if(num < 0)
num = num * -1;
while(soma < num){
i++;
soma = soma +i;
}
if(num == 0)
i = 3;
if((soma-num)%2)
if(i%2)
i +=2;
else
i++;
cout << i << "\n\n" ;
}
return 0;
}
http://icpcres.ecs.baylor.edu/onlinejud ... ID+6311740

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

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

I think it's quiet strange to have wa after checking the test case above.(unless going on with a wrong idea)
Any way thanks to sapnil vai for this post. I was wrong with the input 0. try_try_try_try_&&&_try@try.com
This may be the address of success.

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

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

Code: Select all

code accepted
Last edited by raj on Thu Mar 07, 2013 5:48 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

The Input

Each test case will be separated by a single line.

https://ideone.com/gNuAiw
Exception in thread "main" java.lang.NumberFormatException: For input string: "" at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65) at java.lang.Long.parseLong(Long.java:453) at java.lang.Long.valueOf(Long.java:540) at Main.main(Main.java:13)
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

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

thanks sir@brain fry now its accepted Joth
New poster
Posts: 11
Joined: Sat Mar 10, 2007 8:29 pm

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

Hi - I am having a lot of trouble with this problem.
uDebug is telling me I have the right answers for the inputs I give it - and I have given it at least a couple thousand values including -1000000000, 1000000000, and all numbers from -300 to +300
Could anyone suggest an input I am missing? This is my code in java:

Code: Select all

import java.util.Scanner;
import java.io.File;
import java.util.Arrays;
import java.io.PrintWriter;

public class Main
{
public static void main(String[] args) throws Exception
{
//Scanner inp = new Scanner(new File("in.txt"));
Scanner inp = new Scanner(System.in);

int cases = inp.nextInt();
while( cases > 0 )
{
inp.nextLine(); //blank line
long k = inp.nextLong();
k = Math.abs(k);

int n = (int)Math.ceil((-0.5 + Math.sqrt(2*k+0.25)));
if( n == 0 ) n = 1;

long res = (n*n+n)/2;
long diff = res - k;
String output = "";
if( diff % 2 == 0 )
{
output = n + "\n";
}
else
{
diff += n+1;
if( diff % 2 == 0 )
{
output = (n+1) + "\n";
}
else
{
output = (n+2) + "\n";
}
}
System.out.println( output );
cases--;
}
}
}
Thanks!

Eucliwood
New poster
Posts: 3
Joined: Mon May 30, 2016 1:07 pm

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

For you guys that get TLE, try this algorithm, it's not very fast, but good enough

You only need to check if, say S is the total sum from 1 to n, then check if S-k is even and larger than -1