oj.uz

Submission #67807

# Submission time Handle Problem Language Result Execution time Memory
67807 2018-08-15T10:09:05 Z osmanorhan Binary Subsequences (info1cup17_binary) C++17
100 / 100
 661 ms 652 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset

using namespace std;

typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,char> ic;
typedef pair<db,db> dd;
typedef pair<int,ii> iii;
typedef pair<ii,ii> i4;

const int maxn = 200020;
const int maxm = 1000020;
const int MOd = 998244353;

int main() {

    //freopen("asd.in","r",stdin);
    //freopen("output17.txt","w",stdout);
	
	int a;
	scanf("%d",&a);
	while( a-- ) {
		int k;
		scanf("%d",&k); k += 2;
		int ans = 0;
		int mini = 1e9, h = 0;
		for(int i=1;i<k-i;i++) {
			int x = i;
			int y = k-i;
			int step = 0;
			while( x > 0 && y > 0 ) {
				if( x > y ) step += x/y, x %= y;
				else step += y/x, y %= x;
			}
			if( x > y ) swap( x, y );
			if( y == 1 ) {
				ans++;
				if( step < mini ) {
					mini = step;
					h = i;
				}
			}
		}

		cout << ans+ans << endl;
		int x = h;
		int y = k-h;
		vector<int> v;
		while( x != y ) {
			if( x > y ) x -= y, v.pb( 1 );
			else y -= x, v.pb( 0 );
		}
		for(int i=v.size()-1;i>=0;i--) printf("%d ",v[i]); printf("\n");
	}

	return 0;
}

Compilation message

binary.cpp: In function 'int main()':
binary.cpp:79:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i=v.size()-1;i>=0;i--) printf("%d ",v[i]); printf("\n");
   ^~~
binary.cpp:79:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i=v.size()-1;i>=0;i--) printf("%d ",v[i]); printf("\n");
                                                      ^~~~~~
binary.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&a);
  ~~~~~^~~~~~~~~
binary.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k); k += 2;
   ~~~~~^~~~~~~~~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 392 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 484 KB Output is correct
2 Correct 58 ms 484 KB Output is correct
3 Correct 55 ms 624 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 624 KB Output is correct
2 Correct 661 ms 652 KB Output is correct
3 Correct 630 ms 652 KB Output is correct