An Animal Contest 1 P2 - Alpaca Racing

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 0.6s
Python 1.5s
Memory limit: 256M

Author:
Problem types

You have decided to enter your alpaca into the annual Alpaca Racing Tournament! The race will be run around a track of length D, and you will be competing against N other alpacas. However, your alpaca is running slower than usual because it ate too many Cheetos got injured while training for the race. Desperate to win, you hack into the tournament software containing the speeds of all alpacas to see if there is a chance of victory. The speed of the i^\text{th} alpaca is defined as a_i, and your alpaca has speed P. Soon, you realize that you have no chance of winning, but you have one more trick up your sleeve. You create a device that can reduce the speed of any alpaca, setting its new speed to \left\lfloor \text{speed} \times \frac{100-X}{100} \right\rfloor. However, due to a bug in the device, it can only be used K times. Your task is to find out if you can win if you use the device at most K times. Note that winning means that you finish in the fastest time, meaning no ties.

Constraints

For all subtasks:

1 \le N, K \le 10^6

1 \le D, P, a_i \le 10^{16}

1 \le X \le 100

Subtask 1 [10%]

X = 100

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input will contain 4 integers N, D, K, X, all separated by a space.

The next N lines will each contain a_i, denoting the speed of the i^\text{th} alpaca.

The final line of input will contain P, denoting the speed of your alpaca.

Output Specification

You are to output YES if you can win the race outright after using the device at most K times and NO otherwise.

Note: For this problem, you will NOT be required to pass the sample cases in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

Sample Input 1

2 12 3 30
100
50
50

Sample Output 1

YES

Explanation for Sample Output 1

The first alpaca finishes in 12/100 = 0.12 hours, the second one finishes in 12/50 = 0.24 hours and you finish in 12/50 = 0.24 hours.

You use the device on the first alpaca twice, bringing his speed down to \lfloor 100 \times \frac{100-30}{100} \rfloor = 70, then \lfloor 70 \times \frac{100-30}{100} \rfloor = 49. The first alpaca now finishes in 12/49 = 0.245 hours, which is slower than you. You also need to use the device once on the second alpaca. Using the device 3 times allows you to win.

Sample Input 2

4 200 1 1
1000
12
2134
22
1

Sample Output 2

NO

Comments


  • 0
    rnpmat08_v2  commented on Oct. 9, 2022, 10:27 a.m.

    If you get NumberFormatException, make sure that D, P, and ai are longs instead of ints otherwise the input won't get in properly.


  • 4
    KhaledBaccour  commented on Aug. 15, 2022, 5:40 p.m.

    I still don't get why is the distance needed when we can just compare speeds


  • 1
    Stringvalues56  commented on Aug. 13, 2022, 10:52 a.m.

    I spent an hour rethinking and verifying the correctness of my program and I kept coming back to the same result — it was correct in all respects. My output was the culprit (instead of "YES", my output was "Yes"). The judge is very strict (I'm not complaining, I'm very much aware).

    Make sure that your output is EXACTLY as described in the problem statement before you submit your code.

    Also, the first thing you should check when you get WA (especially on the first test case in any problem) is that your output is EXACTLY as described.


  • 1
    juniper3041  commented on Jan. 31, 2022, 8:47 p.m. edited

    I'm stumped. According to the judge I'm generating output (YES) but I'm also getting a TLE (Python). Huh? Do you get output if you encounter a TLE. Or is it just that my program is generating the output around the time cutoff?


    • 2
      Badmode  commented on Jan. 31, 2022, 11:26 p.m.

      Don't quote me on this, but I think it's the latency between the judge terminating the code and the code stopping - your code generated an output in that time frame


      • 1
        juniper3041  commented on Feb. 1, 2022, 5:40 a.m. edit 2

        Thank you.

        [edit] DMOJ's optimizations relevant to the judge were required for my python submission: https://dmoj.ca/tips/#python-main. But, now that I can see other solutions I see that the optimizations are not required for less convoluted solutions than mine.


  • 8
    cchungelliot  commented on Dec. 26, 2021, 5:57 p.m.

    because it ate too many Cheetos🤣


  • 11
    Badmode  commented on April 12, 2021, 10:40 p.m. edit 4

    When changing the speed another alpaca, remember to floor the alpaca's speed to pass batch #2 test case #7.

    Also, Java users should use long integers, and c++ users should use long long integers to prevent integer overflow to pass batch #2 test case #1.


    • 0
      juniper3041  commented on Feb. 1, 2022, 5:44 a.m.

      Ironically, flooring all the time is what prevented me from solving the problem.


    • 1
      wozhenshuai  commented on April 13, 2021, 1:48 a.m.

      yeah I failed on the first try because I was too rushed at the time and forgot to floor.