Page **1** of **1**

### 12908 - The book thief

Posted: **Mon Apr 13, 2015 9:49 pm**

by **HitmanBBa**

I solved this problem using Binary search O(Log n) using c++ and my time 0.825 out of 1.000 second, I think there is O(1) solution can any one help me with a topic or hint ??

thanks in advance

### Re: 12908 - The book thief

Posted: **Tue Apr 14, 2015 12:22 am**

by **brianfry713**

My O(1) approach AC in 0.148 seconds.

n = number of pages in the book

x = forgotten page

s + x = n * (n + 1) / 2

Temporarily assume the minimum value of 1 for x, solve for n using the quadratic equation and round up, then x = n * (n + 1) / 2 - s

### Re: 12908 - The book thief

Posted: **Sun Jul 19, 2015 8:34 am**

by **crazytim**

I got TLE for the first time. And I also tried the following tips for I/O:

Code: Select all

```
ios_base::sync_with_stdio(0);
cin.tie(0);
```

But I still got TLE. Finally, I use scanf/printf instead of cin/cout, and got Accepted with 0.142s.

In my experience, the difference between these two approaches wasn't too much. I wonder why it is not true in this problem

### 12908 - The book thief (Getting TLE)

Posted: **Tue Jul 28, 2015 11:36 pm**

by **Adnan_Sarker**

i am getting TLE with this code, can anyone tell me why i get TLE ?

i

Code: Select all

```
LL n,ans,mp,p,an,N,NN;
while(cin>>n)
{
if(n==0){return 0;}
NN=n*2;
ans=sqrt(NN);
N=ans+5;
for(int i=ans;i<=N;i++)
{
an=(i*(i+1))/2;
if(an>=n){p=i; mp=an-n; break;}
}
if(mp==0){p=p+1; mp=((p*(p+1))/2)-n;}
cout<<mp<<" "<<p<<endl;
}
```

### Re: 12908 - The book thief

Posted: **Wed Jul 29, 2015 4:05 pm**

by **Adnan_Sarker**

Yes i got it. its a realy so nice & simple problem. oj give me TLE using for cin && cout.

by the way, i got ac