Favorite Numbers

View as PDF

Submit solution

Points: 5
Time limit: 0.6s
Java 1.0s
Python 2 4.0s
Python 3 4.0s
Turing 4.0s
Memory limit: 256M

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

When asked what his Favorite Number is, Joey cannot respond! He likes a lot of numbers! In particular, he has a list of N (1 \leq N \leq 100\,000) numbers that are his Favorite Numbers. Numbers might appear more than once on his list of Favorite Numbers, but that's okay, since it means that he really, really likes that number.

Joey is given Q (1 \leq Q \leq 100\,000) numbers, but these numbers might not be one his Favorite Numbers. For each number that he is given, he would like the smallest Favorite Number that is at least as large as the number he is given. He would also like to know how many times that Favorite Number appears in his list of Favorite Numbers.

Please help Joey!

Input Specification

The first line will contain N: the size of Joey's list of Favorite Numbers.

The next line will contain N space-separated integers: the numbers that are in Joey's list of Favorite Numbers, in no particular order.

The next line will contain Q: the amount of numbers Joey is given.

Q lines of input will follow. Each line will contain one integer: one number that Joey is given.

The absolute value of any integer will not exceed 10^9. It is guaranteed that no number given to Joey will exceed the largest number in his list.

Output Specification

On separate lines, for each number that Joey is given, output two space-separated integers: the smallest Favorite Number that is at least as large as the number given, and how many times it appears in Joey's list of Favorite Numbers.

Sample Input

10
-2 8 -100 19 -2 -2 8 -100 8 8
5
6
8
17
-1000
-10

Sample Output

8 4
8 4
19 1
-100 2
-2 3

Comments


  • 3
    ross_cleary  commented on July 13, 2020, 10:11 p.m.

    Data structures tag seems more appropriate.


  • 3
    DKLS2  commented on April 30, 2017, 6:16 p.m.

    Grammar

    not be one his Favorite Numbers.

    The first sentence of the second paragraph.


  • 1
    ZQFMGB12  commented on Aug. 14, 2016, 1:12 p.m.

    The time limit for this problem has been increased to 4 seconds and the memory limit has been increased to 256 MB in order to allow correct submissions in slower languages (such as Java and Python) to pass.


  • 2
    Zander  commented on Aug. 4, 2016, 12:22 a.m.

    Or only the smallest favourite number greater than the given number?


    • 1
      ZQFMGB12  commented on Aug. 4, 2016, 1:44 p.m.

      Sorry, did not realize that. The problem description has been updated.


    • 1
      anishmahto  commented on Aug. 4, 2016, 1:03 p.m.

      I solved for the smallest favourite number greater than the given number, and it worked. So probably just the smallest favourite number, greater than the given number.