1102 - Bile 2

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

În momentul în care bila i atinge masa, tendinţa ei va fi să se ridice în aer până la înălţimea h - k, 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 k 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 h şi k pentru fiecare dintre cele n bile, să se răspundă la m întrebări de forma: La ce înălţime faţă de masă se va afla bila x în momentul t ?

Date de intrare

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

Date de ieşire

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

Restricţii

• 1 ≤ n, m ≤ 100.000

Exemplul 1

input.txt:

2 3

5 1

8 2

1 4

1 7

2 16

output.txt:

1

2

4

Explicație:

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

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

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

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>