Loading ships
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
Comments
Can anyone tell me how to pass the last 80 lines, why do i get TLE and i use binary search
Change \(l := 1\) and \(r := 2e9\)
I don't know where is the problem in my code
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.
Try to use long long
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.
Can someone tell me where is my fault
The third one is tearing me off
Edit : Never mind I got it
I always get WA in the second test,, I don't know which test case my code doesn't work correctly with it?
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.
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...
I tested your code for X = 2 and it needed 32 trials. the solution is very simple : start with lastright = 2e9 and right = 1e9
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 ?
I have the same probleme how can you give answers without print them I mean the x that we going to look for ?
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
.