Yavaşlama Sprinti#12234

Yavaşlama Sprinti (Həll təhlili)

Problem müəllifi:	Imran AKKI
Hazırlayan:	Imran AKKI
Redaktor:	Hasan Saleh (MathModel)

Həll Problemi, hər iştirakçının qət etdiyi ümumi məsafəni tapmaq və Bobdan daha çox məsafə qət edən iştirakçıların sayını hesablamaq kimi düşünmək olar.

Məsafəni simulyasiya etmək üçün sürət $s$ və sürət azalması $t$ üçün, hər addımda ilkin $s$ -ni $t$ vahidlərinin çoxluğu qədər azaltmağa davam edirsiniz, yalnız $s$ müsbət olduğu müddətcə. Rəsmi olaraq ümumi məsafə $d$ belə olacaq:

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

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

Burada $k = ⌊ \frac{s - 1}{t} ⌋$ k=\lfloor \frac{s-1}{t} \rfloor — əldə edilə biləcək maksimum müsbət sürətdir.

Məsafəni hesablamaq üçün, $s$ $k + 1$ k+1 dəfə təkrarlanır və mənfi hissədə $(1 + 2 + 3 + ... + k) t$ (1+2+3+...+k)t var, və $1 + 2 + 3 + ... + k = \frac{k ( k + 1 )}{2}$ 1+2+3+...+k=\frac{k(k+1)}{2} olduğunu bildiyimiz üçün ümumi məsafə belə hesablanır:

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

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

Buna görə də, $i$ -ci iştirakçının məsafəsini $d_{i}$ d_i kimi hesablayın, dəyərləri sıralayın və Bobdan daha çox qaçan iştirakçıların sayını tapın.

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

Çətinlik $O (n lo g n)$ \mathcal{O}(n \log n).