| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 731710 |
2023-04-27T20:35:55 Z |
rainboy |
ASM (LMIO18_asm) |
C |
|
1 ms |
468 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 50
#define M 18
#define K 385 /* https://en.wikipedia.org/wiki/Partition_(number_theory) */
#define A 1000000000000000000LL
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int ppp[M + 1][K][M], ll[M + 1][K], kk[M + 1], pp[M];
void brute(int m, int s, int p, int l) {
if (s == m) {
int h;
for (h = 0; h < l; h++)
ppp[m][kk[m]][h] = pp[l - 1 - h];
ll[m][kk[m]] = l;
kk[m]++;
return;
}
for (p = min(p, m - s); p > 0; p--)
pp[l] = p, brute(m, s + p, p, l + 1);
}
void init() {
int m;
for (m = 1; m <= M; m++)
brute(m, 0, m, 0);
}
int main() {
static long long xx[N], zz0[M], zz1[M], aa[M], bb[M], aa_[M], bb_[M];
static char yy[N][M + 1];
static int mm[N], dd[M];
int n, m0, m1, l, l_, k, g, h0, h1, i, j, j_, cnt, cnt_, good;
char c;
long long x, y, z;
init();
scanf("%d", &n);
if (n == 1) {
scanf("%lld%lld", &x, &y);
if (x == y) {
printf("1\n");
printf("print\n");
} else if (x < y) {
printf("2\n");
printf("add %lld\n", y - x);
printf("print\n");
} else
printf("-1\n");
return 0;
}
for (i = 0; i < n; i++)
scanf("%lld%s", &xx[i], yy[i]), mm[i] = strlen(yy[i]);
m0 = mm[0], m1 = mm[1];
cnt_ = INF;
for (h0 = 0; h0 < kk[m0]; h0++)
for (h1 = 0; h1 < kk[m1]; h1++)
if (ll[m0][h0] == ll[m1][h1]) {
l = ll[m0][h0];
for (g = 0, j = 0; g < l; g++, j = j_) {
j_ = j + ppp[m0][h0][g];
c = yy[0][j_];
yy[0][j_] = 0;
zz0[g] = atoi(yy[0] + j);
yy[0][j_] = c;
}
for (g = 0, j = 0; g < l; g++, j = j_) {
j_ = j + ppp[m1][h1][g];
c = yy[1][j_];
yy[1][j_] = 0;
zz1[g] = atoi(yy[1] + j);
yy[1][j_] = c;
}
good = 1;
for (g = 0; g < l; g++) {
if ((zz1[g] - zz0[g]) % (xx[1] - xx[0]) != 0) {
good = 0;
break;
}
aa[g] = (zz1[g] - zz0[g]) / (xx[1] - xx[0]);
if (aa[g] <= 0 || xx[0] > zz0[g] / aa[g]) {
good = 0;
break;
}
bb[g] = zz0[g] - aa[g] * xx[0];
}
if (!good)
continue;
for (g = 1; g < l; g++)
if (aa[g] % aa[g - 1] != 0 || bb[g - 1] > bb[g] / (aa[g] / aa[g - 1])) {
good = 0;
break;
}
if (!good)
continue;
good = 1;
for (i = 2; i < n; i++) {
for (g = 0, j = 0; g < l; g++) {
if (xx[i] > (A - 1 - bb[g]) / aa[g]) {
good = 0;
goto out;
}
z = xx[i] * aa[g] + bb[g];
k = 0;
if (z == 0)
dd[k++] = 0;
else {
while (z > 0)
dd[k++] = z % 10, z /= 10;
while (k--) {
if (j == mm[i] || yy[i][j] != dd[k] + '0') {
good = 0;
goto out;
}
j++;
}
}
}
if (j != mm[i]) {
good = 0;
break;
}
}
out:
if (!good)
continue;
cnt = l;
for (g = 0; g < l; g++) {
if (aa[g] != (g == 0 ? 1 : aa[g - 1]))
cnt++;
if (bb[g] != (g == 0 ? 0 : bb[g - 1] * (aa[g] / aa[g - 1])))
cnt++;
}
if (cnt_ > cnt) {
cnt_ = cnt, l_ = l;
memcpy(aa_, aa, l * sizeof *aa), memcpy(bb_, bb, l * sizeof *bb);
}
}
if (cnt_ == INF) {
printf("-1\n");
return 0;
}
printf("%d\n", cnt_);
for (g = 0; g < l_; g++) {
if (aa_[g] != (g == 0 ? 1 : aa_[g - 1]))
printf("multiply %lld\n", aa_[g] / (g == 0 ? 1 : aa_[g - 1]));
if (bb_[g] != (g == 0 ? 0 : bb_[g - 1] * (aa_[g] / aa_[g - 1])))
printf("add %lld\n", g == 0 ? bb_[g] : bb_[g] - bb_[g - 1] * (aa_[g] / aa_[g - 1]));
printf("print\n");
}
return 0;
}
Compilation message
asm.c: In function 'main':
asm.c:45:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
asm.c:47:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%lld%lld", &x, &y);
| ^~~~~~~~~~~~~~~~~~~~~~~~~
asm.c:60:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%lld%s", &xx[i], yy[i]), mm[i] = strlen(yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
