kmjp's blog

競技プログラミング参加記です

yukicoder : No.1732 ~サンプルはちゃんと見て!~ 16進数と8進数(2)

なるほど…。
https://yukicoder.me/problems/no/1732

問題

整数Nが与えられる。
A~Fだけで構成されるN桁の16進数のうち、8進数表記したときに1~7の登場回数が等しいものを1つ示せ。

解法

総当たり及びサンプルケースから、16進数で5桁・10桁・21桁のケースは1つずつ求められる。
このうち21桁の場合は8進数でちょうど28桁なので、(N-21)桁で条件を満たせるなら、後ろにこの21桁を追加すれば、N桁でも条件を満たせる。

ということで、以下の形で表現できる16進数が条件を満たす。

  • 21k
  • 5+21k
  • 10+21k
string S[3]={
	"",
	"BBCCCFACAC",
	"ACCACCCCCCCCABACAAFFE",
};

int T,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	string V="1234567";
	do {
		x=strtol(V.c_str(),NULL,8);
		stringstream ss;
		ss<<std::hex<<x;
		s=ss.str();
		
		int ok=1;
		FORR(c,s) {
			if(c<'a'||c>'f') ok=0;
			c+='A'-'a';
		}
		if(ok) S[0]=s;
	} while(next_permutation(ALL(V)));
	
	cin>>T;
	while(T--) {
		cin>>N;
		string R;
		
		if(N%21==5) {
			R=S[0];
			FOR(i,N/21) R+=S[2];
		}
		if(N%21==10) {
			R=S[1];
			FOR(i,N/21) R+=S[2];
		}
		if(N%21==0) {
			FOR(i,N/21) R+=S[2];
		}
		
		if(R=="") R="-1";
		cout<<R<<endl;
	}
	
}

まとめ

タイトルは何なんだろう。