Ultimele mesaje ale lui: Kelemen Stelian

aici sunt problemele de 11 - 12 have FUN

Problema 1 – Domino

   Se consideră n dominouri, din care se pot construi şiruri respectând următoarele reguli:
Prima piesă de domino face parte în mod obligatoriu din şir.
Următoarele piese se iau în considerare în ordinea în care sunt date (se decide pentru fiecare dacă se va pune în şir sau nu).
Fiecare piesă se pune la un capăt al şirului deja format în poziţia în care a fost dată sau învârtită cu 180°, sau se pune la o parte şi nu se mai revine la ea.
O piesă poate fi pusă la un capăt al şirului, dacă numărul de pe dominoul din capăt (mai precis de pe jumătatea nealipită de şirul construit deja) şi numărul de pe dominoul care se alipeşte şirului la pasul curent (partea care se alipeşte) sunt egale.
Exemplu

Cerinţă
   Să se determine cel mai lung şir de dominouri care se poate construi din dominourile date.

Date de intrare
   Pe prima linie a fişierului DOMINO.IN se află un număr natural n, reprezentând numărul de dominouri. Pe fiecare din următoarele n linii se află două numere x şi y, care reprezintă numerele de pe piesa de domino respectivă.

Date de ieşire
   În fişierul DOMINO.OUT se va scrie un singur număr natural, reprezentând lungimea celui mai lung şir de piese care se poate construi respectând regulile de mai sus.

Restricţii şi precizări
1 <= n <= 100000;
0 <= x, y <= 9;
piesele pot fi rotite înainte să fie aşezate la un capăt al şirului.

Exemplu

DOMINO.IN
6
1 2
1 6
2 3
1 4
2 3
4 3

DOMINO.OUT
5

Timp maxim de executare/test: 1 secundă

si pb 2

Problema 2 – Luna

   În anul 2507 colonizarea Lunii a luat sfârşit, fiecare ţară deţine câteva parcele din teritoriul planetei. Firmele de pe Pământ doresc construirea unor clădiri de formă dreptunghiulară pe Lună. Evident, fiecare firmă va putea construi doar pe teritoriul care se află în proprietatea ţării ei de provenienţă.

Cerinţă
   Stabiliţi în cazul fiecărei firme, dacă este posibilă satisfacerea cererii ei de construire!

Date de intrare
Pe prima linie a fişierului LUNA.IN se află două numere naturale n şi m, care reprezintă numărul de linii, respectiv numărul de coloane a matricei care descrie harta Lunii.
Pe fiecare dintre următoarele n linii se află m numere care indică numărul de ordine al ţării care este proprietara parcelei de pe linia şi coloana respectivă de pe hartă.
Pe următoarea linie se află numărul k al firmelor de pe Pământ, care doresc să construiască pe Lună.
Pe următoarele k linii sunt scrise câte trei numere, reprezentând cererile firmelor. Primul număr reprezintă ţara de provenienţă a firmei. Al doilea şi al treilea număr reprezintă dimensiunile clădirii pe care firma ar dori s-o construiască conform cererii respective.

Date de ieşire
   Fişierul de ieşire LUNA.OUT va conţine exact k linii.
Dacă a i-a cerere poate fi satisfăcută, pe a i-a linie se va scrie mesajul:
    'Cererea poate fi satisfacuta!'.
Dacă ţara de provenienţă al firmei nu are parcele pe Lună, în fişierul de ieşire se va scrie mesajul:
'Tara de provenienta nu are parcele pe Luna!'.
Dacă nu se poate construi o clădire cu dimensiunile date folosind doar parcelele ţării de provenienţă, în fişierul de ieşire se va scrie mesajul: 'Cererea nu poate fi satisfacuta!'.

Restricţii şi precizări
1 ≤ n, m ≤ 50;
numărul de ordine a unei ţări este un număr natural cuprins între 1 şi 2500 (nu uitaţi, suntem în anul 2507, s-au mai format nişte ţări...);
1 ≤ k ≤ 100 000;
numărul de ordine a ţării de provenienţă a unei firme este un număr natural cuprins între 1 şi 5000;
dimensiunile unei clădiri sunt numere naturale cuprinse între 1 şi 100.
Exemplu

LUNA.IN
5 10
1 1 1 2 2 2 2 3 3 4
1 1 1 2 2 2 2 3 3 4
5 5 5 2 2 2 2 7 7 4
5 5 5 6 6 6 6 7 7 4
5 5 5 6 6 6 6 7 7 4
6
1 2 3
2 3 4
3 2 3
1 3 2
7 20 20
8 4 4

LUNA.OUT
Cererea poate fi satisfacuta!
Cererea poate fi satisfacuta!
Cererea nu poate fi satisfacuta!
Cererea poate fi satisfacuta!
Cererea nu poate fi satisfacuta
Tara de provenienta nu are parcele pe Luna!


Timp maxim de executare/test: 1 secundă

nu a fost usor deloc, believe ME

infoarena informatica de performanta