Mike and Cellphone [Codeforces 361 : Div2 A]

問題

http://codeforces.com/contest/689/problem/A

123
456
789
 0

の並びの数字版とn個の押し順が与えられる。
この押し順を縦横にスライドして、まだ押せるなら"NO"押せないなら"YES"

考察

1. スライドできない場合は限られそう（実験するといい）
2. スライドできないのは、押した数字版の範囲が「4H×3W」か「3H×3W」のときだけ！

Hacked!!

3. 「3H×3W」でもスライドできるのあった

456    123
 8  ->  5
 0      8
上にスライドする

0が含まれるときはスライドできる

4. 「3H×3W」でスライドできるやつはまだある

123     456
 5   ->  8
 8       0
下にスライドする

7と9が含まれないときもスライドできる

実装

http://codeforces.com/contest/689/submission/18942724

int n;
string s;
int x[10] = { 1, 0, 1, 2, 0, 1, 2, 0, 1, 2 };
int y[10] = { 3, 0, 0, 0, 1, 1, 1, 2, 2, 2 };
//-----------------------------------------------------------------
string solve() {
	int lx = x[s[0] - '0'];
	int rx = x[s[0] - '0'];
	int ty = y[s[0] - '0'];
	int by = y[s[0] - '0'];

	rep(i, 1, n) {
		lx = min(lx, x[s[i] - '0']);
		rx = max(rx, x[s[i] - '0']);
		ty = min(ty, y[s[i] - '0']);
		by = max(by, y[s[i] - '0']);
	}

	int w = rx - lx + 1;
	int h = by - ty + 1;

	if (4 == h) return "YES";
	if (w == 3 && h == 3) {
		rep(i, 0, n) if (s[i] == '0') return "NO";

		bool ok = false;
		rep(i, 0, n) if (s[i] == '7' || s[i] == '9') ok = true;
		if (ok) return "YES";
	}

	return "NO";
}
//-----------------------------------------------------------------
int main() {
	scanf("%d", &n);
	cin >> s;
	cout << solve() << endl;
}