Corjuc Eunice: Pagină nouă: 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...

2024-01-04T17:09:03Z

Pagină nouă: 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...

New page

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>

1102 - Bile 2 - Revision history