Pagini recente » Cod sursa (job #3195296) | Rezultatele filtrării | Cod sursa (job #1997906)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("vanatoare.in"); ofstream fout ("vanatoare.out");
typedef long long i64;
const int nmax = 16;
const int inf = 1 << 30;
struct str {
i64 a; int b;
} v[nmax + 1];
str c[(1 << nmax)];
int ok[(1 << nmax)];
int d[(1 << nmax)], vine[(1 << nmax)];
int m;
int cn[nmax + 1];
int nrst;
int st[(1 << nmax)];
i64 gcd (i64 a, i64 b) {
while (b > 0) {
i64 r = a % b;
a = b;
b = r;
}
return a;
}
void bck (int stn, int pos) {
if (stn != 0) st[ nrst ++ ] = stn;
for (int i = pos; i < m; ++ i) {
bck(stn + (1 << cn[ i ]), i + 1);
}
}
void eeuclid (i64 a, i64 b, i64 &x, i64 &y, i64 &sol) {
if (b == 0) {
x = 1;
y = 0;
sol = a;
return ;
}
i64 cat = a / b;
eeuclid(b, a % b, x, y, sol);
i64 xx, yy;
xx = y;
yy = x - cat * xx;
x = xx, y = yy;
}
int main() {
int n, t;
fin >> n >> t;
for (int i = 0; i < n; ++ i) {
fin >> v[ i ].b >> v[ i ].a;
c[1 << i] = v[ i ];
ok[1 << i] = v[ i ].b;
}
for (int i = 1; i < (1 << n); ++ i) {
int u = 0;
for (int j = 0; j < n; ++ j) {
if (i & (1 << j)) {
u = j; break;
}
}
int j = i - (1 << u);
if (j == 0) continue;
ok[ i ] = -1;
if (ok[ j ] == -1) continue;
if (c[ j ].a > t) {
if (c[ j ].b % v[ u ].a == v[ u ].b) {
ok[ i ] = c[ j ].b;
}
c[ i ] = c[ j ];
} else {
i64 D = gcd(c[ j ].a, v[ u ].a);
i64 p, q, ans, ct = v[ u ].b - c[ j ].b;
eeuclid(c[ j ].a, v[ u ].a, p, q, ans);
if (ct % ans == 0) {
p *= (ct / ans);
q *= (ct / ans);
c[ i ].a = 1LL * c[ j ].a * v[ u ].a / D;
i64 loc = c[ j ].a * p + c[ j ].b;
loc %= c[ i ].a;
if (loc < 0) loc += c[ i ].a;
if (loc <= t) {
ok[ i ] = loc;
c[ i ].b = loc;
}
}
}
}
d[ 0 ] = 0;
for (int i = 1; i < (1 << n); ++ i) {
m = 0;
for (int j = 0; j < n; ++ j) {
if (i & (1 << j))
cn[ m ++ ] = j;
}
nrst = 0;
bck(0, 0);
d[ i ] = inf;
for (int w = 0; w < nrst; ++ w) {
int j = st[ w ];
if (ok[ j ] != -1 && d[i - j] + 1 < d[ i ]) {
d[ i ] = d[i - j] + 1;
vine[ i ] = i - j;
}
}
}
fout << d[(1 << n) - 1] << "\n";
int stn = (1 << n) - 1;
while (stn != 0) {
fout << ok[stn - vine[stn]] << " ";
stn = vine[ stn ];
}
fout << "\n";
fin.close();
fout.close();
return 0;
}