Loading ships

Submit solution
Points: 10
Time limit: 2.0s
Memory limit: 250M
Author:
moncef
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

Comments


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

    The third one is tearing me off

    Edit : Never mind I got it


  • 0
    XanaX  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?


    • 0
      aymanrs  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.


      • 0
        XanaX  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...


        • 0
          aymanrs  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


  • 0
    Mozart98  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 ?


    • 0
      saadyo  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 ?


    • 0
      aymanrs  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