Points: 10
Time limit: 2.0s
Memory limit: 250M

Author:
Problem type

You own a ship that can store up to $$N$$ Kg of goods ($$1 \leq N \leq 2 \times 10^9$$). You don't know $$N$$ and you want to determine it by experience.

You can make up to 31 trials, in each trial you can load $$x$$ Kg of goods. If $$x > N$$ the ship sinks, if $$x < N$$ it floats.

#### Interaction protocol

To make a trial your program needs to output $$x$$ ($$1 \leq x \leq 2 \times 10^9$$) to stdout. After that the grader will output a single line to stdin, depending on $$x$$, that your program should read.

• If $$x > N$$ the grader will output SINKS, after reading this response your program should make another trial.
• If $$x < N$$ the grader will output FLOATS, after reading this response your program should make another trial.
• If $$x = N$$ the grader will output OK, after reading this response your program should terminate.

Each time you output a number, you need to output a new line and flush your output buffers. For example, in Python you can do this with import sys; sys.stdout.flush(), and in Java with System.out.flush().

After the $$31^{st}$$ trial, your program should terminate.

#### Sample Interaction

>>> denotes your output; you should not be printing it.

>>> 1
FLOATS
>>> 2
FLOATS
>>> 10
FLOATS
>>> 45
SINKS
>>> 11
OK

• commented on Jan. 5, 2023, 8:17 p.m.

Can anyone tell me how to pass the last 80 lines, why do i get TLE and i use binary search

• commented on Jan. 6, 2023, 12:57 p.m. edited

Change $$l := 1$$ and $$r := 2e9$$

• commented on Dec. 24, 2022, 9:32 p.m.

I don't know where is the problem in my code

• commented on Dec. 25, 2022, 12:58 p.m. edit 3

you have an overflow here : $\text{midpoint} = \text{(lower_bound + upper_bound) >> 1}$ this will help $\text{midpoint} = \text{(lower_bound + (upper_bound - lower_bound) / 2;}$ (Also don't use bit shifts for computing midpoint if you use $$\text{stdc++20}$$ there is $$\text{std::midpoint}$$ or just divide by $$2$$ trust me I learnt it the hard way.

• commented on Dec. 24, 2022, 10:48 p.m.

Try to use long long

• commented on Nov. 9, 2021, 3:52 p.m.

I am completely stuck on how to read the "output" in Python (sinks, floats, ok). I can't look up how to do so because I don't know what to call it in the first place. I can output numbers and whatnot, but other than that I can't do anything else.

• commented on July 8, 2021, 7:47 p.m.

Can someone tell me where is my fault

• commented on March 23, 2021, 2:19 a.m. edited

The third one is tearing me off

Edit : Never mind I got it

• commented on Oct. 13, 2020, 12:17 a.m.

I always get WA in the second test,, I don't know which test case my code doesn't work correctly with it?

• commented on Oct. 14, 2020, 4:08 p.m.

Read the problem carefully and especially the constraints. A good practice is to test (if possible) the edge cases in your machine. Run your code on your PC with x = 2e9 and x = 1 to verify that it doesn't require more than 31 trials and gives the correct answer.

• commented on Oct. 18, 2020, 4:39 p.m.

yes i know it's about binary search [log(2e9)=30,9~31].. but i don't know why specially the second test,, and not others! anyway, i will keep trying...

• commented on Oct. 18, 2020, 6:31 p.m. edited

I tested your code for X = 2 and it needed 32 trials. the solution is very simple : start with lastright = 2e9 and right = 1e9

• commented on June 28, 2020, 1:14 a.m.

I'm not sure wether i knew what the problem demand, i mean the intercation. especially this sentence denotes your output; you should not be printing it. Thanks if u have a clear idea about it ?

• commented on Nov. 4, 2020, 3:03 a.m.

I have the same probleme how can you give answers without print them I mean the x that we going to look for ?

• commented on June 28, 2020, 1:47 p.m.

It's like if a real person executes your program. It reads the output and gives an input accordinly. btw in C++ use std::endl it makes a new line and flushes automaticly

• commented on March 4, 2022, 12:20 a.m. edit 4

.