2972 - Rufe

Alex vrea să își usuce rufele pe balcon. El a spălat K tricouri și o șosetă. Uscătorul lui Alex are N niveluri, iar fiecare nivel are M 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 A, locul B, iar apoi aduce coșul de rufe cu cele K 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 r1, locul c1 la nivelul r2, locul c2 are valoarea expresiei |r1 – r2| + |c1 - c2|.

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 rufeIN.txt se vor afla 5 numere întregi N, M, A, B, și K, cu semnificația din enunț, separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire rufeOUT.txt 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

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

Exemplul 1:

rufeIN.txt

5 6 3 3 4

rufeOUT.txt

4

Explicație

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

Exemplul 2:

rufeIN.txt

3476 53410 438 9217 1000000

rufeOUT.txt

45818

Exemplul 2:

rufeIN.txt

5 6 3 8 4

rufeOUT.txt

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>