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^{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$ $⌊ speed \times \frac{100 - X}{100} ⌋$ . 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 \leq N, K \leq 10^{6}$

$1 \le D, P, a_i \le 10^{16}$ $1 \leq D, P, a_{i} \leq 10^{16}$

$1 \le X \le 100$ $1 \leq X \leq 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^{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

Copy

Sample Output 1

Copy

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$ $⌊ 100 \times \frac{100 - 30}{100} ⌋ = 70$ , then $\lfloor 70 \times \frac{100-30}{100} \rfloor = 49$ $⌊ 70 \times \frac{100 - 30}{100} ⌋ = 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

Copy

Sample Output 2

Copy

NO

Comments

1

EthanHardie commented 74 days ago ← 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)$ $f l o o r (s p e e d * (100 - X) / 100)$

0

y889 commented 74 days ago

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 :)

0

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$ $⌊ speed \times \frac{100 - X}{100} ⌋$ 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