Pagini recente » Cod sursa (job #1364876) | Cod sursa (job #1544893) | Cod sursa (job #2813671) | Cod sursa (job #2079893) | Cod sursa (job #163500)
Cod sursa(job #163500)
#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;
}