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

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


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

La firma la care lucrează Gigel există M tipuri de camioane, din fiecare tip existând N exemplare. Gigel aşează camioanele firmei pe N rânduri, aşezând pe fiecare coloană numai camioane de acelaşi tip. Se formează astfel o matrice în care liniile sunt numerotate de sus în jos de la 1 la N, iar coloanele sunt numerotate de la stânga la dreapta de la 1 la M.
În fiecare noapte vine o bandă de hoţi. Şeful bandei anunţă: “în noaptea aceasta vom fura toate camioanele care se află în zona dreptunghiulară având colţul stânga-sus pe linia x1 şi coloana y1, iar colţul opus pe linia x2 şi coloana y2.
În dimineaţa următoare, Gigel vede acest lucru, şi „acoperă” furtul: pe fiecare linie în care există spaţii libere deplasează spre stânga toate camioanele care se află în dreapta locului liber rămas.
De exemplu, pentru N=3 şi M=5 iniţial avem următoarea amplasare:
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

În prima noapte hoţii fură camioane, din dreptunghiul cu colţul stânga-sus în linia 2,coloana 2 şi colţul dreapta-jos linia 3 coloana 3. Astfel, în ziua următoare, după ce Gigel deplasează camioanele, amplasarea este următoarea:
1 2 3 4 5
1 4 5
1 4 5

Dacă în a doua noapte hoţii fură din nou din dreptunghiul cu colţul stânga-sus în linia 1, coloana 1 şi colţul dreapta-jos în linia 3, coloana 2, după deplasările făcute ziua de Gigel, amplasarea este următoarea:
3 4 5
5
5

Cerinţă

Cunoscând câte tipuri de camioane există la firmă iniţial, pe câte randuri au fost aşezate, numărul K de zile în care au loc furturi şi coordonatele dreptunghiurilor din care fură hoţii în fiecare noapte, determinaţi ce tipuri de camioane se află pe o anumită coloană din amplasarea finală.

Date de intrare

Fişierul de intrare camion.in conţine pe prima linie 4 numere naturale: N M K C, reprezentând numărul de rânduri pe care au fost aşezate camioanele, numărul de coloane, numărul de nopţi în care vor fura hoţii camioane, respectiv numărul coloanei pentru care se doreşte să se afle ce tipuri de camioane conţine la final. Pe fiecare dintre următoarele K linii se vor afla câte 4 numere naturale. Pe linia i+1 se află x1 y1 x2 y2, (x1,y1) reprezentând linia şi coloana colţului stânga-sus, iar (x2,y2) linia şi coloana colţului dreapta-jos al dreptunghiului din care fură hoţii în noaptea i. Numerele situate pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire camion.out va conţine N linii, pe fiecare câte un număr întreg. Numărul de pe linia i va reprezenta tipul camionului de pe linia i şi coloana C, după K zile. În caz că pe linia i nu se găseşte nici un camion, se va afişa valoarea 0 pe linia respectivă.

Restricţii

1 <= N <= 600
1 <= C <= M <= 600
0 <= K <= 30000

Nu este obligatoriu ca dreptunghiul din care se va efectua un furt să conţină camioane în fiecare loc.

Exemple

camion.incamion.out
3 5 3 1 2 2 3 3 1 1 3 2 1 2 3 4 3 5 5

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2005: barca1, ivv, peste, kalah, algola
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor