An Animal Contest 1 P2 - Alpaca Racing - DMOJ: Modern Online Judge

An Animal Contest 1 P2 - Alpaca Racing

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$ ~D~, and you will be competing against $N$ ~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}$ ~i^\text{th}~ alpaca is defined as $a_i$ ~a_i~, and your alpaca has speed $P$ ~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$ ~K~ times. Your task is to find out if you can win if you use the device at most $K$ ~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 N, K \le 10^6~

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

$1 \le X \le 100$ ~1 \le X \le 100~

Subtask 1 [10%]

$X = 100$ ~X = 100~

Subtask 2 [90%]

No additional constraints.

Input Specification

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

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

The final line of input will contain $P$ ~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$ ~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

Sample Output 1

YES

Explanation for Sample Output 1

The first alpaca finishes in $12/100 = 0.12$ ~12/100 = 0.12~ hours, the second one finishes in $12/50 = 0.24$ ~12/50 = 0.24~ hours and you finish in $12/50 = 0.24$ ~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$ ~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$ ~3~ times allows you to win.

Sample Input 2

Sample Output 2

NO

Comments

1

EthanHardie commented on Jan. 9, 2025, 7:14 p.m. ← edit 2 →

To clarify any confusion, if the result of the speed equation is not an integer, it must be rounded down to the nearest integer:

$floor(speed * (100 - X) / 100)$ ~floor(speed * (100 - X) / 100)~

0

y889 commented on Jan. 9, 2025, 7:15 p.m.

Thanks so much! I was having major problems, then I saw this comment which helped me. The author may need to update to add additional information as to not potentially confuse newcomers.

0

payday2 commented on Oct. 9, 2024, 12:46 a.m.

I keep on getting the wrong answer for the 2nd problem and have no idea why. Any help?

2

ev_code commented on Oct. 10, 2024, 7:04 p.m.

Hello! Keep in mind that the question asks for d / speeds[i]. Not only speeds[i]! Also, you need to account for ties, as ties still count as "NO". I'm not too familiar with the java mechanics though, because it does get IR on test case 3 (but it passes test case 2!)

0

HisMonDon commented on Oct. 2, 2024, 2:51 p.m.

Can someone tell me why im failing test case 7 in subtask 2?

1

ev_code commented on Oct. 2, 2024, 8:54 p.m.

I was very confused too. It turns out, make sure that the alpaca speeds are typecasted to integers, or else funky dmoj stuff happens. Let me know if this helps :)

1

EthFng64 commented on Sept. 13, 2024, 12:35 a.m.

cheeto diet time

-1

hungrybeagle commented on Feb. 21, 2024, 1:16 a.m.

Nowhere in the problem do I read that the alpaca speeds (after using the device) must be integer values. This has a huge impact on the problem.

5

JoshC commented on Feb. 23, 2024, 8:37 p.m. ← edited →

the statement $\displaystyle \left\lfloor \text{speed} \times \frac{100-X}{100} \right\rfloor$ uses the floor function, which rounds down to the nearest integer.

0

teddycitrus commented on Dec. 15, 2023, 11:03 p.m. ← edited →

Im missing something, why does $D$ ~D~ matter? As far as I could tell, the objective is to calculate the speed of the $K$ ~K~ fastest opponents after using the device as much as possible and then check if your alpaca is the fastest afterwards. so why does $D$ ~D~ matter? im sure it does have a part in the answer but i can't see how can someone help

-1

teddycitrus commented on Dec. 16, 2023, 1:31 p.m.

sorry i did not know editorials could be used like that