首页 > 专题系列 > Java解POJ > POJ 1302 Blue Gene, Jr. [解题报告] Java
2013
11-09

POJ 1302 Blue Gene, Jr. [解题报告] Java

Blue Gene, Jr.

问题描述 :

Inspired by IBM’s Blue Gene project, the CEO of Universal Biological Machinery (UBM), has called on you, UBM’s top software engineer, to develop a program that will calculate the mutation of the Areopagus-virus, a virus discovered on Mars by your company’s privately-subsidized (top-secret) space program.

输入:

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:
  1. Start line – A single line, “START N”, where 1 <= N <= 20.
  2. Viral code – A sequence of N alphanumeric characters. Alphanumeric characters will consist of an uppercase letter (A-Z) or a digit (0-9).
  3. End line – A single line, “END”

Following the final data set will be a single line, “ENDOFINPUT”.

输出:

For each data set, there will be exactly one output set, and there will be no blank lines separating output sets.

A single output set consists of a single line of the viral code after it has stabilized (through mutating).

The viral code will mutate according to the following rules:

  1. Initially the first viral segment to mutate begins with the first alphanumeric character of the viral code and ends with the rightmost alphanumeric character of the code.
  2. If the first alphanumeric character of a viral segment is a letter (A-Z), that alphanumeric character is considered “unstable”, and will mutate into n, where n is the number of mutations that occur to the viral segment immediately to the unstable alphanumeric character’s right (see #5), unless n is greater than 9, in which case the unstable alphanumeric character will mutate into n % 10. Also, if there is no viral segment immediately to the right of the unstable alphanumeric character, the unstable alphanumeric character will mutate into 0.
  3. If the first alphanumeric character of a viral segment, n, is a positive number (1-9), that alphanumeric character is also considered “unstable”, and will mutate into n-1. It also causes the viral segment beginning with the alphanumeric character n alphanumeric characters to its right and ending with the rightmost alphanumeric character of the viral code to mutate. If there is no alphanumeric character n alphanumeric characters to its right, then the viral segment immediately to its right (see #5), if one exists, will mutate.
  4. If the first alphanumeric character of a viral segment is 0, that alphanumeric character is considered “stable”, and will not mutate (the alphanumeric character will remain a 0 and a mutation will not be considered to have occurred).
  5. A viral segment immediately to the right of an alphanumeric character begins with the alphanumeric character one position to its right and ending with the rightmost alphanumeric character of the viral code.

样例输入:

START 1
A
END
START 4
A1B2
END
START 15
A3B2CCC4AD1232R
END
START 15
0ABCDEFGHIJKLMN
END
START 11
ABCDEFGHIJK
END
START 10
9AAAAAAAAA
END
ENDOFINPUT

样例输出:

0
3011
82B26543AD11310
0ABCDEFGHIJKLMN
09876543210
8AAAAAAAA0

解题代码:

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
 static Scanner cin;
 public static void main(String args[]){
   cin = new Scanner(System.in);
   while(run()==true)
		;
 }

static boolean run(){
  String marker = cin.next();
  if(marker.compareTo("ENDOFINPUT")==0)
    return false;

  int n = cin.nextInt();
  Sequence seq = new Sequence(cin.next());
  System.out.println(seq.mutatedSequence());
  cin.next();
  return true;
 }

}

class Sequence{
 char[] content;
 public Sequence(String s){
   content = s.toCharArray();
 }

 public Sequence(char[] content){
   this.content = content;
 }

 private int mutate(int start){
  int count;

  if(start>=content.length)
   return 0;
  char c = content[start];
  if(isLetter(c)){
    count = mutate(start+1);
    content[start] = (char)(count%10+'0');
    count++;
    return count;
   }
  else if(c == '0')
    return 0;
  else if(isNumber(c)){
    content[start] = (char)(c-1);
    if((start+c-'0')< content.length)
	count = mutate(start+c-'0');
    else
	count = mutate(start+1);
    count++;
    return count;
  }
			
  return -1;
}

 private boolean isLetter(char c){
   if((c<='Z')&&(c>='A'))
     return true;
   return false;
  }

 private boolean isNumber(char c){
   if((c<='9')&&(c>='0'))
     return true;
   return false;
 }


 String mutatedSequence(){
   mutate(0);
   return new String(content);
 }
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.