Fişierul intrare/ieşire:spider.in, spider.outSursăONI 2004 clasa a 6-a
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 intrareCe 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şireCe 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.inspider.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici