2013
12-30

# Help the vendor and get some M ^_^

A doll vendor has just received a shipment of dolls from the factory. The vendor can only sell dolls in pairs, and have to ensure that in each pair one doll is K times as large as the other. What is the maximum number of pairs that the vendor can assemble? Each doll can only be sold one time. Now the vendor wants your help to solve this problem. Of course, he will give you 30% of the profit, so, what are you waiting for?

There are multiple test cases.For each case the input contains two integers N (1<=50<=N) and K (1<=K<=25) in first line and N doll sizes (integers between 1 and 100000, inclusive) below, where N is the number of dolls. The doll sizes may separated by white spaces or newline.Input ends when N and K is 0.

There are multiple test cases.For each case the input contains two integers N (1<=50<=N) and K (1<=K<=25) in first line and N doll sizes (integers between 1 and 100000, inclusive) below, where N is the number of dolls. The doll sizes may separated by white spaces or newline.Input ends when N and K is 0.

5 2
1 2 1 2 4
0 0

2

Hint: you can sell two pairs at most, {(1,2),(1,2)} or {(1,2),(2,4)}.

#include<iostream>
using namespace std;
bool vis[60];
int num[60];
bool compare(int a,int b)
{
return a<b;
}
int main()
{
int n,k,sum,temp;
while(scanf("%d%d",&n,&k)!=EOF&&!(n==0&&k==0))
{
sum=0;
memset(vis,false,sizeof(vis));
for(int i=0;i!=n;i++)
{
scanf("%d",&num[i]);
vis[i]=true;
}
sort(num,num+n,compare);
for(int i=0;i<n;i++)
{
if(vis[i])//当前玩具未被出售
{
for(int j=i+1;j<n;j++)//寻找未被出售而且大小是当前玩具的k倍的玩具
{
if(vis[j]&&num[j]==k*num[i])
{
sum++;
vis[i]=vis[j]=false;
break;
}
}
}
}
cout<<sum<<endl;
}
return 0;
}