Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | spider.in, spider.out | Sursă | ONI 2004 clasa a 6-a |
|---|---|---|---|
| Autor | autor necunoscut | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 2048 KB |
| Scorul tău | N/A | Dificultate |
   1.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Spider (clasa a 6-a)
Spider este un păianjen care trăiește în casa unui programator. De la acesta Spider a preluat pasiunea pentru numere și pentru programe. Așa stând lucrurile, Spider a hotărât să nu-și mai țeasă pânza în mod tradițional, ci să folosească informațiile aflate de la programator, abordând și un stil de lucru metodic. Prin urmare, Spider procedează astfel:
- alege n puncte așezate în cerc și le numerotează de la 1 la n (în sensul acelor de ceasornic);
- calculează distanțele dintre oricare două puncte obținând doar numere naturale distincte;
- alege un punct de plecare k;
- stabilește următoarea regulă pe care să o respecte când țese pânza: în fiecare zi va țese câte un fir: dacă numărul zilei este impar, atunci țese firul de la punctul în care se află la punctul următor (de asemenea în sensul acelor de ceasornic, iar după punctul numerotat cu n urmează punctul numerotat cu 1), iar dacă numărul zilei este par Spider țese un fir între punctul în care se află și punctul în care ajunge sărind un punct;
- se oprește atunci când ar trebui să țeasă un fir între două puncte între care există deja un fir țesut.
Cerință
1. numărul de zile necesar pentru a-și țese pânza și punctul în care s-a oprit;
2. lungimile firelor țesute împreună cu capetele lor, în ordinea descrescătoare a lungimilor firelor. Capetele firelor vor fi afișate în ordine crescătoare.
Date de intrare
Din fișierul de intrare spider.in se citesc în această ordine:
| Date intrare | Ce reprezintă |
|---|---|
| n k d11 d12 ... d1n d21 d22 ... d2n ....... dn1 dn2 ... dnn |
reprezentând numărul de puncte alese reprezentînd punctul de plecare reprezentând distanțele dintre puncte. Un element aflat pe linia i și coloana j reprezintă distanța găsită de Spider între punctele numerotate cu i, respectiv j |
Date de ieșire
În fișierul de ieșire spider.out se vor scrie datele astfel:
| Date ieșire | Ce reprezintă |
|---|---|
| p x l1 c11 c12 l2 c21 c22 ....... lp cp1 cp2 |
numărul de zile și punctul în care s-a oprit Spider lungimile firelor și capetele lor, în ordinea descrescătoare a lungimilor firelor. Capetele firelor vor fi afișate în ordine crescătoare. |
Restricții
- 1 ≤ n ≤ 100
- 1 ≤ k ≤ n
- 0 ≤ dij ≤ 50000, pentru i,j = 1,n
Exemplu
| spider.in | spider.out | Explicații |
|---|---|---|
| 4 2 0 5 8 7 5 0 3 10 8 3 0 4 7 10 4 0 |
5 1 10 2 4 8 1 3 7 1 4 5 1 2 3 2 3 |
 În ziua 1 Spider pleacă din punctul 2 și țese un fir până la punctul 3. În ziua 2, din punctul 3 țese un fir până la punctul 1 (sare punctul 4). În ziua 3 din punctul 1 țese un fir până la punctul 2. În ziua 4 din punctul 2 țese un fir până la punctul 4 (sare punctul 3). În ziua 5 din punctul 4 țese un fir până la punctul 1 și se oprește. |
