Fişierul intrare/ieşire:galerie.in, galerie.outSursăOJI 2016 Clasa a 7-a
AutorCristina SichimAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test0.5 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Galerie (clasa a 7-a)

La întâlnirea anuală a cârtiţelor, la concursul pentru selecţia noilor membri ai consiliului director, a fost propusă următoarea problemă:
De jur-împrejurul unui teren dreptunghiular împărţit în nxm celule de formă pătrată, cu aceeaşi arie, cârtiţele au săpat galerii exterioare. Celulele aflate pe marginea terenului sunt numerorate consecutiv, de la 1 la 2*(n+m), începând din colţul din stânga-sus, ca în imaginea alăturată. În galeriile exterioare, pe marginea terenului, se află t cârtiţe care sunt pregătite să sape galerii interioare. Cârtiţele aflate pe latura de Nord a terenului se vor deplasa către Sud, cele care se află pe latura de la Est se vor deplasa către Vest, cele care se află pe latura de la Sud se vor deplasa către Nord, iar cele care se află pe latura de la Vest se vor deplasa către Est.
Cârtiţele încep să sape în acelaşi timp. În fiecare oră, o cârtiţă sapă într-o singură celulă a terenului.
O cârtiţă se opreşte dacă:

  • ajunge într-o altă galerie interioară; ea nu sapă în aceasta, iar galeria ei se uneşte cu cea în care ajunge;
  • în celula în care sapă, mai sapă şi alte cârtiţe, în aceeaşi oră; galeriile lor se unesc într-o singură galerie şi toate aceste cârtiţe se opresc;
  • ajunge pe marginea terenului, în partea opusă celei din care a plecat, galeria săpată de ea până în acest moment comunicând acum cu galeria exterioară, în care ea nu sapă.

De exemplu, dacă pe marginea unui teren format din 7×5 celule, se află 5 cârtiţe, în celulele 3,8,10,19 şi 23, atunci, după o oră, terenul are configuraţia din fig.1, după două ore, configuraţia din fig.2, după trei ore, configuraţia din fig.3 (ultima cârtiţă ajunge în galeria primei cârtiţe si primele două cârtiţe sapă în aceeaşi celulă şi apoi se opresc), după 4 ore, configuraţia din fig.4, după 5 ore, configuraţia din fig.5, când cele două cârtiţe rămase sapă pe marginea terenului şi apoi se opresc pentru că au ajuns în galeria exterioară ( fig.6 ). Galeriile acestora nu se unesc pentru că niciuna dintre ele nu a intrat în galeria celeilalte şi nici nu s-au întâlnit într-o celulă.

Cerinţe

Cunoscându-se numerele n, m,t şi cele t celule exterioare în care se află cârtiţele, să se determine:

  1. numărul maxim de celule în care sapă o cârtiţă până la oprirea tuturor cârtiţelor;
  2. numărul maxim de celule din care este formată o galerie interioară.

Date de intrare

Fişierul de intrare galerie.in conţine pe prima linie, una dintre valorile 1 sau 2 reprezentând cerinţa 1, dacă se cere determinarea numărului maxim de celule în care sapă o cârtiţă până la oprirea tuturor cârtiţelor, respectiv cerinţa 2, dacă se cere determinarea numărul maxim de celule din care este formată o galerie interioară.
Linia a doua conţine, separate prin câte un spaţiu, trei numere naturale: n şi m (reprezentând dimensiunile terenului) şi t (reprezentând numărul de cârtiţe aflate în galeriile exterioare).
Linia a treia conţine cele t numere naturale separate prin câte un spaţiu, reprezentând poziţiile celor t cârtiţe.

Date de ieşire

Fişierul de ieşire galerie.out conţine pe prima linie o valoarea naturală reprezentând numărul maxim de celule în care sapă o cârtiţă până la oprirea tuturor cârtiţelor, dacă cerinţa a fost 1, respectiv un număr natural reprezentând numărul maxim de celule din care este formată o galerie interioară, dacă cerinţa a fost 2.

Restricţii

  • 3n,m200; 1t2*(n+m);
  • Într-o celulă numerotată, exterioară terenului, se poate afla o singură cârtiţă.
  • Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

Exemplu

galerie.ingalerie.out
1
7 5 5
19 3 8 10 23
5
2
7 5 5
19 3 8 10 23
7

Explicaţie

La cerinta 1, cârtiţa care pleacă din poziţia 23 sapă în două celule; cârtiţele care pleacă din poziţiile 3 şi 8, sapă în 3 celule, iar celelalte două cârtiţe în 5 celule.

La cerinta 2, s-au format trei galerii interioare, două formate din câte 5 celule şi o galerie interioară formată din 7 celule ( fig.6 ).

Trebuie sa te autentifici pentru a trimite solutii. Click aici