`
Simone_chou
  • 浏览: 182750 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

An Easy Number Game(生成序列)

 
阅读更多
D - An Easy Number Game
Crawling in process... Crawling failed Time Limit:2000MS     Memory Limit:65535KB     64bit IO Format:%lld & %llu

Description

There are 8 non-negative intergers (no greater than 9) and a number x, can you make a eight-digit number(without leading zeros) with these intergers with the additional condition that the eight-digit number should be divided by the number x.

Input

The first line of the input contains a single integer T (1 <= T <= 100), the number of test cases, followed by the input data for each test case. The first line of each test case contains 8 integers, while the second line contains the interger x (1 <= x <= 100000000).

Output

For each case, if you can form such a eight-digit number,output "Yes", otherwise,output "No".

Sample Input

2
1 2 3 4 5 6 7 8
12345678
1 2 3 4 5 6 7 8
12345677

Sample Output

Yes
No 

       题意:

       有T个例子,8个少于9的非负数组成的数,输入这8个数,判断有一个组成数能否被x整除,如果能,则输出Yes,不能则输出No。

 

       思路:

       用next_permutation()函数来不断生成排列数,生成一个就组成一个新的数判断能否被x整除,一旦有则输出Yes,无则输出No。(注意:因为输入的8个数之中可以存在非负数,即有可能是0,则应排除前导0的情况)

       AC:

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int number[10],temp;
	int i,n;
	long long x,t;
	scanf("%d",&n);
	while(n--)
	{
	 	temp=0;
	 	for(i=0;i<8;i++)
	   		scanf("%d",&number[i]);
	 	scanf("%lld",&x);
	 	sort(number,number+8);
	    do
	    {
			t=0;
			i=8;
			if(!number[i-1]) continue;
			while(i--)
			{
			  t=t*10+number[i];
			}
//从后往前扫,判断最后一位(最高位为最后一位)
			if(t%x==0) 
			{
				temp=1;
				break;
			}
	    }while(next_permutation(number,number+8));
	if(temp) printf("Yes\n");
	else     printf("No\n");
    }
	return 0;
}

   总结:

   1.要忽略前导0的情况,因为输入的数可能是0,那么排列的时候第一位有可能是0;

   2.第一位为0的数量和最后一位为0的排列数量是一样的,但是这题不是单纯看数目,关键是要看这个数能否整除x,就算数量能抵消,本身排出来的这个数也是不一样的,所以影响结果的关键是本身的这个数,而不是符合条件总共的数量。所以要不从头往后扫,然后判断第一位(最高位为第一位);要不从后往前扫,判断最后一位(最高位为最后一位)。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics