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

[asif_rahman0]

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

[..]

http://online-judge.uva.es/board/viewto ... 0902#30902

[tienlex]

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]

The identifier for 'unsigned long long' is '%llu'.

[tienlex]

thanks Guru. but still got WA +_+

[sapnil]

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

[Unioeste_Brazil]

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]

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.

[raj]

Code: Select all

code accepted

[brianfry713]

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)

[raj]

thanks sir@brain fry now its accepted

[Joth]

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]

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