oj.uz

Submission #916330

# Submission time Handle Problem Language Result Execution time Memory
916330 2024-01-25T16:49:34 Z rainboy Binary Subsequences (info1cup17_binary) C
82 / 100
 900 ms 416 KB 
#include <stdio.h>

int min(int a, int b) { return a < b ? a : b; }

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int length(int a, int b) {
	return b == 0 ? -1 : length(b, a % b) + 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_, b, k, l, l_;

		scanf("%d", &n), n += 2;
		k = 0, l_ = n, a_ = 0;
		for (a = 1; a < n; a++) {
			b = n - a;
			if (gcd(a, b) == 1) {
				k++;
				l = length(a, b);
				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:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
binary.c:27:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d", &n), n += 2;
      |   ^~~~~~~~~~~~~~~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 344 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB Output is correct
2 Correct 87 ms 416 KB Output is correct
3 Correct 81 ms 400 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 344 KB Output is correct
2 Execution timed out 1051 ms 396 KB Time limit exceeded
3 Halted 0 ms 0 KB -