Editing 2455 - Plaja 2

Zizi îşi va petrece concediul în această vară într-o frumoasă staţiune de la Marea Neagră. Acolo va sta <code>N</code> zile. Zilele

sunt numerotate de la <code>1</code> la <code>N</code>. În fiecare dintre cele <code>N</code> zile de concediu, ea intenţionează să facă plajă un număr cât

mai mare de unităţi de timp. Va trebui să ţină seama totuşi de prognoza meteo, care este nefavorabilă în <code>K</code> dintre cele <code>N</code> zile, respectiv în zilele <code>z[1]</code>, <code>z[2]</code>, …, <code>z[k]</code>. În fiecare dintre aceste <code>K</code> zile va ploua sau va fi prea mult soare, iar Zizi va trebui să-şi limiteze timpii de plajă la cel mult <code>t[1]</code>, <code>t[2]</code>, …, <code>t[k]</code> unităţi de timp. De asemenea, din motive de confort fizic, Zizi doreşte ca diferenţa în valoare absolută a timpilor de plajă între oricare două zile consecutive să nu depăşească <code>T</code>.

= Cerința =
Cunoscând zilele <code>z[1]</code>, <code>z[2]</code>, …, <code>z[k]</code> în care există limitările <code>t[1]</code>, <code>t[2]</code>, …, <code>t[k]</code> pentru timpul de plajă şi valoarea <code>T</code>, să se determine numărul maxim de unităţi de timp pe care Zizi le poate petrece la plajă într-o singură zi dintre cele <code>N</code> zile de concediu.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie trei numere naturale <code>N</code>, <code>K</code> şi <code>T</code> separate printr-un spaţiu, reprezentând numărul de zile de concediu, numărul de zile în care există limitări pentru timpul de plajă şi diferenţa maximă

admisă a timpilor de plajă pentru oricare două zile consecutive. Pe fiecare dintre următoarele <code>K</code> linii se află câte două numere <code>z</code> şi <code>t</code>, despărțite printr-un spațiu, reprezentând numărul de ordine al unei zile cu limitări pentru timpul de plajă, respectiv limita de timp pentru ziua respectivă. Valorile <code>z[1]</code>, <code>z[2]</code>, …, <code>z[k]</code> sunt în ordine strict crescătoare.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie un singur număr natural <code>tmax</code>, reprezentând numărul maxim de

unităţi de timp pe care Zizi le poate petrece făcând plajă într-una din cele <code>N</code> zile de concediu.

= Restricții și precizări =

* <code>1 ≤ N ≤ 1 000 000 000</code>
* <code>1 ≤ K ≤ 100 000</code>

== Exemplul 1 ==
input.txt:

3 1 3

1 2

output.txt:

8

Explicație:

În prima zi timpul de plajă este limitat la <code>2</code> unități de timp. În ziua a doua timpul maxim de plajă este <code>2 + 3</code>, iar în ziua a treia, timpul maxim este <code>2 + 3 + 3 = 8</code> unități de timp.

== Exemplul 2 ==
input.txt:

5 2 11

2 2

4 5

output.txt:

16

Explicație:

În ziua <code>2</code> timpul de plajă este limitat la <code>2</code> unități de timp, iar în zilele <code>1</code> și <code>3</code> nu există limitare. Atunci timpul maxim de plajă pentru zilele <code>1</code> sau <code>3</code> este <code>2 + 11 = 13</code>. În ziua <code>4</code> timpul de plajă este limitat la <code>5</code> unități de timp, iar în ziua <code>5</code> nu există limitare. Deci în ziua <code>5</code> timpul maxim de plajă este <code>5 + 11 = 16</code>.

== Exemplul 3 ==
input.txt:

99999999999999999999 2 11

2 2

4 5

Output:

Error: N is not within the valid range (1 <= N <= 1,000,000,000)

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
# prof. Constantin Galatan
# solutie O(K * log T)

import sys

def verify_constraints(N, K):
    if not (1 <= N <= 1000000000):
        sys.exit("Error: N is not within the valid range (1 <= N <= 1,000,000,000)")
    
    if not (1 <= K <= 100000):
        sys.exit("Error: K is not within the valid range (1 <= K <= 100,000)")

def try_time(t0, i):
    return d[i + 1] - d[i] >= (t0 - t[i] + T - 1) // T + (t0 - t[i + 1] + T - 1) // T

input_file = open("input.txt", "r")
output_file = open("output.txt", "w")

N, K, T = map(int, input_file.readline().split())
verify_constraints(N, K)

d = [0] * (K + 1)
t = [0] * (K + 1)

for i in range(1, K + 1):
    d[i], t[i] = map(int, input_file.readline().split())

for i in range(1, K):
    t[i + 1] = min(t[i + 1], t[i] + (d[i + 1] - d[i]) * T)

for i in range(K - 1, 0, -1):
    t[i] = min(t[i], t[i + 1] + (d[i + 1] - d[i]) * T)

res = 0
for i in range(1, K):
    l, r = max(t[i], t[i + 1]), 1 * N * T
    tmp = 0
    while l <= r:
        m = (l + r) // 2
        if try_time(m, i):
            l = m + 1
            tmp = m
        else:
            r = m - 1
    res = max(res, tmp)

res = max(res, max(t[K] + (N - d[K]) * T, t[1] + (d[1] - 1) * T))
output_file.write(str(res))

input_file.close()
output_file.close()

</syntaxhighlight>