Уповільнений Спринт#12234

Уповільнений Спринт (Розбір)

Автор задачі:	Imran AKKI
Підготовка:	Imran AKKI
Редагування:	Hasan Saleh (MathModel)

Розв'язання Задача зводиться до знаходження загальної відстані, яку пройшов кожен учасник, і підрахунку тих, хто пробіг строго більше, ніж Боб.

Просимулюємо загальну відстань для швидкості $s$ і зменшення швидкості $t$ : на кожному кроці ви зменшуєте початкове $s$ на кратне $t$ , доки воно позитивне. Формально, загальна відстань $d$ буде

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

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

Тут $k = ⌊ \frac{s - 1}{t} ⌋$ k=\lfloor \frac{s-1}{t} \rfloor — це максимальна кількість кроків із позитивною швидкістю.

Щоб порахувати відстань, помітимо, що $s$ зустрічається $k + 1$ k+1 разів, і ми маємо $(1 + 2 + 3 + ... + k) t$ (1+2+3+...+k)t у від'ємній частині. А ми знаємо, що $1 + 2 + 3 + ... + k = \frac{k ( k + 1 )}{2}$ 1+2+3+...+k=\frac{k(k+1)}{2}, тоді загальна відстань обчислюється як

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

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

Тепер за цим обчислюємо відстань для $i$ -го учасника як $d_{i}$ d_i, сортуємо значення і рахуємо, скільки бігунів пробігли більше за Боба.

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

Складність $O (n lo g n)$ \mathcal{O}(n \log n).