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

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

### 11614

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

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

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

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

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

I used 'unsigned long long'

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

### Re: 11614

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

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

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

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

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

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

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

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!