随笔 - 147  文章 - 71  trackbacks - 0
<2024年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

  •  

最新评论

阅读排行榜

评论排行榜

http://acm.pku.edu.cn/JudgeOnline/problem?id=1016

举个例子来说明:
一个数5553141:他包含了2个1,1个3,1个4,3个5;
那么和起来写:21131435就是5553141的Inventory 数;
然后题目要求,给出一个数n( 最多80位),他可以被归到如下四类:
1)n is self-inventorying(n用给出那个数代,下同)
即对给出的数,求出他的Inventory 数,如果是本身,则输出该行;
例如:31123314的Inventory数仍然是31123314,输出: 31123314 is self-inventorying
2) n is self-inventorying after j steps 
对一个数求他的Inventory 数,然后再对他的Inventory数继续求,如实我们可以得到一个序列:n[0]->n[1]->n[2]…n[j]…. 如此往复,当1<=j<=15时。如果n[j]的Inventory数等于他本身,则输出该行;
例如: 21221314 -> 31321314 -> (31321314),输出: 21221314 is self-inventorying after 2 steps
3) n enters an inventory loop of length k 
仍然用n的序列说明: n[0]->n[1]->n[2]…n[j]…n[i]…. (0<=j<i<=15),当n[i]的Inventory数(记作n[k]) 等于n[0]…n[i-1]的中n[j]时,那么很显然,再求下会形成一个循环;因此我们要找出是否存在最小(k>=1)使得n序列够成循环,输出这个k;
例如: 314213241519 --> 412223241519 -->314213241519,对应上述的n[j] --> n[i] -> (n[k]) 
4) n can not be classified after 15 iterations
如果在找出15个数后,没有满足上述的任何一条,那么就输出该行;

import java.util.*;
import java.io.*;

public class poj_1016{
    
    
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];
            
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 ");
        }

    }

    
    
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;
    }

    
    
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;
    }


}
posted on 2009-09-07 10:34 飞翔天使 阅读(723) 评论(0)  编辑  收藏 所属分类: poj

只有注册用户登录后才能发表评论。


网站导航: