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


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

      Change \(l := 1\) and \(r := 2e9\)


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

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


    • 1
      AkramElOmrani  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.


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

      Try to use long long


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


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

    Can someone tell me where is my fault


  • 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