Editing 2972 - Rufe


Alex vrea să își usuce rufele pe balcon. El a spălat <code>K</code> tricouri și o șosetă. Uscătorul lui Alex are <code>N</code> niveluri, iar fiecare nivel are <code>M</code> locuri unde poate atârna câte un singur obiect de îmbrăcăminte. Alex usucă hainele într-un mod specific: începe prin a pune șoseta pe nivelul <code>A</code>, locul <code>B</code>, iar apoi aduce coșul de rufe cu cele <code>K</code> tricouri și le așază pe rând, mereu alegând o poziție liberă cât mai depărtată de locul unde a pus șoseta. Metrica pe care o găsește ca fiind cea mai potrivită când vine vorba de uscatul rufelor este distanța Manhattan, astfel încât distanța de la nivelul <code>r1</code>, locul <code>c1</code> la nivelul <code>r2</code>, locul <code>c2</code> are valoarea expresiei <code>|r1 – r2| + |c1 - c2|</code>.

= Cerința =
Aflați distanța dintre poziția unde a atârnat ultimul tricou și poziția unde se usucă șoseta.

= Date de intrare =
Pe prima linie a fișierului de intrare <code>rufeIN.txt</code> se vor afla <code>5</code> numere întregi <code>N</code>, <code>M</code>, <code>A</code>, <code>B</code>, și <code>K</code>, cu semnificația din enunț, separate prin câte un spațiu.

= Date de ieșire =
În fișierul de ieșire <code>rufeOUT.txt</code> se va afla o singură linie care să conțină valoarea cerută. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N, M ≤ 1.000.000.000</code>
* <code>1 ≤ A ≤ N</code>
* <code>1 ≤ B ≤ M</code>
* <code>1 ≤ K ≤ N * M – 1</code>
* Pentru teste în valoare de <code>13</code> puncte se garantează că <code>N, M ≤ 1.000</code>.
* Pentru alte teste în valoare de <code>12</code> puncte se garantează că <code>N ≤ 1.000.000</code>.
* Pentru alte teste în valoare de <code>12</code> puncte se garantează că <code>M ≤ 1.000.000</code>.
* Pentru alte teste în valoare de <code>18</code> puncte se garantează că <code>K ≤ 1.000.000</code>.
* Pentru alte teste în valoare de <code>7</code> puncte se garantează că <code>A = B = 1</code>.

= Exemplul 1: =
<code>rufeIN.txt</code>
 5 6 3 3 4
<code>rufeOUT.txt</code>
 4

=== Explicație ===
Uscătorul are <code>5</code> niveluri cu câte <code>6</code> locuri pe nivel. Șoseta se pune pe nivelul <code>3</code>, locul <code>3</code>. Primele <code>2</code> tricouri vor fi atârnate la distanță <code>5</code> în colțurile uscătorului. Următoarele <code>2</code> tricouri pot fi puse numai la distanță <code>4</code>.

= Exemplul 2: =
<code>rufeIN.txt</code>
 3476 53410 438 9217 1000000
<code>rufeOUT.txt</code>
 45818

= Exemplul 2: =
<code>rufeIN.txt</code>
 5 6 3 8 4
<code>rufeOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
def check_constraints(n, m, x, y, k):
    if not (1 <= n <= 1_000_000_000 and 1 <= m <= 1_000_000_000):
        return False
    if not (1 <= x <= n and 1 <= y <= m):
        return False
    if not (1 <= k <= n * m - 1):
        return False
    return True

def unwrap(a):
    return max(a, 0)

def sum_from_to(from_, to, i0):
    if from_ > to:
        return 0
    return (to - from_ + 2 * i0) * (to - from_ + 1) // 2

def count_corner(x, y, d, n, m):
    return (sum_from_to(unwrap(x + d - n), min(d, m - y), unwrap(n - x - d) + 1)
            + unwrap(m - y - d) * (n - x + 1))

def count_greater_equal(x, y, d, n, m, k):
    if d == 0:
        return n * m

    return (count_corner(x, y, d, n, m) + count_corner(n - x + 1, m - y + 1, d, n, m)
            + count_corner(n - x + 1, y, d, n, m) + count_corner(x, m - y + 1, d, n, m)
            - unwrap(x - d) - unwrap(y - d) - unwrap(n - (x + d - 1)) - unwrap(m - (y + d - 1)))

def main():
    with open('rufeIN.txt', 'r') as f:
        n, m, x, y, k = map(int, f.read().strip().split())

    # Check constraints
    if not check_constraints(n, m, x, y, k):
        with open('rufeOUT.txt', 'w') as f:
            f.write("Datele nu corespund restrictiilor impuse\n")
        return

    l, r = -1, n + m - 1
    while r - l > 1:
        p = (l + r) // 2
        if count_greater_equal(x, y, p, n, m, k) < k:
            r = p
        else:
            l = p

    with open('rufeOUT.txt', 'w') as f:
        f.write(f"{l}\n")

if __name__ == '__main__':
    main()

</syntaxhighlight>