Se dau N puncte în spațiul 3D prin coordonatele lor. Dorim să amplasăm două cuburi cu laturile paralele cu axele de coordonate, astfel încât fiecare punct să se afle pe una dintre feţele sau în interiorul a cel puțin unuia dintre cuburi. În plus, latura cubului de latură maximă dintre cele două trebuie să fie minimă.

Cerința

Scrieţi un program care să determine latura cubului de latură maximă pentru două cuburi care realizează acoperirea mulțimii de puncte în condiţiile de mai sus.

Date de intrare

Pe prima linie a fişierului cuburi.in se află 10 numere naturale N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz. Coordonatele celor N puncte se generează după următoarele reguli:

X1 = 1, Xi = (Xi-1 * Ax + Bx * i) mod Cx, pentru i = 2...n
Y1 = 1, Yi = (Yi-1 * Ay + By * i) mod Cy, pentru i = 2...n
Z1 = 1, Zi = (Zi-1 * Az + Bz * i) mod Cz, pentru i = 2...n

Al i-lea punct are coordonatele (Xi, Yi, Zi).

Date de ieșire

Fişierul de ieşire cuburi.out va conţine un singur număr natural reprezentând latura cubului de latură maximă.

Restricții și precizări

1 ≤ N ≤ 2*1.000.000
1 ≤ Ax, Ay, Az ≤ 1000
1 ≤ Bx, By, Bz ≤ 1010
2 ≤ Cx, Cy, Cz ≤ 1015
Un punct aflat pe o față a cubului (inclusiv pe o muchie sau într-un colț al cubului) se consideră în interiorul cubului
Pentru un număr de teste în valoare de 30 de puncte N ≤ 100 și Cx, Cy, Cz ≤ 20
Pentru un număr de teste în valoare de 70 de puncte N ≤ 10.000

Exemplu

cuburi.in

6 2 3 10 3 1 9 5 7 8

cuburi.out

Explicație

Cele 6 puncte au următoarele coordonate: (1,1,1), (8,5,3), (5,0,4), (2,4,0), (9,8,3), (6,3,1). O soluție posibilă este să amplasăm primul cub astfel încât două dintre colțurile opuse să aibă coordonatele (0, 0, 0) respectiv (5,5,5) iar al doilea cub să aibă două colțuri opuse la coordonatele (6,3,1), respectiv (11,8,6).

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 Cuburi:

// O(N) - 100 puncte
// Autor: Tudose Vlad Andrei

#include <cstdio>
#include <algorithm>
#include <cassert>
#define NMAX 2000005
#define ll long long
using namespace std;

int n;
ll X[NMAX], Y[NMAX], Z[NMAX], xmin, xmax, ymin, ymax, zmin, zmax;

ll dist(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2) {
    ll dx = abs(x1 - x2);
    ll dy = abs(y1 - y2);
    ll dz = abs(z1 - z2);
    return max(dx, max(dy, dz));
}

ll solve(ll y1, ll z1) {
    ll x1 = xmin, x2 = xmax, y2 = ymin + ymax - y1, z2 = zmin + zmax - z1;
    
    ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        ll d1 = dist(X[i], Y[i], Z[i], x1, y1, z1);
        ll d2 = dist(X[i], Y[i], Z[i], x2, y2, z2);
        ans = max(ans, min(d1, d2));
    }
    return ans;
}

int main() {
    freopen("cuburi.in", "r", stdin);
    freopen("cuburi.out", "w", stdout);
    
    ll ax, bx, cx, ay, by, cy, az, bz, cz;
    scanf("%d%lld%lld%lld%lld%lld%lld%lld%lld%lld", &n, &ax, &bx, &cx, &ay, &by, &cy, &az, &bz, &cz);
    assert(1 <= n && n <= 2000000);
    assert(1 <= ax && ax <= 1000);
    assert(1 <= ay && ay <= 1000);
    assert(1 <= az && az <= 1000);
    assert(1 <= bx && bx <= 10000000000ll);
    assert(1 <= by && by <= 10000000000ll);
    assert(1 <= bz && bz <= 10000000000ll);
    assert(2 <= cx && cx <= 1000000000000000ll);
    assert(2 <= cy && cy <= 1000000000000000ll);
    assert(2 <= cz && cz <= 1000000000000000ll);
    
    X[1] = Y[1] = Z[1] = xmin = xmax = ymin = ymax = zmin = zmax = 1;
    for(int i = 2; i <= n; ++i) {
        X[i] = (X[i - 1] * ax + bx * i) % cx;
        Y[i] = (Y[i - 1] * ay + by * i) % cy;
        Z[i] = (Z[i - 1] * az + bz * i) % cz;
        xmin = min(xmin, X[i]);
        xmax = max(xmax, X[i]);
        ymin = min(ymin, Y[i]);
        ymax = max(ymax, Y[i]);
        zmin = min(zmin, Z[i]);
        zmax = max(zmax, Z[i]);
    }
    
    ll s1 = solve(ymin, zmin);
    ll s2 = solve(ymin, zmax);
    ll s3 = solve(ymax, zmin);
    ll s4 = solve(ymax, zmax);
    
    printf("%lld
", min(min(s1, s2), min(s3, s4)));
    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 #613 Cuburi

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #613 Cuburi 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!

Rezolvare completă PbInfo #613 Cuburi