結果

問題 No.2593 Reorder and Mod 120
コンテスト
ユーザー daiota
提出日時 2023-12-21 11:33:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,823 bytes
コンパイル時間 2,132 ms
コンパイル使用メモリ 190,496 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-27 10:57:06
合計ジャッジ時間 3,194 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define REP(i,n) for(int i=0;i<int(n);i++)

int n[12];
int f(int x){
	if(x<10) return x;
	return f(x/10)+x%10;;
}

int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	int i,j;

	int N;
	string S;
	cin >> N >> S;

	if(N==1){
		cout << 1 << endl;
		return 0;
	}
	if(N==2){
		if(S[0]==S[1]) cout << 1 << endl;
		else cout << 2 << endl;
		return 0;
	}

	map<int,int> b;
	if(N==3){

		sort(S.begin(),S.end());
		do{

		  int x=stoi(S);
		  b[x%120]++;

		}while(next_permutation(S.begin(),S.end()));

		cout << (int)b.size() << endl;
		return 0;
	}

	int T=0;
	REP(i,N){
		int a=S[i]-'0';
		T+=a;
		for(j=1;j<=9;j++){
			if(j==a){
				n[j]++;
				break;
			}
		}
	}


      queue<string> q;

      for(i=1;i<=9;i++) if(n[i]>0){
    	  q.push(to_string(i));
    	  n[i]*=-1;
      }

      REP(i,10) n[i]*=-1;


      vector<int> u;

      while(!q.empty()){

      string s=q.front();
      q.pop();
      int m=s.size();

      if(m==4){
    	  vector<int> c(10,0);
    	  REP(i,4) c[s[i]-'0']++;

    	  bool f=true;
    	  for(i=1;i<=9;i++){
    		  if(n[i]<c[i]){
    			  f=false;
    			  break;
    		  }
    	  }

    	  if(f) u.push_back(stoi(s));
      }

      else if(m<4){
    	  for(i=1;i<=9;i++) if(n[i]>0){
    		  string t=s+to_string(i);
    		  q.push(t);
    	  }
      }

      }

  	int p=u.size();

  	for(i=0;i<120;i++){
  		REP(j,p){
  			bool g=true;
  			int x=u[j]-i;

  			if(x%10!=0 && x%10!=5){
  				g=false;
  				continue;
  			}

  			if((x%1000)%8!=0){
  				g=false;
  				continue;
  			}

  			if((T-f(u[j])+f(x))%3!=0){
 				g=false;
  				continue;
  			}

  			if(g){
  			    b[i]++;
  				break;
  			}

  		}


  	}


  	cout << (int)b.size() << endl;




	return 0;
}
0