Question

Problema panglica site: arhiva campion

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.
Exemplu
panglica.in panglica.out
5 2 4
1 2
2 1
1 0
2
2

Answer 1

#include <fstream>
using namespace std;
int n,c,v[10005],i,j,cul,cc,ll,st,dr,minn=1000000;
int main()
{
  ifstream f("panglica.in");
  ofstream g("panglica.out");
  f>>n>>c;
  for(i=1;i<=n;i++) f>>v[i];

  for(i=1;i<=n/2+1;i++)
  {
   for(j=n;j>=n/2-1;j--)
    if(v[i]==v[j])
    {
       cul=v[i];
       break;
    }
    ll=i-1+n-j;

    if(ll<minn) minn=ll,cc=cul,st=i,dr=n-j;
  }
  g<<n-minn<<"\n";
  g<<cc<<"\n";
  g<<st-1<<"\n";
  g<<dr;
  f.close();
  g.close();
  return 0;
}