Fişierul intrare/ieşire:panglica.in, panglica.outSursăONI 2002 clasa a 5-a
AutorRodica PinteaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Panglica (clasa a 5-a)

Gigel are o panglică alcătuită din benzi de 1 cm lăţime, colorate în diverse culori. Panglica are N benzi colorate cu C culori, culori pe care le vom numerota de la 1 la C. Gigel vrea ca la ambele capete ale panglicii să aibă aceeaşi culoare, dar cum nu poate schimba culorile benzilor, singura posibilitate rămâne tăierea unor bucăţi de la capete.

Cerinţă

Scrieţi un program care să determine modul de tăiere a panglicii astfel încât la cele două capete să fie benzi de aceeaşi culoare, iar lungimea panglicii obţinute să fie maximă.

Date de intrare

Fişierul de intrare panglica.in conţine:

  • pe prima linie numerele naturale N şi C separate printr-un spaţiu;
  • pe următoarele N linii descrierea panglicii: pe fiecare linie un număr natural de la 1 la C, reprezentând în ordine culorile fâşiilor ce alcătuiesc panglica.

Date de ieşire

Fişierul de ieşire panglica.out va conţine următoarele 4 numere:

  • pe prima linie numărul de fâşii rămase
  • pe linia a doua numărul culorii care se află la capete
  • pe linia a treia câte fâşii trebuie tăiate de la începutul panglicii iniţiale
  • pe linia a patra câte fâşii trebuie tăiate de la sfârşitul panglicii iniţiale

Restricţii

  • 2 ≤ N ≤ 10000
  • 1 ≤ C ≤ 200
  • Dacă există mai multe soluţii alegeţi pe cea în care se taie cât mai puţin din partea de început a panglicii.

Exemple

panglica.inpanglica.out
6 3
1
2
1
3
2
3
4
2
1
1
5 2
1
2
1
2
2
4
2
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici