CodeThanksFestival 2017

E - Coin Authentication (400)

E - Coin Authentication

概要

インタラクティブ問題。
個の袋の中にコインが枚入っている。
コインの重さはgの5種類であり、同じ袋の中には同じ種類のコインが入っている。
上記のうちgのコインが本物のコインであり、gのコインが偽物のコインであるとする。
「各袋から好きな枚数ずつ取り出して合計の重さをはかる」操作を高々10回行い、
それぞれの袋に含まれているコインが本物であるか偽物であるかを特定せよ。

制約

方針

5袋ずつから枚ずつ取り出して重さを測る。
全体の重さから5袋それぞれのコインの種類を特定することが可能。

感想

コインの重さが5種類なので重さを5進数に対応させればよい。
そのため、取り出す枚数は枚でよい。

解答

Submission #3915208 - CODE THANKS FESTIVAL 2017(Parallel)

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int max_n = 53;
int n;
int m;
int ans[max_n];
 
void setAns(int x, ll ret){
	int y = 5 * x;
	rep(i, 5){
		int u = ret % 10;
		// cout << i << " " << ret << endl;
		if(u == 9 || u == 1){
			ans[y] = 1;
		}else if(u == 0 || u == 2 || u == 8){
			ans[y] = 0;
		}else{
			// cout << "error:" << y << " " << ret << endl; 
		}
		ret /= 10;
		if(u % 10 <= 2) ret--;
		y++;
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> n;
	m = (n % 5 == 0 ? n / 5: n / 5 + 1);
	rep(i, m){
		cout << "?";
		rep(j, n){
			cout << " ";
			if(5 * i <= j && j < 5 * (i+1) ){
				cout << pow(10, j % 5);
			}else{
				cout << 0;
			}
		}
		cout << endl;
 
		ll ret;
		cin >> ret;
 
		setAns(i, ret);
	}
 
	cout << "!";
	rep(i, n) cout << " " << ans[i];
	cout << endl;
}