农民Brown和John的牛们计划协同逃出它们各自的农场。它们设计了一种加密方法用来保护它们的通讯不被他人知道。
如果一头牛有信息要加密，比如"International Olympiad in Informatics"，它会随机地把C，O，W三个字母插到到信息中（其中C在O前面，O在W前面），然后它把C与O之间的文字和 O与W之间的文字的位置换过来。这里是两个例子：
International Olympiad in Informatics
->
CnOIWternational Olympiad in Informatics
International Olympiad in Informatics
->
International Cin InformaticsOOlympiad W
为了使解密更复杂，牛们会在一条消息里多次采用这个加密方法（把上次加密的结果再进行加密）。一天夜里，John的牛们收到了一条经过多次加密的信息。请你写一个程序判断它是不是这条信息经过加密（或没有加密）而得到的：
Begin the Escape execution at the Break of Dawn
格式
PROGRAM NAME:cryptcow
INPUT FORMAT:(file cryptcow.in)
一行,不超过75个字符的加密过的信息。
OUTPUT FORMAT:(file cryptcow.out)
一行，两个整数. 如果能解密成上面那条逃跑的信息，第一个整数应当为1，否则为0；如果第一个数为1，则第二个数表示此信息被加密的次数，否则第二个数为0。
SAMPLE INPUT
Begin the EscCution at the BreOape execWak of Dawn
SAMPLE OUTPUT
1 1
nocow分析和优化技巧：
基本的思路很简单：按从小到大的顺序依次找出C,O,W，然后交换中间的两个串并将这三个字符删掉。如此往复直到没有成对的C,O,W，judge一下最后生成的字符串是否是题目所给的串。但是单纯的按上述算法只能通过20%的数据。我们需要进一步优化。
优化技巧
1. 由于添加的COW是一起的，因此给出的字符串的字符个数应该等于47（目标字符串的长度）+3*k。如果不满足就可直接判断无解。
2. 除了COW三个字符外，其他的字符的个数应该和目标串相一致。如果不一致也可直接判断无解。
3. 搜索中间肯定会出现很多相同的情况，因此需要开一个hash来记录搜索到过哪些字符串，每搜索到一个字符串，就判重。如果重复直接剪枝。这里的字符串的hash函数可以采用ELFhash，但由于ELFhash的数值太大，所以用函数值对一个大质数（我用的是99991）取余，这样可以避免hash开得太大，同时又可以减少冲突。
4. 对搜索到的字符串，设不包含COW的最长前缀为n前缀（同样也可以定义n后缀），那么如果n前缀不等于目标串的长度相同的前缀，那么当前字符串一定无解，剪枝。N后缀也可采取相同的判断方法。
5. 一个有解的字符串中，COW三个字母最早出现的应该是C，最后出现的应该是W，如果不满足则剪枝。
6. 当前字符串中任意两个相邻的COW字母中间所夹的字符串一定在目标串中出现过。如果不符合可立即剪枝。
7. 需要优化搜索顺序。经过试验我们可以发现，O的位置对于整个COW至关重要。可以说，O的位置决定了整个串是否会有解。因此，我们在搜索时，应该先枚举O的位置，然后再枚举C和W的位置。其中W要倒序枚举。这样比依次枚举COW至少要快20~30倍。
8. 在判断当前串的子串是否包含在目标串中的时候，可以先做一个预处理：记录每一个字母曾经出现过的位置，然后可以直接枚举子串的第一个字母的位置。这样比用pos要快2倍左右。
经过上述优化，程序对于极端数据也可以在1s以内出解。
其实只用3、4、6、7就可以进1s。
【参考程序】：//C++打了几十遍的no ac，只能贴个pascal（一定补上）
{
ID: XIONGNA1
PROG: cryptcow
LANG: PASCAL
}
var ss,st:string;
hash:array[0..50239] of boolean;
procedure print(step:integer);
begin
writeln(1,' ',step);
close(output);
halt;
end;
function checkhash(now:string):boolean;
var g,h,i:longword;
begin
h:=0;
for i:=1 to length(now) do
begin
h:=h shl 4 + ord(now[i]);
g:=h and $f0000000;
if g<>0 then h:=h xor (g shr 24);
h:=h and (not g);
end;
h:=h mod 50239;
if hash[h] then
begin
hash[h]:=false;
checkhash:=false;
exit;
end;
checkhash:=true;
end;
function check(now:string):boolean;
var i,j:integer;
a:string;
begin
for i:=1 to length(now) do
if (now[i]='C')or(now[i]='O')or(now[i]='W') then
begin
for j:=i+1 to length(now) do
if (now[j]='C')or(now[j]='O')or(now[j]='W') then
break;
a:=copy(now,i+1,j-i-1);
if a='' then continue;
for j:=1 to length(a) do
if (a[j]='C')or(a[j]='O')or(a[j]='W') then
delete(a,j,1);
if pos(a,ss)=0 then
begin
check:=false;
exit;
end;
end;
check:=true;
end;
procedure search(now:string;step:integer);
var i,j,k:integer;
next :string;
begin
if now=ss then print(step);
if checkhash(now) then exit;
if not check(now) then exit;
for j:=1 to length(now) do
if now[j]='O' then
for i:=j-1 downto 1 do
if now[i]='C' then
for k:=length(now) downto j+1 do
if now[k]='W' then
begin
next:= copy(now,1,i-1)
+copy(now,j+1,k-j-1)
+copy(now,i+1,j-i-1)
+copy(now,k+1,100);
search(next,step+1);
end;
end;
begin
//while not eof do
//begin
assign(input,'cryptcow.in');reset(input);
assign(output,'cryptcow.out');rewrite(output);
ss:='Begin the Escape execution at the Break of Dawn';
readln(st);
fillchar(hash,sizeof(hash),true);
search(st,0);
writeln('0 0');
close(output);
//end;
end.