oj.uz

Submission #916331

# Submission time Handle Problem Language Result Execution time Memory
916331 2024-01-25T16:53:01 Z rainboy Binary Subsequences (info1cup17_binary) C
100 / 100
 643 ms 396 KB 
#include <stdio.h>

#define INF	0x3f3f3f3f

int length(int a, int b) {
	int l;

	if (b == 0)
		return a == 1 ? -1 : INF;
	l = length(b, a % b);
	return l == INF ? INF : l + a / b;
}

void print(int a, int b) {
	if (a < b)
		print(a, b - a), printf("0 ");
	else if (a > b)
		print(a - b, b), printf("1 ");
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		int n, a, a_, k, l, l_;

		scanf("%d", &n), n += 2;
		k = 0, l_ = n, a_ = 0;
		for (a = 1; a < n; a++) {
			l = length(a, n - a);
			if (l != INF) {
				k++;
				if (l_ > l)
					l_ = l, a_ = a;
			}
		}
		printf("%d\n", k);
		print(a_, n - a_), printf("\n");
	}
	return 0;
}

Compilation message

binary.c: In function 'main':
binary.c:24:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
binary.c:28:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d", &n), n += 2;
      |   ^~~~~~~~~~~~~~~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 356 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 348 KB Output is correct
2 Correct 54 ms 348 KB Output is correct
3 Correct 51 ms 348 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 396 KB Output is correct
2 Correct 643 ms 392 KB Output is correct
3 Correct 622 ms 396 KB Output is correct