2013
11-09

# Word

Dr. R. E. Wright’s class was studying modified L-Systems. Let us explain necessary details. As a model let us have words of length n over a two letter alphabet {a, b}. The words are cyclic, this means we can write one word in any of n forms we receive by cyclic shift, whereby the first and the last letters in the word are considered to be neighbours.

Rewriting rules rewrite a letter at a position i, depending on letters at the positions i – 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps?

Help Dr. R. E. Wright and write a program which solves this task.

There are several blocks in the input, each describing one system. There is an integer number n, 2 < n < 16 the length of the input word in the first line. There is a word in the next line. The word contains only lowercase letters a and b. There are four characters c1 c2 c3 c4 in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i - 2 is c1 and the letter at the position i is c2 and the letter at the position i + 1 is c3 then the letter at the position i after rewriting will be c4. Rewriting rules are correct and complete. There is an integer number s, 0 <= s <= 2000000000, in the last line of the block.

There is one line corresponding to each block of the input. The line contains a word which we receive after s rewriting steps from the corresponding starting word using given rewriting rules. As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.

5
aaaaa
aaab
aabb
abab
abbb
baab
babb
bbab
bbbb
1

bbbbb

//* @author: Yeming Hu"[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */"
import java.util.*;
import java.io.*;

public class Main
{
public static BufferedInputStream bis;
public static StringBuilder str;
public static char[][] rules;
public static StringBuilder[] words;
public static int k;
public static void main(String[] args) throws Exception
{
bis = new BufferedInputStream(System.in);

rules = new char[8][4];
Map< String,Boolean> exist = new HashMap< String,Boolean>();
words = new StringBuilder[40000];
StringBuilder start,result, previous, key;
str = new StringBuilder();
start = new StringBuilder();
result = new StringBuilder();
previous = new StringBuilder();
key = new StringBuilder();
for(int i = 0; i < 40000; i++)
{
words[i] = new StringBuilder();
}
while(true)
{
if(n == -1)
{
break;
}
k = 0;
start.delete(0,start.length());
result.delete(0,result.length());
result.append(start);
exist.clear();

words[k].delete(0,words[k].length());
words[k].append(lowest(result));
k++;
for(int j=0;j< s;j++)
{
previous.delete(0,previous.length());
previous.append(result);
result.delete(0,result.length());
for(int i=0;i< n;i++)
{
int i1 = (i-2+n)%n;
int i2 = i;
int i3 = (i+1)%n;
key.delete(0,key.length());
key.append(previous.charAt(i1));
key.append(previous.charAt(i2));
key.append(previous.charAt(i3));
result.append(getKey(key));
}
String lw = lowest(result);

if(exist.get(lw) == null)
{
exist.put(lw,true);
words[k].delete(0,words[k].length());
words[k].append(lw);
k++;
}else
{
int index = find(lw);
int p = j + 1 - index;
long resultIndex = ((s - j) % p - 1 + p)%p  + index;
result.delete(0,result.length());
result.append(words[(int)resultIndex]);
break;
}
}

System.out.println(lowest(result));
}
}

public static int find(String lw)
{
int index = 0;
for(int i = 0; i < k; i++)
{
boolean reached = true;
for(int j = 0; j < lw.length(); j++)
{
if(lw.charAt(j) != words[i].charAt(j))
{
reached = false;
break;
}
}
if(reached)
{
index = i;
break;
}
}
return index;
}

public static char getKey(StringBuilder sb)
{
char result = '\0';
for(int i = 0; i < 8; i++)
{
boolean reached = true;
for(int j = 0; j < 3; j++)
{
if(rules[i][j] != sb.charAt(j))
{
reached = false;
break;
}
}
if(reached)
{
result = rules[i][3];
break;
}
}
return result;
}

public static void readRules() throws Exception
{
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 4; j++)
{
while(true)
{
if(Character.isLetter(bt))
{
rules[i][j] = (char)bt;
break;
}
}
}
}
}

static String lowest(StringBuilder sb)
{
String p = sb.toString();
String min = p;
int n = p.length();
for(int i=0;i< n;i++)
{
String next = p.substring(n-1,n) + p.substring(0,n-1);
if(next.compareTo(min) < 0)
{
min = next;
}
p = next;
}
return min;
}

public static long readLong() throws Exception
{
long num = 0;
while(true)
{
if(bt == -1)
{
return -1;
}
if(Character.isDigit(bt))
{
num = num*10 + bt - '0';
break;
}
}

while(true)
{
if(!Character.isDigit(bt))
{
break;
}
num = num*10 + bt - '0';
}
return num;
}

public static StringBuilder readString() throws Exception
{
str.delete(0,str.length());
while(true)
{
if(Character.isLetter(bt))
{
str.append((char)bt);
break;
}
}

while(true)
{
if(!Character.isLetter(bt))
{
break;
}
str.append((char)bt);
}

return str;
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.