2466.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2466 on 2007-04-16 at 11:08:47 */
#include <cstdio>

#include <cassert>

#include <algorithm>

using namespace std;

 

class ACMER {

public:

	char name[50];

	long long rp;

	void create() { scanf("%s %lld", name, &rp); }

};

 

long long best;

bool multi;

ACMER acm[16];

int n, k, set;

 

long long euler(long long);

 

int main()

{

	while(scanf("%d %d", &n, &k) == 2) {

		for(int i = 0; i < n; i++) acm[i].create();

		best = -1; multi = false;

		for(int i = 0; i < (1<<n); i++) {

			int cnt = 0;

			long long res = 0;

			for(int j = 0; j < n; j++)

				if(i&(1<<j)) { cnt++; res += acm[j].rp; }

			if(cnt != k) continue;

			long long eul = euler(res);

			assert(eul >= 0);

			if(eul > best) { best = eul; multi = false; set = i; }

			else if(eul == best) multi = true;

		}

		if(multi) printf("The solution doesn't work!\n");

		else {

			int peo = 0;

			for(int i = 0; i < n; i++)

				if(set&(1<<i)) {

					if(peo) printf(" ");

					printf("%s", acm[i].name);

					peo++;

				}

			printf("\n");

		}

	}

 

	return 0;

}



long long euler(long long n)

{

	if(n == 1) return 0;

	long long res = n;

	for(long long i = 2; i*i <= n; i++) {

		if(n%i == 0) res -= res/i;

		while(n%i == 0) n /= i;

	}

	if(n != 1) res -= res/n;

	return res;

}