Search This Blog

Loading...

Friday, March 30, 2012

Rezolvarea problemei "talent"


Acum 2 zile am publicat enuntul problemei "talent", data  la ONI 2011 clasei a VI-a si v-am lasat timp sa o rezolvati. Problema a fost destul de interesanta si in algoritmul de rezolvare se ascundeau niste idei de optimizare a timpului de executie esentiale celor ce vroiau sa ia 100 de puncte. Iata mai jos rezolvarea problemei:


#include <fstream>
using namespace std;
ifstream fin("talent.in");
ofstream fout("talent.out");
long sp[15001],dist[15001];
int main ()
{
 long n,nr,cop,x=0,y,i,j,cif[11],imp,cnt,pali,p=1,t,k,max=0, min=2000000001;
 fin>>n;
 for(i=1; i<=n; i++)
 {
  fin>>nr;
  cop=nr;
  cnt=0;
  imp=0;
  for(j=0; j<10; j++)
   cif[j]=0;
  while(cop>0)
  {
   cif[cop%10]++;
   cnt++;
   cop/=10;
  }
  for(j=0; j<10; j++)
   if(cif[j]%2==1)
    imp++;
  if(cif[0]==cnt-1 && cif[0]!=0)
   pali=0;
  else
   if(imp==0 || imp==1)
    pali=1;
   else 
    pali=0;
  if(pali==1)
  {
   sp[p]=nr;
   p++;
   x++;
  }
 }
 if(p>1)
 {
  for(k=1; k<p; k++)
  {
   cop=sp[k];
   cnt=0;
   dist[k]=1;
   for(j=0; j<10; j++)
    cif[j]=0;  
   for(j=1; cop>0; j++)
   {
    cif[j]=cop%10;
    cop/=10;
    cnt++;
   }
   for(i=1; i<cnt; i++)
    for(j=i+1; j<=cnt; j++)
     if(cif[i]>cif[j])
     {
     t=cif[i];
     cif[i]=cif[j];
     cif[j]=t;
     }
   for(i=2; i<=cnt; i++)
    if(cif[i]!=cif[i-1])
     dist[k]++;
  }
  
  for(i=1; i<p; i++)
   if(dist[i]>max)
    max=dist[i];
  for(i=1; i<p; i++)
   if(sp[i]<min && dist[i]==max)
   {
    min=sp[i];
    y=min;
   }
 }
 else
  y=0;
 fout<<x<<" "<<y<<endl;
 fin.close();
 fout.close();
 return 0;
}
Daca nu ati inteles ceva din rezolvarea problemei, lasati un comentariu si va voi explica.