Editing 1102 - Bile 2

Pe o masă cad <code>n</code> bile săltăreţe. Fiecare este lăsată să cadă liber de la o înălţime <code>h</code>, diferită pentru fiecare bilă. Toate bilele cad simultan, cu o viteză constantă <code>(1m/s)</code> .

În momentul în care bila <code>i</code> atinge masa, tendinţa ei va fi să se ridice în aer până la înălţimea <code>h - k</code>, după care aceasta cade din nou. De fiecare dată când o bilă atinge masa, aceasta va tinde să urce la o înlăţime cu <code>k</code> mai mică decât cea la care a urcat anterior. Dupa multe sărituri, bilele pot obosi şi nu vor mai sări. Când bilele sar în sus, vor urca tot cu aceeaşi viteza constantă.

Dându-se <code>h</code> şi <code>k</code> pentru fiecare dintre cele <code>n</code> bile, să se răspundă la <code>m</code> întrebări de forma: La ce înălţime faţă de masă se va afla bila <code>x</code> în momentul <code>t</code> ?

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conţine pe prima linie 2 numere naturale <code>n</code> şi <code>m</code>. Pe următoarele <code>n</code> linii se află o pereche de numere, <code>h</code> şi <code>k</code> . Următoarele <code>m</code> linii vor conţine <code>2</code> numere naturale <code>x</code> şi <code>t</code> cu semnificaţiile de mai sus.

= Date de ieşire =
În fişierul de ieşire <code>output.txt</code> se vor afişa <code>m</code> linii, răspunsurile la cele <code>m</code> întrebări.

= Restricţii =

* <code>1 ≤ n, m ≤ 100.000</code>

== Exemplul 1 ==
input.txt:

2 3

5 1

8 2

1 4

1 7

2 16

output.txt:

1

2

4

Explicație:

Bila <code>1</code> cade de la înălţimea <code>5</code> timp de <code>4</code> secunde apoi se opreşte la înălţimea <code>1</code>.

Bila <code>1</code> cade de la înălţimea <code>5</code> şi atinge pământul, iar în cele <code>2</code> secunde rămase ajunge la înălţimea <code>2</code>.

Bila <code>2</code> cade de la înălţimea <code>8</code>, atinge pământul şi apoi ajunge la noua sa înălţime maximă, <code>6</code>, în <code>14</code> secunde. în cele <code>2</code> secunde rămase, bila apucă să coboare la înălţimea <code>4</code>.

== Exemplul 2 ==
input.txt:

999999999999 3

5 1

8 2

1 4

1 7

2 16

Output:

Constraints not met!

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_constraints(n, m):
    return 1 <= n <= 100000 and 1 <= m <= 100000

def main():
    with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
        N = 100005
        h = [0] * N
        k = [0] * N

        n, m = map(int, fin.readline().split())

        if not verify_constraints(n, m):
            print("Constraints not met!")
            return

        for i in range(1, n + 1):
            h[i], k[i] = map(int, fin.readline().split())

        for _ in range(m):
            x, t = map(int, fin.readline().split())

            crt = h[x]
            height = h[x]

            if t <= h[x]:
                fout.write(f"{h[x] - t}\n")
                continue

            t -= h[x]
            height = 0
            crt -= k[x]

            while t and crt:
                if t <= crt:
                    height += t
                    t = 0
                else:
                    t -= crt
                    height = crt

                if not t:
                    break

                if t <= crt:
                    height -= t
                    t = 0
                else:
                    t -= crt
                    height = 0

                crt = max(0, crt - k[x])

            fout.write(f"{height}\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>