Submission #731714

#	Time	Username	Problem	Language	Result	Execution time	Memory
731714		rainboy	ASM (LMIO18_asm)	C11	100 / 100	66 ms	768 KiB

asm

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	50
#define M	18
#define K	1212
#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) {
	int h;

	pp[l] = m - s;
	for (h = 0; h <= l; h++)
		ppp[m][kk[m]][h] = pp[l - h];
	ll[m][kk[m]] = l + 1;
	kk[m]++;
	for (p = min(p, m - 1 - 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] = atol(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] = atol(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 || aa[g] == 0 && g + 1 < l || 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 || aa[g] > 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 (aa[g] > 0 && 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 (stderr)

asm.c: In function 'main':
asm.c:94:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |      if (aa[g] < 0 || aa[g] == 0 && g + 1 < l || aa[g] > 0 && xx[0] > zz0[g] / aa[g]) {
      |                       ~~~~~~~~~~~^~~~~~~~~~~~
asm.c:94:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |      if (aa[g] < 0 || aa[g] == 0 && g + 1 < l || aa[g] > 0 && xx[0] > zz0[g] / aa[g]) {
      |                                                  ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
asm.c:103:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  103 |      if (aa[g] % aa[g - 1] != 0 || aa[g] > 0 && bb[g - 1] > bb[g] / (aa[g] / aa[g - 1])) {
      |                                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
asm.c:43:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
asm.c:45:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%lld%lld", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~
asm.c:66:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%lld%s", &xx[i], yy[i]), mm[i] = strlen(yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 53 / 53
• Subtask 4: 21 / 21