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.

Post by asif_rahman0 » Tue Jan 18, 2005 6:42 pm

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

Post by .. » Tue Jan 18, 2005 6:59 pm

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

Post by tienlex » Sun Oct 14, 2007 10:53 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Oct 17, 2007 9:50 pm

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

Post by tienlex » Sun Oct 21, 2007 9:05 am

thanks Guru. but still got WA +_+

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

Post by sapnil » Sun Oct 21, 2007 1:28 pm

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

Post by Unioeste_Brazil » Tue Mar 18, 2008 6:25 am

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
Location: (BUBT) Dhaka,Bagladesh.

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

Post by Obaida » Fri Dec 11, 2009 8:07 pm

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

Post by raj » Fri Mar 01, 2013 10:07 am

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

Post by brianfry713 » Fri Mar 01, 2013 11:54 pm

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

Post by raj » Tue Mar 05, 2013 10:01 pm

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

Post by Joth » Sun Apr 03, 2016 2:26 am

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

Post by Eucliwood » Wed Jun 22, 2016 9:36 am

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

Post Reply

Return to “Volume 100 (10000-10099)”