首页 > 专题系列 > Java解POJ > POJ 2897 Dramatic Multiplications [解题报告] Java
2013
11-05

POJ 2897 Dramatic Multiplications [解题报告] Java

Dramatic Multiplications

问题描述 :

Hassan, helping with his younger brother’s homework, found out that when you multiply 102564 by 4, its right-most digit moves to the left, and the other digits move one position to the right; i.e. 4 * 102564 = 410256. We call a number that has this property when multiplied by n, an n-dramatic number. For instance, 102564 and 128205 are both 4-dramatic. Given two one-digit numbers n and k, the goal is to find the smallest n-dramatic number that its rightmost digit is k.

输入:

On the first line of the input, there is an integer t, which is the number of cases that follow. Each test case, is on a line by itself, and contains two integers n and k, where 1 <= n <= 9, and 1 <= k <= 9.

输出:

For each test case, output a single integer on a line by itself, which is the smallest n-dramatic number that its rightmost digit is k. If no such number exists, output 0 instead.

样例输入:

2
4 5
2 1

样例输出:

128205
0

解题代码:

//* @author  [email protected]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
 public static void main(String[] args) throws IOException{
  BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
    int[] number=new int[100];
    int[] answer=new int[100];
    int count=Integer.parseInt(stdin.readLine()),carry, lastIndex,n,k;
    StringTokenizer token;
    for(int j=0;j< count;j++){
     token=new StringTokenizer(stdin.readLine());
	boolean shouldPrint=false;
	n=Integer.parseInt(token.nextToken());
	k=Integer.parseInt(token.nextToken());
	if(n>k){
		System.out.println(0);
		continue;
	}
	number[99]=k;
	carry=0;
	lastIndex=99;
	for(int i=99;i>=0;i--){
		answer[i]=(number[i]*n+carry)%10;
		carry=(number[i]*n+carry)/10;
		if(answer[i]==k){
			if(carry!=0){
				if(i!=0)number[i-1]=answer[i];
				
				continue;
			}
			shouldPrint=true;
			lastIndex=i;
			break;
		}
		if(i!=0)number[i-1]=answer[i];
		
	}
	if(number[lastIndex]==0) shouldPrint=false;
	if(!shouldPrint)System.out.println(0);
	else{
		for(int i=lastIndex;i<=99;i++)	System.out.print(number[i]);
		System.out.println();
	}
    }
  }
}

  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. [email protected]