首页 > 专题系列 > Java解POJ > POJ 1016 Numbers That Count [解题报告] Java
2013
11-08

POJ 1016 Numbers That Count [解题报告] Java

Numbers That Count

问题描述 :

“Kronecker’s Knumbers” is a little company that manufactures plastic digits for use in signs (theater marquees, gas station price displays, and so on). The owner and sole employee, Klyde Kronecker, keeps track of how many digits of each type he has used by maintaining an inventory book. For instance, if he has just made a sign containing the telephone number “5553141″, he’ll write down the number “5553141″ in one column of his book, and in the next column he’ll list how many of each digit he used: two 1s, one 3, one 4, and three 5s. (Digits that don’t get used don’t appear in the inventory.) He writes the inventory in condensed form, like this: “21131435″.

The other day, Klyde filled an order for the number 31123314 and was amazed to discover that the inventory of this number is the same as the number—it has three 1s, one 2, three 3s, and one 4! He calls this an example of a “self-inventorying number”, and now he wants to find out which numbers are self-inventorying, or lead to a self-inventorying number through iterated application of the inventorying operation described below. You have been hired to help him in his investigations.

Given any non-negative integer n, its inventory is another integer consisting of a concatenation of integers c1 d1 c2 d2 … ck dk , where each ci and di is an unsigned integer, every ci is positive, the di satisfy 0<=d1<d2<…<dk<=9, and, for each digit d that appears anywhere in n, d equals di for some i and d occurs exactly ci times in the decimal representation of n. For instance, to compute the inventory of 5553141 we set c1 = 2, d1 = 1, c2 = 1, d2 = 3, etc., giving 21131435. The number 1000000000000 has inventory 12011 (“twelve 0s, one 1″).

An integer n is called self-inventorying if n equals its inventory. It is called self-inventorying after j steps (j>=1) if j is the smallest number such that the value of the j-th iterative application of the inventory function is self-inventorying. For instance, 21221314 is self-inventorying after 2 steps, since the inventory of 21221314 is 31321314, the inventory of 31321314 is 31123314, and 31123314 is self-inventorying.

Finally, n enters an inventory loop of length k (k>=2) if k is the smallest number such that for some integer j (j>=0), the value of the j-th iterative application of the inventory function is the same as the value of the (j + k)-th iterative application. For instance, 314213241519 enters an inventory loop of length 2, since the inventory of 314213241519 is 412223241519 and the inventory of 412223241519 is 314213241519, the original number (we have j = 0 in this case).

Write a program that will read a sequence of non-negative integers and, for each input value, state whether it is self-inventorying, self-inventorying after j steps, enters an inventory loop of length k, or has none of these properties after 15 iterative applications of the inventory function.

输入:

A sequence of non-negative integers, each having at most 80 digits, followed by the terminating value -1. There are no extra leading zeros.

输出:

For each non-negative input value n, output the appropriate choice from among the following messages (where n is the input value, j is a positive integer, and k is a positive integer greater than 1):

n is self-inventorying

n is self-inventorying after j steps

n enters an inventory loop of length k

n can not be classified after 15 iterations

样例输入:

22 
31123314 
314213241519 
21221314 
111222234459 
-1

样例输出:

22 is self-inventorying 
31123314 is self-inventorying 
314213241519 enters an inventory loop of length 2 
21221314 is self-inventorying after 2 steps 
111222234459 enters an inventory loop of length 2 

解题代码:

(1)
import java.util.*;
import java.io.*;

public class Main{
    
    public static void main(String rgs[]) throws Exception
    {        
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while(true){
            String s = cin.next();
            if(s.equals("-1"))
                break;
            String[] t = new String[16];//保存s与15个变换结果
            int i;
            t[0]=s;
            for(i=0;i< 15;i++){
                t[i+1] = change(t[i]);
                int res = Judge (t,i+1); //判断
                if(res==1 && i==0){
                    System.out.println(s+" is self-inventorying ");
                    break;
                }
                if(res==1){
                    System.out.println(s+" is self-inventorying after "+i+" steps ");
                    break;
                }
                if(res>0){
                    System.out.println(s+" enters an inventory loop of length "+res+" ");
                       break;
                }
            }
            if(i==15)
                System.out.println(s+" can not be classified after 15 iterations ");
        }
    }
    
    //输出s的Inventory 数,输入5553141则输出21131435 
    public static String change(String s){
        int i,n=s.length();
        int[] count=new int[10];
        String t="";
        Arrays.fill(count,0);
        for(i=0;i< n;i++)
            count[s.charAt(i)-'0']++;
        for(i=0;i< 10;i++){
            if(count[i]>0)
                t+=String.valueOf(count[i])+String.valueOf(i);
        }        
        return t;
    }
    
    //第ind次变换结果与前面所有结果比较
    public static int Judge(String[] t,int ind){
        for(int i=0;i< ind;i++){
            if(t[ind].equals(t[i])){
                if(ind==i+1)
                    return 1;
                else 
                    return ind-i;
            }
        }
        return 0;
    }

}
(2)
import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.Arrays;

 public class Main {

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         String s;
         char[][] c;
         char[] next;
         int step;
         int[] num;
         int result;
         StringBuffer buff = new StringBuffer();
         while (!(s = read.readLine()).startsWith("-")) {
             c = new char[15][];
             step = 2;
             num = new int[10];
             c[0] = s.toCharArray();
             while (true) {
                 Arrays.fill(num, 0);
                 for (int i = 0; i < c[step - 2].length; i++) {
                     num[c[step - 2][i] - '0']++;
                 }
                 buff.delete(0, buff.length());
                 for (int i = 0; i < 10; i++) {
                     if (num[i] != 0) {
                         buff.append(num[i]);
                         buff.append(i);
                     }
                 }
                 next = buff.toString().toCharArray();
                 if ((result = equal(c, next, step)) != -1) {
                     if (step == 2) {
                         System.out.printf("%s is self-inventorying\n", s);
                     } else {
                         if (step - result == 2) {
                             System.out.printf(
                                     "%s is self-inventorying after %d steps\n",
                                     s, step - 1);
                         } else {
                             System.out
                                     .printf(
                                             "%s enters an inventory loop of length %d\n",
                                             s, step - result - 1);
                         }
                     }
                     break;
                 } else {
                     if (step >= 15) {
                         System.out
                                 .printf(
                                         "%s can not be classified after 15 iterations\n",
                                         s);
                         break;
                     }
                     c[step - 1] = next;
                     step++;
                 }
             }
         }
     }

     public static int equal(char[][] a, char[] b, int t) {
         int[] aa = new int[10];
         int[] bb = new int[10];
         loop: for (int i = 0; i < t - 1; i++) {
             Arrays.fill(aa, 0);
             Arrays.fill(bb, 0);
             if (a[i].length != b.length) {
                 continue;
             } else {
                 for (int j = 0; j < b.length; j++) {
                     aa[a[i][j] - '0']++;
                     bb[b[j] - '0']++;
                 }
                 for (int j = 0; j < 10; j++) {
                     if (aa[j] != bb[j]) {
                         continue loop;
                     }
                 }
                 return i;
             }
         }
         return -1;
     } 
}

  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

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

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