控控控之蘿莉控

https://tioj.ck.tp.edu.tw/problems/1828

Description

你走在路上遇到了一個可愛小蘿莉，因為你的控屬性，所以你跑上去問了她的名字：「小妹妹～你叫什麼名字啊？」
她回答：「啊！！！你幹嘛！我不認識你啊你誰啊！！！」
你：「我是你的好哥哥，來和我一起玩吧～」
這時機智的小妹妹拿起手機打了110
你決定要趕快逃跑，以免進入暗無天日的深淵

於是問題來了！
你要跑多快才不會被抓(你只能跑整數的速度)？
因為警察的體力有限，不能跑超過警局外的$10000$單位距離，所以逃出$10000$單位距離就好了

第一行有一個整數$T$代表測資筆數，
每行有三個無號整數$X,Y,Z$
$X$代表你現在跟警察局的距離，
$Y$代表小妹妹跟警察叔叔還要在$Y$秒才會講完電話，
$Z$代表講完電話後警察會馬上用秒速$Z$的速度沖上來追你
$0 \leq X,Y,Z \leq 10^6$
如果講完電話後，你還待在警察局門口，是會被抓的喔
注意你站在距警察局恰$10000$單位距離的點上也還是會被抓的喔

請輸出ㄧ個整數代表你至少要用多少的體力才不會被追悼
如果不管怎麼樣都會被追到請輸出 -1

Solution

是個大特判題呢
唯ㄧ會出現 -1 的case就是$X=Y=0$的時候，也就是ㄧ開始就被追上
首先可以知道人和警察兩個直線的差會與時間成線性
所以最小的差肯定是出現在端點
我們僅需要考慮剛出發那一刻和警察跨過$10000$那一刻，是否有被警察超前過即可
假設$T$是距離講完電話過了$T$秒，並且逃跑的速度是$V$
那麼可以列出式子

$$
X + (Y+T)V > TZ
$$

當$T$是$0$，可以知道$V$的最小值不是$0$就是$1$，取決於$X,Y$是否為0
當警察跨過$10000$時，$T=10000/Z$，移項一下可以得到$V > \frac{(10000-X)Z}{YZ+10000}$
不過注意$Z$必須不為$0$，若$Z$為$0$可以直接特判掉

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <cstdio>

typedef long long ll;

const int L = 10000;
int solve() {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    if(x == 0 && y == 0) return -1;
    if(x > L) return 0;
    if(!z) return !x;
    return (L-x) * ll(z) / (ll(z)*y + L) + 1;
    /*
    X + (Y+T)V > min(10000, TZ)
    X + (Y+T)V > TZ
    XZ + (YZ+TZ)V > TZZ
    consider T == 10000/Z and T == 0
    V > (10000-X)Z / (ZY+10000)
    X + YV > 0
    */
}
signed main() {
    int t;
    scanf("%d", &t);
    while(t--) printf("%d\n", solve());
    return 0;
}