USACO - 2.2.1 - Preface Numbering

原创文章转载请注明出处

摘要：模拟 ， 数学分析

一. 题目翻译

1. 描述：

2. 格式：

          INPUT FORMAT:

          (preface.in)

          一个整数N。

          OUTPUT FORMAT:

          (preface.out)

          每行一个字符和一个数字k，表示这个字符出现了k次。字符必须按数字表中的递增顺序输出。

3. SAMPLE：

          SAMPLE INPUT:

 5

          SAMPLE OUTPUT:

I 7

V 2

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          这道题目看起来比较复杂， 仔细分析以后其实可以当做一个数学问题来考虑。由于题目中已经说明了一个数字用罗马数字表示有且只有一种，输入的数字N是小于3500的，并且对于一个数字，合法的表示是对千位、百位、十位、个位拆分表示（eg : 490表示为CDXC，而非XD）。那么我们可以预先计算出 1~ 9 10 ~ 90 100 ~ 900 1000 ~ 3000的所有数字，也就是个位、十位、百位和千位。然后对输入的数字N计算法出个位、十位、百位和千位是多少，然后查预先计算出来的表即可。

 

2. 具体实现（具体实现过程中出现的问题）：

          重点在于计算出的字符，高位的可以参考低位的，大家可以自己考虑一下如何计算这个数组。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:preface
*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class preface {
	// 1 , 5 , 10 , 50 , 100 , 500 , 1000
static int[][] gewei = new int[][] { { 0, 0, 0, 0, 0, 0, 0 },
			{ 1, 0, 0, 0, 0, 0, 0 }, { 2, 0, 0, 0, 0, 0, 0 },
			{ 3, 0, 0, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0, 0, 0 },
			{ 0, 1, 0, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0, 0, 0 },
			{ 2, 1, 0, 0, 0, 0, 0 }, { 3, 1, 0, 0, 0, 0, 0 },
			{ 1, 0, 1, 0, 0, 0, 0 }, };
	static int[][] shiwei = new int[][] { { 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 2, 0, 0, 0, 0 },
			{ 0, 0, 3, 0, 0, 0, 0 }, { 0, 0, 1, 1, 0, 0, 0 },
			{ 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 1, 1, 0, 0, 0 },
			{ 0, 0, 2, 1, 0, 0, 0 }, { 0, 0, 3, 1, 0, 0, 0 },
			{ 0, 0, 1, 0, 1, 0, 0 } };
	static int[][] baiwei = new int[][] { { 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 2, 0, 0 },
			{ 0, 0, 0, 0, 3, 0, 0 }, { 0, 0, 0, 0, 1, 1, 0 },
			{ 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 1, 1, 0 },
			{ 0, 0, 0, 0, 2, 1, 0 }, { 0, 0, 0, 0, 3, 1, 0 },
			{ 0, 0, 0, 0, 1, 0, 1 } };;
	static int[][] qianwei = new int[][] { { 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0, 0, 2 },
			{ 0, 0, 0, 0, 0, 0, 3 } };
	static char[] trans = new char[]{'I','V','X','L','C','D','M'};
	
	public static void main(String[] args) {
		try {
//			Scanner in = new Scanner(System.in);
//			PrintWriter pw = new PrintWriter(System.out);
			Scanner in = new Scanner(new BufferedReader(new FileReader(
			"preface.in")));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
			"preface.out")));
			int num = in.nextInt();
			int[] count = new int[7];
			for (int i = 1; i <= num; i++) {
//			int geweishu = i % 10;
//			int shiweishu = i / 10;
//			int baiweishu = i / 100;
//			int qianweishu = i / 1000;
			int qianweishu = i /1000;
			int baiweishu = (i - qianweishu*1000)/100;
			int shiweishu = (i - qianweishu*1000 - baiweishu*100)/10;
			int geweishu = i % 10;
			for (int j = 0; j < 7; j++) {
				count[j] = gewei[geweishu][j] + shiwei[shiweishu][j]
						+ baiwei[baiweishu][j] + qianwei[qianweishu][j]+count[j];
				}
			}
			for (int i=0;i<7;i++){
				if (count[i]!=0){
					pw.println(trans[i]+" "+count[i]);
				}
			}
			pw.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
			
	}

}