Sprint de Ralentissement#12234

Sprint de Ralentissement (Corrigé)

Auteur du problème :	Imran AKKI
Préparé par :	Imran AKKI
Édité par :	Hasan Saleh (MathModel)

Solution Le problème revient à obtenir la distance totale parcourue par chaque concurrent et à calculer combien de concurrents ont parcouru strictement plus que Bob.

Simulons la distance totale parcourue pour une vitesse $s$ et une diminution de vitesse $t$ : à chaque étape, on continue à diminuer $s$ d'un multiple de $t$ tant que la vitesse reste positive. Formellement, la distance totale $d$ sera :

d = s + (s - t) + (s - 2 t) + (s - 3 t) + .... + (s - k t)

\displaystyle d=s+(s-t)+(s-2t)+(s-3t)+....+(s-kt)

Ici $k = ⌊ \frac{s - 1}{t} ⌋$ k=\lfloor \frac{s-1}{t} \rfloor, ce qui est la vitesse positive maximale atteignable.

Pour calculer la distance, notez que $s$ apparaît $k + 1$ k+1 fois et que nous avons $(1 + 2 + 3 + ... + k) t$ (1+2+3+...+k)t comme partie négative, et on sait que $1 + 2 + 3 + ... + k = \frac{k ( k + 1 )}{2}$ 1+2+3+...+k=\frac{k(k+1)}{2}. Ainsi, la distance totale est calculée comme :

= s \times (k + 1) - t \times \frac{k ( k + 1 )}{2}

\displaystyle = s \times (k+1) - t \times \frac{k(k+1)}{2}

Selon cela, calculez la distance pour le $i_{e ˋ m e}$ i_{ème} concurrent comme $d_{i}$ d_i, triez les valeurs et comptez combien de concurrents ont couru plus que Bob.

for _ in range(int(input())):
    n,b=map(int,input().split())
    s=list(map(int,input().split()))
    t=list(map(int,input().split()))
    a=[]
    want=-1
    for i in range(n):
        x=s[i]
        r=(s[i]-1)//t[i]
        x+=s[i]*r
        v=(r*(r+1))//2
        x-=v*t[i]
        a.append(x)
        if(i+1==b):
            want=x
    a.sort()
    ans=1
    for i in range(n-1):
        if(a[i]==want and a[i+1]>want):
            ans=n-i
            break
    print(ans)

Python

Complexité $O (n lo g n)$ \mathcal{O}(n \log n).