Dramatic Multiplications

From Progteam

Revision as of 03:37, 10 November 2007 by Jjx203 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Jjx203.


Dramatic Multiplication | Jiexun Xu

Idea: construct two arrays of integers, number and answer, of sizes 100. Number represent the expected solution if possible. The input for each data set is a multipler n and the last digit of the expected solution k. Apparently if n>k, there won't be any solution. When n<=k, the last index(index 99) of number is set to k(number[99]=k). Then, a for loop counting from i=99 downto 0 is applied so that at the ith iteration, answer[i] is calculated as answer[i]=number[i]*n+carry, and number[i-1]=answer[i] according to the property of dramatic multiplication. Whenever the program detects that answer[i]=k and carry=0, the program terminates and the answer is printed.

import java.util.*;

public class Multiplication{
	static int[] number;
	static int[] answer;
	public static void main(String[] args){		
		Scanner reader=new Scanner(System.in);
		int count=reader.nextInt();
		for(int j=0;j<count;j++){
			boolean shouldPrint=false;
			int n=reader.nextInt();
			int k=reader.nextInt();
			if(n>k){
				System.out.println(0);
				continue;
			}
			number=new int[100];
			answer=new int[100];
			number[99]=k;
			int carry=0;
			int lastIndex=99;			
			for(int i=99;i>=0;i--){
			//	printNum();
			//	printAns();				
				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();
			}
		}
	}
	
	public static long toLong(){
		long num=0;
		for(int i=0;i<=9;i++){
			num=num+(long)(Math.pow(10,9-i)*number[i]);
		}
		return num;
	}
	
	public static void printAns(){		
		System.out.print("Ans:");
		int lastIndex=99;
		for(int i=0;i<=99;i++){
			if(answer[i]!=0){
				lastIndex=i;
				break;
			}
		}
		for(int i=lastIndex;i<=99;i++){
			System.out.print(answer[i]+"");
		}
		System.out.println();
	}
	
	public static void printNum(){
		System.out.print("Num:");
		int lastIndex=99;
		for(int i=0;i<=99;i++){
			if(number[i]!=0){
				lastIndex=i;
				break;
			}
		}
		for(int i=lastIndex;i<=99;i++){
			System.out.print(number[i]+"");
		}
		System.out.println();
	}
}
Personal tools