11614 - Etruscan Warriors Never Play Chess

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
crazy
New poster
Posts: 1
Joined: Tue Jul 17, 2012 5:48 am

11614

Post by crazy » Tue Jul 17, 2012 6:12 am

it gave me wrong answer ...

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
long int x,n,m,k,i;
scanf("%ld",&k);
for(i=0;i<k;i++)
{
    scanf("%ld",&n);
{
    m=(1+8*n)-1;
    x=sqrt(m)/2;
printf("%ld\n",x);
}}
return 0;
}

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

Re: 11614

Post by brianfry713 » Wed Jul 18, 2012 12:10 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

tarsun
New poster
Posts: 7
Joined: Thu Sep 20, 2012 7:58 pm
Contact:

11614 - Etruscan Warriors Never Play Chess

Post by tarsun » Thu Sep 20, 2012 8:10 pm

Why gave time limit exceed??

#include<stdio.h>

int main()
{
long int n,i,sum,f,x,test,t1;
scanf("%ld",&test);
for(t1=1;t1<=test;t1++)
{ sum=0;
scanf("%ld",&n);
for(i=1;;i++)
{
sum=sum+i;
if(sum==n)
{
printf("%ld",i);
break;
}
if(sum>n)
{
x=i-1;
printf("%ld",x);
break;
}

}
}
return 0;

}

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

Re: 11614

Post by brianfry713 » Thu Sep 20, 2012 9:09 pm

Input:

Code: Select all

1
100000000000000
AC output:

Code: Select all

14142135
Check input and AC output for thousands of problems on uDebug!

tarsun
New poster
Posts: 7
Joined: Thu Sep 20, 2012 7:58 pm
Contact:

Re: 11614

Post by tarsun » Sat Sep 22, 2012 6:06 pm

is it correct code?
which datatype used for this program?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11614

Post by helloneo » Sun Sep 23, 2012 5:39 pm

I used 'unsigned long long'

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

Re: 11614

Post by raj » Thu Sep 19, 2013 9:13 pm

Code: Select all

Accepted
and Thanks Brianfry:)
Last edited by raj on Sat Sep 28, 2013 11:47 pm, edited 3 times in total.

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

Re: 11614

Post by brianfry713 » Thu Sep 19, 2013 9:36 pm

There is a formula, I didn't precompute anything.
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: 11614

Post by raj » Fri Sep 20, 2013 5:48 pm

Code: Select all

removed
Last edited by raj on Tue Sep 24, 2013 6:55 am, edited 1 time in total.

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

Re: 11614

Post by brianfry713 » Fri Sep 20, 2013 9:30 pm

Don't double post.
Check input and AC output for thousands of problems on uDebug!

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re: 11614 - Etruscan Warriors Never Play Chess

Post by ssavi » Mon Dec 08, 2014 6:03 pm

Why It is getting TLE ?? Is there any correction ???

Code: Select all

#include<stdio.h>
int main()
{
    long long int n, i, t, sum;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        sum=0; i=1;
        while(sum<n)
        {
            sum=sum+i;
            i++;
        }
        if(n<sum)
           {printf("%lld\n",i-2);}
        else if(n==sum)
            printf("%lld\n",i-1);
    }
    return 0;
}
I know I am a Failure Guy . :(

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

Re: 11614 - Etruscan Warriors Never Play Chess

Post by brianfry713 » Mon Dec 08, 2014 10:31 pm

You can solve each test case in constant time.
Check input and AC output for thousands of problems on uDebug!

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re: 11614 - Etruscan Warriors Never Play Chess

Post by ssavi » Tue Dec 09, 2014 5:22 am

brianfry713 wrote:You can solve each test case in constant time.
I dont get your words .
I know I am a Failure Guy . :(

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

Re: 11614 - Etruscan Warriors Never Play Chess

Post by brianfry713 » Wed Dec 10, 2014 1:25 am

Your algorithm is too slow, it runs in O(n) for each test case. To solve it within the time limit, you can use a O(1) formula.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 116 (11600-11699)”