首页 > 代码库 > CodeForces 42C Safe cracking 规律题

CodeForces 42C Safe cracking 规律题

题目链接:点击打开链接

3个数为一组,找最大的一个数让它降低,则显然是有解的,分类讨论一下就可以

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int n, k;
int a[4];
vector<pair<int,int> >ans;
int maxpos(){
	int pos = 0;
	for(int i = 1; i < 4; i++)
		if(a[pos]<a[i])pos = i;
	return pos;
}
void chu(int pos){
	a[pos] >>= 1; a[(pos+1)%4] >>= 1;
	ans.push_back(pair<int,int>(0, pos));
}
void ADD(int pos){
	a[pos] ++; a[(pos+1)%4] ++;
	ans.push_back(pair<int,int>(1, pos));
}
int main(){
	while(cin>>a[0]>>a[1]>>a[2]>>a[3]){
		ans.clear();
		int pos, siz = 0;
		while(1){
			pos = maxpos();
			if(a[pos]==1)return true;
			int l = pos-1; if(l<0)l = 3;
			int r = pos+1; if(r>3)r = 0;
			if(a[pos]&1){
				if(a[l]&1)
				{
					ADD(l);
					chu(l);
				}
				else if(a[r]&1)
				{
					ADD(pos);
					chu(pos);
				}
				else {
					ADD(pos);
					chu(l);
				}
			}
			else {
				if((a[l]&1)==0)
				{
					chu(l);
				}
				else if((a[r]&1)==0)
				{
					chu(pos);
				}
				else {
					ADD(l); ADD(pos);
					chu(l);
				}
			}
		}
		for(int i = 0; i < ans.size(); i++)
			printf("%c%d\n", ans[i].first?‘+‘:‘/‘, ans[i].second+1);
	}
	return 0;
}


CodeForces 42C Safe cracking 规律题