solution-code2131

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#include <cstdlib>
6
using namespace std;
7
string target="Begin the Escape execution at the Break of Dawn",s;
8
const int m1=392131,m2=413477,m3=9997,m4=10001,p1=23,p2=31,p3=17,p4=37,lt=target.length();
9
bool hash1[m1+5],hash2[m2+5],hash3[m3+5],hash4[m4+5];
10
inline bool check(string a)
11
{
12
  int i,a1=0,a2=0,a3=0,a4=0,len=a.length();
13
  for(i=0;i<len;++i)
14
  {
15
    a1=(a1*p1+a[i])%m1;
16
    a2=(a2*p2+a[i])%m2;
17
    a3=(a3*p3+a[i])%m3;
18
    a4=(a4*p4+a[i])%m4;
19
  }
20
  if(hash1[a1]&&hash2[a2]&&hash3[a3]&&hash4[a4])return false;
21
  return hash1[a1]=hash2[a2]=hash3[a3]=hash4[a4]=true;
22
}
23
inline void dfs(string s,int dep)
24
{
25
  if(!check(s))return;
26
  if(s==target)
27
  {
28
    printf("1 %d\n",dep);exit(0);
29
  }
30
  int i,j,k,ls=s.length();
31
  for(i=ls-1,j=lt-1;s[i]!='C'&&s[i]!='O'&&s[i]!='W';--i,--j)
32
  {
33
    if(s[i]!=target[j])return;
34
  }
35
  for(i=0;s[i]!='C'&&s[i]!='O'&&s[i]!='W';++i)
36
  {
37
    if(s[i]!=target[i])return;
38
  }
39
  string sub="",news;
40
  for(++i;i<ls;++i)
41
  {
42
    if(s[i]=='C'||s[i]=='O'||s[i]=='W')
43
    {
44
      if(target.find(sub)==-1)return;
45
      sub="";
46
    }
47
    else sub+=s[i];
48
  }
49
  for(i=0;i<ls;++i)
50
  {
51
    if(s[i]!='O')continue;
52
    for(j=0;j<i;++j)
53
    {
54
      if(s[j]!='C')continue;
55
      for(k=ls-1;k>i;--k)
56
      {
57
        if(s[k]!='W')continue;
58
        news=s.substr(0,j)+s.substr(i+1,k-i-1)+s.substr(j+1,i-j-1)+s.substr(k+1);
59
        dfs(news,dep+1);
60
      }
61
    }
62
  }
63
  return;
64
}
65
int main(void)
66
{
67
  getline(cin,s);
68
  dfs(s,0);
69
  printf("0 0\n");
70
  return 0;
71
}