白駿12025いたずら鬼泳勲

1792 ワード
ps テキストリンク

BOJ 12025


目標:泳勲はいたずらっ子なので、喜賢のパスワードは1を6、6を1、または2を7に変更して2に変更します.この問題を解決するために、喜賢は暗号数列の1と6を1とし、2と7を2とする数字と、1と6を6と7とする数字の間で可能な場合を辞書順に並べ、そのうちk番目の数列の暗号を見つけることにした.崩壊に陥ったヒヒョンのパスワードを見つけよう
条件:K<=2^63-10<=パスワードの桁数<=60

ソリューション

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string input;
long long N, M = 1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> input >> N;
	for (int i = 0; i < input.length(); i++){
		if (input[i] == '1' || input[i] == '6'){
			input[i] = '1';
			M *= 2;
		}
		else if (input[i] == '2' || input[i] == '7'){
			input[i] = '2';
			M *= 2;
		}
	}	
	if (N > M || N < 0){
		cout << -1 << "\n";
	}
	else{
		N -= 1;
		for (int i = input.length()-1; i >= 0; i--){
			if (input[i] == '1'){
				if (N % 2) {
					input[i] = '6';
				}
				N /= 2;
			}
			else if (input[i] == '2'){
				if (N % 2) {
					input[i] = '7';
				}
				N /= 2;
			}
		}
		cout << input << "\n";
	}
	
	return 0;
}
k個のパスワードを見つけるために,可能なパスワード数列が1,2,6,7の個数がN個の場合は2^N個である.これはKをバイナリで表すことができ,容易に解決できる.たとえば、K=4の場合、数字は0000から1111、0から、0011が4番目のパスワードであることを示し、2、3文字目のみが6または7に変更して解決することができる.
JavaScriptのクラス
1つのmapにおける複数のkeyの方法および種々の遍歴方法の例