oj.uz

Submission #731711

# Submission time Handle Problem Language Result Execution time Memory
731711 2023-04-27T20:37:57 Z rainboy ASM (LMIO18_asm) C
9 / 100
 1 ms 492 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 if (y == 0) {
			printf("2\n");
			printf("multiply 0\n");
			printf("print\n");
		} else {
			printf("3\n");
			printf("multiply 0\n");
			printf("add %lld\n", y);
			printf("print\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:68:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%lld%s", &xx[i], yy[i]), mm[i] = strlen(yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 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 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 488 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 488 KB Output is correct
13 Correct 0 ms 484 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 17.0

# 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 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Incorrect 0 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 0 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Incorrect 0 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -