Cod sursa(job #176870)

Utilizator alextheroTandrau Alexandru alexthero Data 11 aprilie 2008 20:42:25
Problema Vanatoare Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

#define cmax 100000
#define inf 0x3f3f3f3f

using namespace std;
typedef pair<int, int> ii;

int n, t, cm;
ii a[cmax];
int d[cmax], prev[cmax];

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int gcm(int a, int b)
{
	long long aux = (long long)a * b;
	aux /= (long long)gcd(a, b);
	return (int)aux;
}

ii calc(ii a, ii b)
{
	int c1 = a.first, p1 = a.second;
	int c2 = b.first, p2 = b.second;

	int maxx = c1 + 2 * gcm(p1, p2);

	while(c1 != c2)
	{
		if(c1 > maxx) return ii(inf, inf);

		if(c1 < c2) 
		{
			c1 = c2 - (c2 - c1) % p1;
			if(c1 < c2) c1 += p1;
		}
		else if(c2 < c1)
		{
			c2 = c1 - (c1 - c2) % p2;
			if(c2 < c1) c2 += p2;
		}

		if(max(c1, c2) > t) return ii(inf, inf);
		if(c1 == c2) return ii(c1, gcm(p1, p2));
	}

	return ii(inf, inf);
}

void back(int config, int nconf, int p)
{
	if(p == n) 
	{
		if(d[config] > d[nconf] + d[config ^ nconf])
		{
			d[config] = d[nconf] + d[config ^ nconf];
			prev[config] = nconf;
		}
	}
	else
	{

		if(config & (1 << p)) back(config, nconf * 2 + 1, p + 1);
		back(config, nconf * 2, p + 1);
	}
}

void reconst(int x)
{
	if(d[x] == 1) printf("%d ", a[x].first);
	else 
	{
		reconst(prev[x]);
		reconst(x ^ prev[x]);
	}
}
int main()
{
	freopen("vanatoare.in", "r", stdin);
	freopen("vanatoare.out", "w", stdout);
	
	scanf("%d%d", &n, &t); cm = (1 << n) - 1;
	for(int i = 0; i < cmax; i++) a[i] = ii(inf, inf);
	for(int i = 0; i < n; i++) scanf("%d%d", &a[1 << i].first, &a[1 << i].second);

	for(int i = 0; i <= cm; i++)
		if(a[i].first != inf && a[i].second != inf)
			for(int j = 0; j < n; j++)
				if((!(i & (1 << j))) && (a[1 << j].first != inf)) 
					a[i + (1 << j)] = calc(a[i], a[1 << j]);
	
	for(int i = 0; i <= cm; i++)
		if(a[i].first != inf) d[i] = 1;
		else d[i] = inf;

	for(int i = 0; i <= cm; i++) back(i, 0, 0);
	printf("%d\n", d[cm]);

	reconst(cm);
	return 0;
}