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

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


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

La un concurs de dans sunt invitati N barbati si N femei. Atât femeile, cât si barbatii sunt numerotati de la 1 la N. Organizatorii doresc ca toti cei 2*N invitati sa danseze cu o persoana preferata si solicita din partea fiecarui invitat lista preferintelor sale. Aceasta lista cuprinde numerele de ordine ale tuturor persoanelor de sex opus, ordonata descrescator în functie de preferinte.
Inainte de inceperea concursului, organizatorii trebuie sa prezinte lista celor N perechi (barbat, femeie) desemnate pentru dans. Spunem ca o pereche arbitrara (b, f) din lista este stabila, daca respecta conditia: orice femeie f' aflata înaintea lui f  în lista preferintelor lui b si cuplata cu b' în lista, îl prefera pe b' lui b. Întreaga lista este stabila daca toate cele N perechi sunt stabile.

Cerinta

Cunoscând numarul N si listele de preferinte întocmite de cele 2*N persoane, sa se determine (daca este posibil) o lista stabila.

Date de intrare

Pe prima linie a fisierului spair.in este scris numarul natural N. Pe urmatoarele N linii se afla listele de preferinte ale barbatilor sub forma unor permutari ale multimii {1, 2, ..., N }; numerele de pe linia i+1 reprezinta lista preferintelor barbatului i în ordinea descrescatoare a preferintelor acestuia. Pe urmatoarele N linii sunt scrise preferintele femeilor în acelasi format. Numerele scrise pe o linie sunt despartite prin cate un singur spatiu.

Date de iesire

Rezultatele se vor scrie în fisierul spair.out pe N linii. O linie va contine o pereche de numere naturale din multimea {1, 2, ..., N } reprezentând un element din lista stabila determinata. Primul numar al fiecarei perechi este numarul de ordine al barbatului, iar cel de al doilea este al partenerei sale de dans. Daca nu exista solutie, pe prima linie în fisier se va scrie mesajul impossible  

Restrictii

0 < n <= 1000
În cazul în care exista mai multe solutii, în fisier se va scrie una singura.

Exemplu

spair.in

spair.out

Explicatie

3
3 1 2
2 3 1
2 3 1
2 3 1
1 3 2
1 2 3

1 3
2 1
3 2

Lista
1 3
2 1
3 2

este stabila.
Daca am considera lista cu perechi:
1 2
2 1
3 3
Lista nu este stabila, deoarece perechea (1 2) nu este stabila. Într-adevar, barbatul 1 prefera femeia 3 în fata partenerei sale (2), iar femeia 3 îl prefera pe barbatul 1 înaintea partenerului ei (3).

prof. Dana Lica
C. N. "I. L. Caragiale" Ploiesti
danal182001@yahoo.com

 

 

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2006: scara, programs, nr, iepuras2, numere3, robot2, fry, suma, sah, formule, perm, cifra, repeat, ture, 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, caravane, cuburi, grup, invest, cd, friends2, mese, toys
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, 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 vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor