Rezolvare completă PbInfo #3321 Stone

Peste 3700 de ani lumea a devenit dreptunghiulară, este formată n x m zone și este stăpânită de un rege care are o armată formată din q soldați. În regat se află k turnuri de piatră, ostile armatei regelui, la coordonate cunoscute; fiecare turn atacă zonele de pe linia și coloana sa.

Cerința

Regele dorește să afle în câte moduri poate plasa soldații în zonele fără turnuri ale regatului astfel încât aceștia să nu fie atacați de turnuri.

Date de intrare

Programul citește de la tastatură dimensiunile n și m ale regatului, numărul de turnuri k și numărul de soldați q. Pe următoarele k linii se află câte două valori, reprezentând coordonatele turnurilor.

Date de ieșire

Programul va afișa pe ecran numărul p, reprezentând numărul de moduri în care pot fi plasați soldații regelui.

Restricții și precizări

  • 1 ≤ n , m ≤ 4
  • 1 ≤ q , k ≤ n*m
  • în cazul în care nu există niciun mod de plasare a soldaților se va afișa 0
  • soldații sunt diferiți între ei; două moduri de plasare a soldaților pot să folosească aceleași zone, dar să fie diferite prin ordinea în care sunt plasați soldații în aceste zone.

Exemplu 1:

Intrare

3 3 1 1
2 2

Ieșire

4

Explicație

Zonele neatacate de turnuri au coordonatele (1,1), (1,3), (3,1), (3,3).

Exemplu 2:

Intrare

4 4 1 9
1 1

Ieșire

362880

Precizare

Acesta este cel mai mare test.

Exemplu 3:

Intrare

3 3 3 4
1 1
2 2
3 3

Ieșire

0

Explicație

Nu au rămas destule zone neatacate de turnuri.

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

#include <iostream>

using namespace std;

int n,m,q,k,x,y,fx[6],fy[6];

int main()
{
    cin>>n>>m>>k>>q;
    while(k--){
        cin>>x>>y;
        if(fx[x]!=1){fx[0]++;}
        fx[x]=1;
        if(fy[y]!=1){fy[0]++;}
        fy[y]=1;
    }
    ///Numarul de casute neatacate
    int s=n*m-m*fx[0]-n*fy[0]+fx[0]*fy[0];
    ///Imposibil
    if(s<q){
        cout<<"0";
    }
    else {
        ///Aranjamente fara repetitie de s luate cate q
        int p=1;
        for(int i=s-q+1;i<=s;i++){p*=i;}
        cout<<p;
    }
}

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 #3321 Stone

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