Submission #916330

#	Time	Username	Problem	Language	Result	Execution time	Memory
916330		rainboy	Binary Subsequences (info1cup17_binary)	C11	82 / 100	1051 ms	416 KiB

binary

#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 (stderr)

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 / 43
• Subtask 2: 39 / 39
• Subtask 3: 0 / 18