Avem o jucărie formată din NxN pătrate de latură 1 dispuse ca într-o matrice cu N linii și N coloane. Liniile și coloanele matricei sunt numerotate de la 1 la N, iar N este mereu impar. Pătrățelele pot fi albe și le vom codifica 0, sau negre și le codificăm 1. Împărțim matricea în zone concentrice astfel: zona 1 este formată din linia 1, coloana N, linia N și coloana 1; zona 2 este formată din linia a doua, coloana N-1, linia N-1, coloana 2 etc. Sunt [N/2] astfel de zone. În mijlocul matricei este, evident, un singur element, N fiind impar. Asupra oricărei zone putem aplica o operație de rotire, doar spre stânga. Iată în figura de mai jos efectul unei operații de rotire “de lungime” 3, asupra unei zone.

În figurile de mai jos culorile de fundal ale pătrățelelor au doar rolul de a pune în evidență zonele (cu gri închis este zona 1 și cu gri mai deschis zona 2). Dorim să aplicăm asupra jucăriei un set de rotiri așa încât “să rezolvăm jucăria”. Asta înseamnă că toate pătrățelele de pe linia din mijloc și cele de pe coloana din mijloc să devină negre.

Observăm în figura din dreapta că linia 3 și coloana 3 sunt pline de 1. Pentru aceasta, am aplicat o rotire de lungime 2 asupra zonei 1 și o rotire de lungime 0 asupra zonei 2. Codificăm această soluție cu (2,0). Altă soluție este cea codificată prin (2,2).

Cerința

Dată fiind codificarea jucăriei, precum și “lungimea” maximă permisă pentru o rotire în oricare zonă, să se determine numărul de posibilități de a aplica rotiri asupra zonelor așa încât să rezolvăm jucăria. Evident, unei zone i se poate aplica o singură rotire, de lungime cuprinsă între 0 și valoarea maximă permisă.

Date de intrare

Fișierul de intrare cubic.in conține pe prima linie două numere N și P, separate printr-un spațiu, reprezentând dimensiunea jucăriei respectiv lungimea maximă permisă pentru rotirile din oricare zonă. Pe fiecare din următoarele N linii se află câte N numere care pot fi 0 sau 1, neseparate de spații.

Date de ieșire

Fișierul de ieșire cubic.out conține pe prima linie numărul de posibilități de a aplica rotiri asupra zonelor, pentru a rezolva jocul. Două posibilități se consideră distincte dacă diferă prin lungimea rotirii din cel puțin o zonă. Pentru că acest număr poate fi foarte mare, se va afișa restul împărțirii lui la 9901.

Restricții și precizări

3 ≤ N ≤ 999, N este impar
0 ≤ P ≤ 100 000

Exemplu

cubic.in

cubic.out

Explicație

Soluțiile sunt (2,0), (3,0), (2,2), (3,2).

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

/*
    prof. Marius Nicoli
    Complexitate O(n x n)
*/
#include <fstream>

#define DIM 1002
#define MOD 9901

using namespace std;

char a[DIM][DIM];
char c;

int v[DIM * 6];
int n, p, i, j, sc, sp, sr, start, d, sol, per, k, pas, rest;

int main () {
    ifstream fin ("cubic.in");
    ofstream fout("cubic.out");

    fin>>n>>p;
    p++;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            fin>>a[i][j];

    c = a[n/2+1][n/2+1];
    if (c == '0') {
        fout<<"0\n";
        return 0;
    }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (a[i][j] == c)
                a[i][j] = 1;
            else
                a[i][j] = 0;

    sol = 1;
    for (d=1, per = n-1, start = n/2+1;d<=n/2;d++, per-=2, start--) {
        k = 0;
        for (i=d;i<=n-d+1;i++)
            v[++k] = a[d][i];
        for (i=d+1;i<=n-d+1;i++)
            v[++k] = a[i][n-d+1];
        for (i=n-d; i>=d; i--)
            v[++k] = a[n-d+1][i];
        for (i=n-d; i>d; i--)
            v[++k] = a[i][d];

        for (i=1;i<=2*per;i++) {
            v[++k] = v[i];
        }
        rest = p%per;
        sp = sr = 0;
        for (i=start, pas = 1;i<start + per;i++, pas++)
            if (v[i] == v[i+per] && v[i] == v[i+2*per] && v[i] == v[i+3*per] && v[i] == 1) {
                sp++;
                if (pas <= rest)
                    sr++;
            }
        sc = p/per * sp + sr;
        sc %= MOD;

        sol = sol * sc % MOD;
    }

    fout<<sol<<"\n";

    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 #2049 cubic

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