アルゴリズムのメモ
2009.07.09 22:40 ACM/ICPC 2009
#include #include using namespace std; #define MAX 12 int N, L[26], R[26], LT[26][10], RT[26][10]; string S[MAX]; int num[26]; bool used[10]; int cnt, MDL[26], MDR[26]; void setValue( string str, int a[] ){ for ( int i = str.size()-1, p = 1; i >= 0; i--, p *= 10 ){ a[str[i] - 'A'] += p; } } bool zeroCheck(){ for ( int i = 0; i < N; i++ ){ if ( S[i].size() > 1 && num[S[i][0]-'A'] == 0 ) return false; } return true; } void rec( int cur, int left, int right ){ if ( cur == 26 ){ if ( left == right && zeroCheck() ) cnt++; return; } if ( left + MDL[cur] < right ) return; if ( right + MDR[cur] < left ) return; if ( L[cur] + R[cur] == 0 ){ rec( cur+1, left, right ); return; } for ( int d = 9; d >= 0; d-- ){ if ( used[d] ) continue; used[d] = true; num[cur] = d; rec( cur+1, left + L[cur]*d, right + R[cur]*d ); used[d] = false; } } void makeMD(){ int md = 0; MDL[25] = 9*(L[25]); MDR[25] = 9*(R[25]); for ( int i = 24; i >= 0; i-- ){ MDL[i] = MDL[i+1] + (L[i])*9; MDR[i] = MDR[i+1] + (R[i])*9; } } main(){ while ( cin >> N && N ){ for ( int i = 0; i < 26; i++ ) { L[i] = R[i] = 0;} for ( int i = 0; i < N; i++ ) { cin >> S[i]; if ( i == N-1 ) setValue( S[i], R ); else setValue( S[i], L ); } makeMD(); for ( int i = 0; i <= 9; i++ ) used[i] = false; cnt = 0; rec(0, 0, 0); cout << cnt << endl; } }
テーマ : プログラミング - ジャンル : コンピュータ
| コメント(0) | トラックバック(0) | ↑ページトップ |
管理人にのみ表示
↑ページトップ
この記事にトラックバックする(FC2ブログユーザー)
Footmark
このブログをリンクに追加する Powered By FC2 ブログ