Uneven Sand

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Having just landed in the desert Kira remembers that his Strike Gundam is not yet programmed for sand environments. He needs to determine the right amount of pressure N that the Strike needs to exert on the sand so that it will neither sink nor float. In other words, he needs the pressure to be an exact number. He knows that the maximum pressure that needs to be exerted is 2 \times 10^9 and the minimum pressure is 1. He wants to find this number N in at most 31 guesses.

Interaction

This is an interactive problem. Your program will keep outputting numbers between 1 and 2 \times 10^9 inclusive and reading a line of input after each output. The line your program reads will be FLOATS if your guess for the pressure is too high, SINKS if your guess for the pressure is too low, and OK if you have the right number. At this point, 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().

Sample Interaction

>>> denotes your output; don't actually print this out.

>>> 1
SINKS
>>> 6
SINKS
>>> 10
SINKS
>>> 40
FLOATS
>>> 32
OK

Comments


  • 0
    goatMan  commented on July 15, 2020, 2:15 a.m. edited

    Any reason why I TLE on case 3? My solution should take the same amount of time for each question if I'm using binary search to solve.

    EDIT: Nvm, I think I got it. Disregard.


  • -4
    nsyne  commented on Nov. 12, 2019, 4:42 p.m.

    I'm getting AC on every case but TLE on the 2nd one


    • 2
      kingW3  commented on Nov. 12, 2019, 5:09 p.m. edited

      Perhaps you should read the comments, the person below had the same problem as you...


  • 3
    xxsc  commented on Aug. 31, 2019, 9:06 p.m.

    What is wrong with int

    Why can't I use int? I switched to long long and then it passed


    • 8
      magicalsoup  commented on Aug. 31, 2019, 9:15 p.m. edited

      Because you mostly might be doing (left+right) / 2, when left =2 \times 10^9 and right = 2 \times 10^9, it would overflow a 32-bit data type. This is why you need to use a 64-bit data type. The likely reason for your TLE verdict is mostly because you overflowed, and thus the variables went to negative (this is what happens when data types overflow), so your while loop went on forever.


  • 1
    MioSenpai  commented on Oct. 20, 2018, 11:58 p.m.

    Shinn > Kira