Bulbuka a primit de curând cadou un infinit de tromino-uri în formă de L. După ce s-a jucat un timp cu ele, a ajuns la următoarea concluzie: poate să acopere cu tromino-uri o tablă de dimensiuni 2^Kx2^K aproape complet (mai puţin un pătrăţel de dimensiune 1x1). Deşteapta de Bulbuka are un algoritm pentru asta: porneşte de la o configuraţie 2^K-1x2^K-1, o copiază de încă 3 ori, apoi roteşte 2 dintre copii şi la sfârşit, adaugă un tromino la mijloc (v-a făcut un desen mai jos, ca să înţelegeţi mai bine, pentru K = 1, 2 şi 3). Pornind de la o configuraţie de acest tip, ea a observat că poate roti la 90^o câte un tromino, în sensul acelor de ceasornic sau invers, doar dacă după rotire încape înapoi pe tablă. Folosind astfel de rotaţii, pătrăţelul lipsă poate ajunge pe orice poziţie de pe tablă.

Bulbuka vă pune acum Q întrebări de tipul: care este numărul minim de rotaţii necesare pentru ca pătrăţelul lipsă să ajungă de la coordonatele (S_R,S_C) la coordonatele (F_R,F_C)?

Cerința

Pentru o configuraţie 2^Kx2^K, explicată în enunţ, Bulbuka vă pune Q întrebări de tipul: care este numărul minim de rotaţii de 90^o de care avem nevoie pentru a aduce pătrăţelul lipsă din punctul (S_R,S_C) în (F_R,F_C)?

Date de intrare

Fișierul de intrare tromino.in conține pe prima linie două valori K şi Q, unde 2^Kx2^K reprezintă dimensiunea tablei şi Q reprezintă numărul de întrebări pe care le pune Bulbuka. Fiecare din următoarele Q linii din fişier reprezintă o întrebare şi conţine valorile S_R, S_C, F_R, F_C unde (S_R,S_C) reprezintă coordonatele iniţiale ale pătrăţelului lipsă şi (F_R,F_C) reprezintă coordonatele finale la care va ajunge pătrăţelul.

Date de ieșire

Fișierul de ieșire tromino.out va conține Q linii, ce reprezintă răspunsurile la cele Q întrebări.

Restricții și precizări

1 ≤ K ≤ 60; 3 ≤ Q ≤ 5000; 0 ≤ S_R, S_C, F_R, F_C < 2^K
Se garantează că pentru orice poziţie a pătrăţelului lipsă există o configuraţie unică a tablei
Pentru 15% din teste K ≤ 3

Exemplul 1

tromino.in

2 1
1 3 0 0

tromino.out

Explicație

Exemplul 2

tromino.in

tromino.out

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

#include <bits/stdc++.h>

/*
 * Author: Vlad Stoian
 */

using namespace std;
struct point {
    point() { x = 0; y = 0; }
    point(const long long _x, const long long _y) : x(_x), y(_y) {};
    long long x, y;
};

inline long long pow2(const int k) {
    return (1LL << k);
}

int which_quad(const int k, const point p) {
    long long pow2k = pow2(k - 1);
    int quad = 0;

    if(p.x >= pow2k) quad += 2;
    if(p.y >= pow2k) quad += 1;

    return quad;
}

point normalize(const int k, const point p) {
    return point(p.x % pow2(k - 1), p.y % pow2(k - 1));
}

point translate_to_quad_0(const int k, point p) {
    int quad = which_quad(k, p);

    if(quad == 1 || quad == 3) {
        p.y = pow2(k) - 1 - p.y;
    }
    if(quad == 2 || quad == 3) {
        p.x = pow2(k) - 1 - p.x;
    }

    return p;
}

long long distance_to_middle(int k, point p) {
    long long cost_of_translation = 0;
    long long result = pow2(k + 1) - 2;

    while(p.x != 0 || p.y != 0) {
        int quad = which_quad(k, p);

        if(quad == 1 || quad == 2) {
            p = translate_to_quad_0(k, p);
            cost_of_translation++;
        }
        if (quad == 3) {
            p = normalize(k, p);
            cost_of_translation += pow2(k);
        }

        k--;
    }

    return (result - cost_of_translation);
}

bool opposite_quads(const int k, const point p1, const point p2) {
    return ((which_quad(k, p1) ^ which_quad(k, p2)) == 3);
}

bool same_quad(const int k, const point p1, const point p2) {
    return (which_quad(k, p1) == which_quad(k, p2));
}

long long compute(int k, point p1, point p2) {
    while(k > 0 && same_quad(k, p1, p2)) {
        p1 = normalize(k, p1);
        p2 = normalize(k, p2);

        k--;
    }

    // k == 0 means p1 == p2
    if(k == 0) {
        return 0;
    }

    long long result = 1;
    // if opposite quads, then result = 2, else result = 1
    if(opposite_quads(k, p1, p2)) {
        result++;
    }

    p1 = translate_to_quad_0(k, p1);
    p2 = translate_to_quad_0(k, p2);
    k--;

    result += distance_to_middle(k, p1) + distance_to_middle(k, p2);

    return result;
}


int main() {
    ifstream cin("tromino.in");
    ofstream cout("tromino.out");
    int k, q;
    long long r1, r2, c1, c2;

    cin >> k >> q;

    while(q--) {
        cin >> r1 >> c1;
        cin >> r2 >> c2;

        point p1(r1, c1);
        point p2(r2, c2);

        cout << compute(k, p1, p2) << endl;
    }

    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 #1643 Tromino

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