Ex9 Sebi

#include <stdio.h>
#include <stdlib.h>

unsigned ZigZag(unsigned n, unsigned i, unsigned j, unsigned pivot, unsigned lung) {
    if (lung) { // daca lungimea matricei este ce-l putin 1x1
        n = n - ((2 * (i > lung) + (j > lung) ) * pivot); // ne punem mereu pe primul element din cadran
        // n se pastreaza ca primul element din cadran si pivot ca si numar de lemente din cadran
        if (i > lung ) i -= lung; // i isi va schimba pozitia in funtie al catelea este in cadran
        if (j > lung ) j -= lung; // j la fel ca i

        return ZigZag(n, i, j, pivot/ 4, lung /2); // apelam recursiv functia pentru pivot/4 si lung/2 asta pentru a
    }                                             // ne pune pe un cadran mai mic pana ajungem sa nu mai avem nici unu
    return n; // afisam n obtinut
}

int main() {
    unsigned n, i, j , q, pivot, lung; // variabile auxiliare
    FILE *f, *g; // 2 variabile de tip fiser
    f = fopen("in.txt", "r"); // deschidem in mod citire
    g = fopen("out.txt", "w"); // deschidem in mod scriere
    fscanf(f, "%u%u", &n, &q); // citim n respectiv numarul de perechi de i si j
    pivot = 1 << 2 * (n - 1); // salvam pivotul care este mereu numarul de elemtne din matirce /4 ca sa facem cele 4 cadrane
    lung = 1 << (n - 1); // lungimea matricei ne este necesara mereu / 2
    n = 1 << 2 * n; // salvam valoarea maxima
    while (q) {
        fscanf(f, "%u%u", &i, &j); // citim perehea i si j
        fprintf(g, "%u\n", ZigZag(n , i, j , pivot, lung)); // apelam functia necesara complexitate O(n *q)
        q--; // scadem numarul de perechi care trebuie citite
    }
    fclose(f); //inchidem fiserul
    fclose(g); //inchidem fiserul
    return 0;
}