首页 > 专题系列 > Java解POJ > POJ 1465 Multiple [解题报告] Java
2013
11-09

POJ 1465 Multiple [解题报告] Java

Multiple

问题描述 :

a program that, given a natural number N between 0 and 4999 (inclusively), and M distinct decimal digits X1,X2..XM (at least one), finds the smallest strictly positive multiple of N that has no other digits besides X1,X2..XM (if such a multiple exists).

输入:

The input has several data sets separated by an empty line, each data set having the following format:

On the first line – the number N

On the second line – the number M

On the following M lines – the digits X1,X2..XM.

输出:

For each data set, the program should write to standard output on a single line the multiple, if such a multiple exists, and 0 otherwise.

An example of input and output:

样例输入:

22
3
7
0
1

2
1
1

样例输出:

110
0

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.*;
public class Main
{
 static int[] p,q;
 static int m,n;
 static Queue< mye> qu;
 public static void main(String[] args) throws IOException
 {
  Scanner in=new Scanner(System.in);
  qu=new LinkedList< mye>();
  while(in.hasNext())
  {
	qu.clear();
	n=in.nextInt();
	m=in.nextInt();
	p=new int[m];
	for(int i=0;i< m;i++)
		p[i]=in.nextInt();
	Arrays.sort(p);
	if(n==0)
		System.out.println(0);
	else {
		q=new int[n];
	bsf(q,p);
	if(q[0]==0)System.out.print(0);
	System.out.println();
	}		
    }
 }

  static void f(mye e)
  {
   if(e.pre!=null)
   {
	f(e.pre);
   }
   if(e.pre!=null)System.out.print(e.curN);
  }


  static void bsf(int[] q,int[] p)
  {
   qu.add(new mye(0,0,null));
   while(!qu.isEmpty())
   {
	mye uu=qu.poll();
	int num=uu.dig*10;
	for(int i=0;i< m;i++)
	{
	  int k=num+p[i];
	  if(k==0) continue;
	  k%=n;
	  if(q[k]==0)
	  {
	   q[k]++;
	   if(k==0)
	   {
		mye tt=new mye(k,p[i],uu);
		f(tt);
		return;
	   }
	   qu.add(new mye(k,p[i],uu));
	 }
	}
    }		
 }
}
class mye
{
	int dig=0;
	int curN;
	mye pre;
	public mye(int d,int c,mye e)
	{
		dig=d;
		curN=c;
		pre=e;
	}
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.