SRM 358 250pt : BrokenButtons

keyword

BruteForce　C++

問題概要

いくつかボタンが壊れたリモコンがある。そのリモコンの壊れてないボタンとinc, decを最低何度押したら目的の値を出せるか求める問題。

解法

探す値が大きくないので全探索する。

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

bool out[0x100];

struct BrokenButtons {

	int minPresses(int page, vector <int> broken) {
		int ret = abs(100-page);
		for(int i=0; i<(int)broken.size(); i++){
			out[broken[i] + '0'] = true;
		}
		for(int i=0; i<=1000000; i++){
			char buf[12];
			sprintf(buf, "%d", i);
			bool ok = true;
			for(int j=0; buf[j]; j++)if(out[(int)buf[j]]){
				ok = false;
			}
			if(ok){
				ret = min(ret, abs(page - i) + (int)strlen(buf));
			}
		}
		return ret;
	}

};