Rezolvare completă PbInfo #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 rufe.in 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 rufe.out se va afla o singură linie care să conțină valoarea cerută.

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:

rufe.in

5 6 3 3 4

rufe.out

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:

rufe.in

3476 53410 438 9217 1000000

rufe.out

45818

Exemplul 3:

rufe.in

1000000000 1000000000 1 1 7

rufe.out

1999999995

Exemplul 4:

rufe.in

654321 123456 5454 1212 10000000000

rufe.out

628395

Explicație

În acest caz Alex usucă 1010 tricouri. Acordați atenție citirii unei astfel de valori din fișier.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema rufe:

// autor Ciobanu Bogdan
#include <stdio.h>
#include <algorithm>
#include <memory>
using namespace std;

long long n, m, x, y, k;

long long unwrap(long long a) {
    return a > 0LL ? a : 0LL;    
}

long long sum(long long from, long long to, long long i0) {
    if (from > to) return 0LL;
    return (to - from + 2 * i0) * (to - from + 1) / 2;
}

long long count_corner(long long x, long long y, long long d) {
    return sum(unwrap(x + d - n), min(d, m - y), unwrap(n - x - d) + 1)
         + unwrap(m - y - d) * (n - x + 1);
}

long long count_greater_equal(long long d) {
    if (d == 0) return n * m;
    
    return count_corner(x, y, d) + count_corner(n - x + 1, m - y + 1, d)
         + count_corner(n - x + 1, y, d) + count_corner(x, m - y + 1, d)
         - unwrap(x - d) - unwrap(y - d) - unwrap(n - (x + d - 1)) - unwrap(m - (y + d - 1));
}

int main() {
    unique_ptr<FILE, decltype(&fclose)> f(fopen("rufe.in", "r"), &fclose);
    fscanf(f.get(), "%lld%lld%lld%lld%lld", &n, &m, &x, &y, &k);
    
    long long l = -1, r = n + m - 1;
    while (r - l > 1LL) {
        long long p = (l + r) / 2;
        ((count_greater_equal(p) < k) ? r : l) = p;
    }
    
    f.reset(fopen("rufe.out", "w"));
    fprintf(f.get(), "%lld\n", l);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2972 rufe

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2972 rufe de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!