首页 > 专题系列 > Java解POJ > POJ 3095 Linear Pachinko [解题报告] Java
2013
11-12

POJ 3095 Linear Pachinko [解题报告] Java

Linear Pachinko

问题描述 :

This problem is inspired by Pachinko, a popular game in Japan. A traditional Pachinko machine is a cross between a vertical pinball machine and a slot machine. The player launches small steel balls to the top of the machine using a plunger as in pinball. A ball drops through a maze of pins that deflect the ball, and eventually the ball either exits at a hole in the bottom and is lost, or lands in one of many gates scattered throughout the machine which reward the player with more balls in varying amounts. Players who collect enough balls can trade them in for prizes.

For the purposes of this problem, a linear Pachinko machine is a sequence of one or more of the following: holes ("."), floor tiles ("_"), walls ("|"), and mountains ("/\"). A wall or mountain will never be adjacent to another wall or mountain. To play the game, a ball is dropped at random over some character within a machine. A ball dropped into a hole falls through. A ball dropped onto a floor tile stops immediately. A ball dropped onto the left side of a mountain rolls to the left across any number of consecutive floor tiles until it falls into a hole, falls off the left end of the machine, or stops by hitting a wall or mountain. A ball dropped onto the right side of a mountain behaves similarly. A ball dropped onto a wall behaves as if it were dropped onto the left or right side of a mountain, with a 50% chance for each. If a ball is dropped at random over the machine, with all starting positions being equally likely, what is the probability that the ball will fall either through a hole or off an end?

For example, consider the following machine, where the numbers just indicate character positions and are not part of the machine itself:

123456789
/\.|__/\.

The probabilities that a ball will fall through a hole or off the end of the machine are as follows, by position: 1=100%, 2=100%, 3=100%, 4=50%, 5=0%, 6=0%, 7=0%, 8=100%, 9=100%. The combined probability for the whole machine is just the average, which is approximately 61.111%.

输入:

The input consists of one or more linear Pachinko machines, each 1–79 characters long and on a line by itself, followed by a line containing only “#” that signals the end of the input.

输出:

For each machine, compute as accurately as possible the probability that a ball will fall through a hole or off the end when dropped at random, then output a single line containing that percentage truncated to an integer by dropping any fractional part.

样例输入:

/\.|__/\.
_._/\_|.__/\./\_
...
___
./\.
_/\_
_|.|_|.|_|.|_
____|_____
#

样例输出:

61
53
100
0
100
50
53
10

解题代码:

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 

public class Main { 

    public static void main(String[] args) throws IOException { 
        BufferedReader read = new BufferedReader(new InputStreamReader( 
                System.in)); 
        String s; 
        while (!(s = read.readLine()).equals("#")) { 
            char[] c = s.toCharArray(); 
            int[] p = new int[c.length]; 
            for (int i = 0; i < c.length; i++) { 
                if (c[i] == '.') { 
                    p[i] = 100; 
                } else if (c[i] == '_') { 
                    p[i] = 0; 
                } else if (c[i] == '|') { 
                    int k = 1; 
                    while (true) { 
                        if (i - k < 0) { 
                            p[i] += 50; 
                            break; 
                        } 
                        if (c[i - k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i - k] == '.' || c[i - k] == '/') { 
                            p[i] += 50; 
                            break; 
                        } else if (c[i - k] == '|' || c[i - k] == '\\') { 
                            break; 
                        } 
                    } 
                    k = 1; 
                    while (true) { 
                        if (i + k == c.length) { 
                            p[i] += 50; 
                            break; 
                        } 
                        if (c[i + k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i + k] == '.' || c[i + k] == '\\') { 
                            p[i] += 50; 
                            break; 
                        } else if (c[i + k] == '|' || c[i + k] == '/') { 
                            break; 
                        } 
                    } 
                } else if (c[i] == '/') { 
                    int k = 1; 
                    while (true) { 
                        if (i - k < 0) { 
                            p[i] = 100; 
                            break; 
                        } 
                        if (c[i - k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i - k] == '.' || c[i - k] == '/') { 
                            p[i] = 100; 
                            break; 
                        } else if (c[i - k] == '|' || c[i - k] == '\\') { 
                            break; 
                        } 
                    } 
                } else if (c[i] == '\\') { 
                    int k = 1; 
                    while (true) { 
                        if (i + k == c.length) { 
                            p[i] = 100; 
                            break; 
                        } 
                        if (c[i + k] == '_') { 
                            k++; 
                            continue; 
                        } else if (c[i + k] == '.' || c[i + k] == '\\') { 
                            p[i] = 100; 
                            break; 
                        } else if (c[i + k] == '|' || c[i + k] == '/') { 
                            break; 
                        } 
                    } 
                } 
            } 
            int sum = 0; 
            for (int i = 0; i < p.length; i++) { 
                sum += p[i]; 
            } 
            System.out.println(sum / p.length); 
        } 
    } 
}

  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。