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

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


Timp maxim de execuţie / test:
2.5s
Memorie totala disponibilă / stivă:
16MB / 1MB

O firmă produce un tip nou de diamante de formă dreptunghiulară şi de calităţi diferite. Pentru a calcula calitatea unui diamant firma împarte diamantul în N*M pătrăţele formând o matrice cu N linii numerotate de la 1 la N şi M coloane numerotate de la 1 la M. Pătrăţelul de pe linia i şi coloana j poate influenţa calitatea diamantului în felul următor (1≤i≤N, 1≤j≤M):
• dacă pătrăţelul conţine impurităţi este marcat cu -1 şi va diminua calitatea diamantului cu i*j
• dacă pătrăţelul este simplu este marcat cu 0 şi nu schimbă calitatea diamantului
• dacă pătrăţelul conţine aur este marcat cu +1 şi va mări calitatea diamantului cu i*j.
Fiecare pătrăţel va fi marcat cu unul dintre cele trei numere (-1, 0, +1).
Un client bogat vrea să cumpere cât mai multe diamante diferite, de aceeaşi calitate X. Două diamante sunt diferite dacă există cel puţin un pătrăţel de pe o line i şi coloană j marcat diferit în cele două diamante.

Cerinţă

Ajutaţi firma să poată răspunde la astfel de cereri scriind un program care pentru un anumit X găseşte numărul de diamante diferite de calitate X.

Date de intrare

Pe prima linie a fişierului de intrare diamant.in sunt scrise trei numere întregi N M X separate prin câte un spaţiu reprezentând numărul de linii, numărul de coloane ale unui diamant şi respectiv calitatea cerută.

Date de ieşire

Pe prima linie din fişierul de ieşire diamant.out se va afla numărul de diamante diferite cu calitatea cerută, modulo 10000.

Restricţii

0 < N < 21
0 < M < 21
-231 < X < 231

Exemple

diamant.indiamant.outExplicaţii
2 2 7 3 Matricile corespunzătoare celor 3 diamante sunt:

-1 +1 +1 0 +1 +1
+1 +1 +1 +1 0 +1

autor: Dan Ionut Fechete
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2006: borg, matrice1, petrom, ratina, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, sg1, fact, limbaj, panouri, pereti, sant1, zumzi, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
De acelaşi autor: 2sec, croco, judete, tetris2, trafic, monede1, mesaj1, ratina, import, drept1, gard, pitici1, curent
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, ture, 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, 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