.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » ture

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
ture


Timp maxim de executie/test:
0.3 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Gigel are o tabla de sah cu N linii si M coloane. El vrea sa aseze pe tabla K ture astfel incat acestea sa nu se atace intre ele (consideram ca doua ture se ataca daca ele se afla pe aceeasi linie sau pe aceeasi coloana). Pentru a face lucrurile mai interesante, Gigel a marcat anumite casute in care nu poate aseza nici o tura si acum vrea sa stie in cate moduri poate aseza turele.

Cerinta

Ajutati-l pe Gigel sa gaseasca numarul de posibilitati in care se pot aseza cele K ture.

Date de intrare

Pe prima linie a fisierului de intrare ture.in sunt scrise trei numere naturale N, M si K separate prin cate un spatiu. Pe cea de-a doua linie se afla P numarul de casute marcate de Gigel. Urmeaza apoi P linii cu cate doua numere x, y cu semnificatia ca Gigel a marcat casuta de pe linia x si coloana y.

Date de iesire

Fisierul de iesire ture.out va contine o singura linie pe care va fi scris numarul de posibilitati de amplasare a turelor pe tabla de sah.

Restrictii

  • 0 <= N*M <= 250
  • 0 <= K <= 100
  • 0 <= P <= N*M

Exemplu

ture.in ture.out
3 3 3
1
2 2
4

Diaconu Adrian Paul
Universitatea Bucuresti, Facultatea de Matematica si Informatica

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2006: scara, programs, nr, iepuras2, numere3, robot2, fry, suma, sah, formule, perm, cifra, repeat, xor, policefm, unu, criptare, ed, bilete, vector, scor, ratb, infinit, race, dragon, kreg, placi, hanoig, red, 2sec, flood, sume3, balls, festival, croco, johnie, matrice3, pavaj, sume, arthur, kimberley, kafka, vocale, pento, prop, ro, sol, bacan, erdos, poligon, reduceri, druid, novel, gramezi, nrbinar, laser, spair, caravane, cuburi, grup, invest, cd, friends2, mese, toys
De acelaşi autor: nrbun2, nrbun, siruri, perspic, toys, secv, arb, sir1, mexc, pviz
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor