AOJ 2157: Dial Lock

解法

SRM607Med CombinationLockDiv1と同じように考えると、直ぐ解ける。
まず、to - from を計算して、回転数を求めて、差分を求めることができる。
「(複数の)ダイアルを1回回す」 ⇔ 「差分を任意に2つ選び、それぞれ +x, -x する」
であるから、差分を総和が0になるようなグループに分けて、そのグループ数だけ回転数を減らせる。
全順列を試すと、グループ数の最大値が求められる。

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

int main(){
	int n;
	while(cin>>n, n){
		string s, t;
		cin>>s>>t;
		vector<int> d(n+2, 0);
		for(int i = 0; i < n; i++) d[i+1] = s[i]-t[i];
		vector<int> x;
		for(int i = 0; i <= n; i++){
			int a = (d[i+1]-d[i]+90)%10;
			if(a) x.push_back(a);
		}
		int m = x.size(), res = m;
		if(m>0){
			sort(x.begin(), x.end());
			do{
				int sum = 0, c = 0;
				for(int i = 0; i < m; i++){
					sum += x[i];
					if(sum>=10) sum-=10;
					if(sum==0) c++;
				}
				res = min(res, m-c);
			}while(next_permutation(x.begin()+1, x.end()));
		}
		cout<<res<<endl;
	}
	return 0;
}