Cod sursa(job #328045)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 30 iunie 2009 20:18:09
Problema Lampa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <string>
using namespace std;
#define mp make_pair
const int LMAX=100001;
int N,M;
string S,fu,fp,fn,A,B;
ifstream f("lampa.in");
ofstream g("lampa.out");
int verifica(int la,int lb)
{
    int i,j=la+lb,k;
    A="";B="";
    if (fn[0]=='a')
    {
       A.assign(S,0,la);
       B.assign(S,la,lb);
    }
    else
    {
       B.assign(S,0,lb);
       A.assign(S,lb,la);
    }
    
    for (i=2;i<(int)fn.length();++i)
      if (fn[i]=='a')
        {for (k=0;k<la;++k) if (S[j++]!=A[k]) return 0;}
      else
        {for (k=0;k<lb;++k) if (S[j++]!=B[k]) return 0;} 
    return 1;
    }
int main()
{
    int i,j;
    pair<int,int> ult,pen,now;
    f>>N>>M;
    getline(f,S);
    getline(f,S);
    
    ult=mp(1,0);
    pen=mp(0,1);
    fu="a";fp="b";
    fu.reserve(LMAX);
    fp.reserve(LMAX);
    fn.reserve(LMAX);
    for (i=3;i<=N;++i)
    {
        now=mp(ult.first+pen.first,ult.second+pen.second);
        ult=pen;pen=now;
        fn=fu+fp;
        fu=fp;fp=fn;
    }
    
    A.reserve(LMAX);B.reserve(LMAX);
    for (i=1,M-=now.first;M>0;++i,M-=now.first)
      if (M%now.second==0)
      {
        j=M/now.second;
        if (verifica(i,j)) 
        {
          g<<A<<'\n'<<B;
          return 0;
        }
      }
        
    g<<0;      
          
    return 0;
}