RGPC '17 P2 - Cubes are Life

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

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

Because Gabriel got an early offer from UOIT, his overjoyed parents gave him a lot of Rubik's Cubes as a reward. However, he soon developed Carpal Tunnel Syndrome, and now has to sell some of his cubes at half of their original price to pay for his medical bills.

Gabriel is a very unique person; the N cubes that he got each have a distinct value V_i, and are placed in a straight line. He wants to know if he has a total of at least M dollars after he sells all of his cubes inclusively between the one valued at V_a and the one valued at V_b (in the line). He specifically wants to ask Q questions in the form (V_a, V_b) to know if he has enough money after selling all of the cubes in that range. Both cubes are guaranteed to exist in the sequence.

Note: it may be helpful to use unsigned 64-bit variables (e.g. unsigned long long in C++).


Subtask 1 [10%]
  • 1 \le N, Q \le 100
  • 1 \le M, V \le 1\,000
Subtask 2 [90%]
  • 1 \le N, Q \le 100\,000
  • 1 \le M \le 10\,000\,000
  • 1 \le V \le 1\,000\,000

Input Specification

The first line of input will consist of 3 space-separated integers N, M, and Q. The next line will contain N space-separated integers, where the i^{th} integer represents the {V_i}^{th} value. For the next Q lines, each line will contain 2 space separated integers V_a and V_b.

Output Specification

For each question, output Enough if Gabriel can afford his bills or Not enough if he cannot.

Sample Input

5 10 2
10 1 4 3 7
1 3
10 7

Sample Output

Not enough


  • 2
    root  commented on May 18, 2017, 6:16 p.m.

    Some AC submissions have precision issues. Proposed test case:

    2 2 1
    1 3
    1 3

    • 0
      chenj  commented on May 19, 2017, 6:47 p.m.

      Thanks for pointing that out; the test data has been updated. Incorrect solutions should not pass now.

    • -1
      Ninjaclasher  commented on May 19, 2017, 5:56 p.m.

      So basically what it does is instead of being able to do (priceOfCube/2), you would have to do (priceOfCude>>1) for C++.

  • 0
    moladan123  commented on Feb. 17, 2017, 10:42 p.m.

    This problem is extremely similar to DMOPC '14 Contest 2 P4 - Deforestation. Just for the record.

    • 3
      Dankat  commented on Feb. 17, 2017, 10:56 p.m.

      It's a coincidence and there is a slight difference.

  • -2
    jimgao  commented on Feb. 13, 2017, 2:14 p.m.

    Are the prices multiples of 2?

    • 0
      chenj  commented on Feb. 13, 2017, 4:50 p.m.

      Not necessarily. If the total price after halving isn't exactly M or greater, then it's Not enough.