Google Code Jam 2019 Round 1A : B. Golf Gophers

なんか問題が読みにくかった。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104f1a

問題

18個の歯車があり、それぞれ2～18個の歯の個数を任意に指定できる。
一晩経つと、全歯車で合計歯N個分歯車が回転する。
ただしどの歯車は歯何個分回転するかはランダムで、毎回変わる。

Nは10^6以下の正整数であることはわかっているが、正確な値がわかっていない。
歯の数を指定すると、一晩後の回転量がわかる場合、最大7回まで歯の数を指定し、Nを求めよ。

解法

全歯車において葉の数を同じ値pにすれば、一晩後の返り値の総和を取ることでN % pが求まる。
よって、pとして(2^4),(3^2),5,7,11,13,17と試せば、あとは中国人剰余定理でNが求まる。
実際には、Nの範囲が小さいのでCRTを用いずとも1～10^6を総当たりすればよい。

int N,M;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	vector<int> P={16,9,5,7,11,13,17};
	vector<int> R;
	FORR(p,P) {
		FOR(i,18) {
			cout<<p;
			if(i<17) cout<<" ";
		}
		cout<<endl;
		int t=0;
		FOR(i,18) {
			cin>>x;
			t+=x;
		}
		
		R.push_back(t%p);
	}
	
	for(i=1;i<=M;i++) {
		FOR(j,7) if(i%P[j]!=R[j]) break;
		
		if(j==7) {
			cout<<i<<endl;
			cin>>j;
			return;
		}
	}
	assert(0);
	
	
}

void init() {
	cin>>N>>M;
}

まとめ

N,Mが初回しか与えられない、ということに気付かず大量に時間を溶かした。