Carrera de Desaceleración#12234

Carrera de Desaceleración (Editorial)

Autor del Problema:	Imran AKKI
Preparado por:	Imran AKKI
Editado por:	Hasan Saleh (MathModel)

Solución El problema es equivalente a obtener la distancia total recorrida por cada concursante y calcular cuántos concursantes viajaron estrictamente más que Bob.

Simulemos la distancia total recorrida para alguna velocidad $s$ y decremento de velocidad $t$ ; en cada paso continuaremos disminuyendo el $s$ original por un múltiplo de $t$ mientras sea positivo. Formalmente, la distancia total $d$ será

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

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

Aquí $k = ⌊ \frac{s - 1}{t} ⌋$ k=\lfloor \frac{s-1}{t} \rfloor , que es la máxima velocidad positiva que podemos alcanzar.

Para calcular la distancia, notemos que $s$ aparece $k + 1$ k+1 veces y tenemos $(1 + 2 + 3 + ... + k) t$ (1+2+3+...+k)t como parte negativa y sabemos que $1 + 2 + 3 + ... + k = \frac{k ( k + 1 )}{2}$ 1+2+3+...+k=\frac{k(k+1)}{2}, entonces la distancia total se calcula como

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

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

Ahora, según esto, calcula la distancia para el $i_{t h}$ i_{th} concursante como $d_{i}$ d_i, ordena los valores y cuenta cuántos concursantes corrieron más 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

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