Cod sursa(job #163500)

Utilizator blasterzMircea Dima blasterz Data 22 martie 2008 14:06:20
Problema Vanatoare Scor 5
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasele 11-12 Marime 1.54 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

inline int gcd(int a, int b, int &x, int &y)
{
    if(b==0)
    {
	x=1; y=0; return a;
    }
    int x0, y0,d;
    d=gcd(b, a%b, x0, y0);
    x=y0;
    y=x0-(a/b)*y0;
    return d;
}

unsigned int T;
int n;
int a[32],v[32];
int K;
int x[32];
int q[32][32];

inline void afis()
{
    int i,j,s;
    for(i=1;i<=n;++i) q[i][0]=0;
    for(i=1;i<=n;++i)
	q[x[i]][++q[x[i]][0]]=i;
    
    int nr=0;
    int sol[32],ns=0;
    for(i=1;i<=K;++i)
    {

	if(q[i][0]==0)continue;
	if(q[i][0]==1) {++nr;int r=a[q[i][1]], t=v[q[i][1]]; if(r+t<=T) sol[++ns]=r+t;else sol[++ns]=a[q[i][1]];continue;}
	int d, x1, y1;
	int X, Y;
	int aa, bb, cc;
	aa=v[q[i][1]];
	bb=-v[q[i][2]];
	cc=a[q[i][2]]-a[q[i][1]];

	d=gcd(aa,bb, x1, y1);

	if(cc%d) continue;
	X=x1*(cc/d);
	Y=y1*(cc/d);

	s=a[q[i][1]]+X*v[q[i][1]];
	if(s>T) return;
	for(j=1;j<=q[i][0];++j)
	    if(a[q[i][1]]+X*v[q[i][1]]!=s) return;

//	printf("%d\n", s);
	++nr;
	sol[++ns]=s;
    }

    sort(sol+1,sol+nr+1);
   // printf("da!!! %d\n", K);
   // printf("%d\n", s);
    printf("%d\n", nr);

    for(i=1;i<=nr;++i)printf("%d ", sol[i]);
    printf("\n");
    exit(0);
	


    



}

inline void back(int k)
{
    if(k==n+1) afis();
    else
    {
	for(int i=1;i<=K;++i)
	{
	    x[k]=i;
	    back(k+1);
	}
    }
}

int main()
{
    freopen("vanatoare.in","r",stdin);
    freopen("vanatoare.out","w",stdout);
    scanf("%d %d\n", &n, &T);
    int i;
    for(i=1;i<=n;++i) scanf("%d %d\n", a+i, v+i);
    for(K=1;K<=n;++K) back(1);


    return 0;
}