Combination Lock
描述
Finally, you come to the interview room. You know that a Microsoft interviewer is in the room though the door is locked. There is a combination lock on the door. There are N rotators on the lock, each consists of 26 alphabetic characters, namely, 'A'-'Z'. You need to unlock the door to meet the interviewer inside. There is a note besides the lock, which shows the steps to unlock it.
Note: There are M steps totally; each step is one of the four kinds of operations shown below:
Type1: CMD 1 i j X: (i and j are integers, 1 <= i <= j <= N; X is a character, within 'A'-'Z')
This is a sequence operation: turn the ith to the jth rotators to character X (the left most rotator is defined as the 1st rotator)
For example: ABCDEFG => CMD 1 2 3 Z => AZZDEFG
Type2: CMD 2 i j K: (i, j, and K are all integers, 1 <= i <= j <= N)
This is a sequence operation: turn the ith to the jth rotators up K times ( if character A is turned up once, it is B; if Z is turned up once, it is A now. )
For example: ABCDEFG => CMD 2 2 3 1 => ACDDEFG
Type3: CMD 3 K: (K is an integer, 1 <= K <= N)
This is a concatenation operation: move the K leftmost rotators to the rightmost end.
For example: ABCDEFG => CMD 3 3 => DEFGABC
Type4: CMD 4 i j(i, j are integers, 1 <= i <= j <= N):
This is a recursive operation, which means:
If i > j:
Do Nothing
Else:
CMD 4 i+1 j
CMD 2 i j 1For example: ABCDEFG => CMD 4 2 3 => ACEDEFG
输入
1st line: 2 integers, N, M ( 1 <= N <= 50000, 1 <= M <= 50000 )
2nd line: a string of N characters, standing for the original status of the lock.
3rd ~ (3+M-1)th lines: each line contains a string, representing one step.
输出
One line of N characters, showing the final status of the lock.
提示
Come on! You need to do these operations as fast as possible.
- 样例输入
-
7 4
ABCDEFG
CMD 1 2 5 C
CMD 2 3 7 4
CMD 3 3
CMD 4 1 7 - 样例输出
-
HIMOFIN
import java.util.Scanner;
public class Main {
public static void main(String[] argv){
Scanner in = new Scanner(System.in);
int M = in.nextInt();
int N = in.nextInt();
in.nextLine();
String source = in.nextLine();
String[] move= new String[N];
for(int i=0; i<N;i++){
move[i]=in.nextLine();
}
in.close();
int[] int_Source = new int[M];
char[] c_Source = source.toCharArray();
for(int i=0; i<M;i++){
int_Source[i]= c_Source[i]-65;
}
for(int i=0; i<N;i++){
String[] temp = move[i].split(" ");
switch(temp[1]){
case "1":
if(temp[4].length()==1)
oneMethod(int_Source,Integer.parseInt(temp[2]),Integer.parseInt(temp[3]),((int)(temp[4].toCharArray()[0]))-65);
break;
case "2":
secondMethod(int_Source,Integer.parseInt(temp[2]),Integer.parseInt(temp[3]),Integer.parseInt(temp[4]));
break;
case "3":
thirdMethod(int_Source,Integer.parseInt(temp[2]));
break;
case "4":
fourthMethod(int_Source,Integer.parseInt(temp[2]),Integer.parseInt(temp[3]));
break;
}
/*
for(int out:int_Source ){
System.out.println(out+" ");
}
System.out.println();
*/
}
for(int out:int_Source ){
System.out.print((char)(out+65));
}
}
public static void oneMethod(int[] s, int i, int j,int k){
for(int p=i-1; p<j; p++){
s[p]=k;
s[p]=s[p]%26;
}
}
public static void secondMethod(int[] s, int i, int j,int k){
for(int p=i-1; p<j; p++){
s[p]=s[p]+k;
s[p]=s[p]%26;
}
}
public static void thirdMethod(int[] s, int i){
int[] temp =new int[s.length];
for(int q=0; q<s.length;q++){
temp[q]=s[q];
}
for(int p=0; p<s.length; p++){
if(i+p<s.length)
s[p]=temp[i+p];
else
s[p]=temp[(i+p)%s.length];
s[p]=s[p]%26;
}
}
public static void fourthMethod(int[] s, int i, int j){
for(int p=i-1;p<j;p++ ){
s[p]=s[p]+p-i+2;
s[p]=s[p]%26;
}
}
}