質問する

に答える

Nは最大100000まで入力できるので、すべての場合、数量にナビゲートするとタイムアウトが発生します.

これは

ハトの巣の原理に関する問題であり,MBTIの種類が16個あり,Nが32より大きい場合,MBTI入力から遠ざかるためにも3つの繰り返しが必要であり,32より大きい場合,答えは必ず0である.Nが32未満の場合にのみ、この事実を使用してすべての場合の数字を検索できます.そうしないと、0が出力されます.
注意:タイムアウトエラーが発生したため、ずっと大変でした.タイムアウトエラーは時間の複雑さのために発生しますが、入力を受け付けずに待機している場合もあります.この問題に対しては,32より大きいN個のMBTIを全て入力して判断してこそ,入力によるタイムアウトを回避することができる.

タイムアウトしたら、入力が届いたかどうかを確認するのに慣れています.

コード1

//난이도 : 실버1
//시작 : 18:10
//끝 :
#include <iostream>
#include <vector>

using namespace std;

//MBTI를 숫자로 바꾸는 함수
vector<int> change_num(string tmp) {
	vector<int> num_mbti;
	if (tmp[0] == 'E') {
		num_mbti.push_back(1);
	}
	else {
		num_mbti.push_back(2);
	}
	if (tmp[1] == 'N') {
		num_mbti.push_back(1);
	}
	else {
		num_mbti.push_back(2);
	}
	if (tmp[2] == 'F') {
		num_mbti.push_back(1);
	}
	else {
		num_mbti.push_back(2);
	}
	if (tmp[3] == 'J') {
		num_mbti.push_back(1);
	}
	else {
		num_mbti.push_back(2);
	}

	return num_mbti;
}

//3개의 MBTI의 거리를 출력하는 함수
int get_distance(vector<vector<int>> mbti_3) {
	int distance = 0;
	for (int i = 0; i < 4; i++) {
		distance += abs(mbti_3[0][i] - mbti_3[1][i]);
	}
	for (int i = 0; i < 4; i++) {
		distance += abs(mbti_3[1][i] - mbti_3[2][i]);
	}
	for (int i = 0; i < 4; i++) {
		distance += abs(mbti_3[0][i] - mbti_3[2][i]);
	}
	return distance;
}

// 경우의 수에 따라 거리 측정하는 함수
int solve(vector<vector<int>> mbti) {
	int min_distance = 100;
	for (int i = 0; i < mbti.size() - 2; i++) {
		for (int j = i + 1; j < mbti.size() - 1; j++) {
			for (int k = j + 1; k < mbti.size(); k++) {
				vector<vector<int>> mbti_3;
				mbti_3.push_back(mbti[i]);
				mbti_3.push_back(mbti[j]);
				mbti_3.push_back(mbti[k]);
				int distance = get_distance(mbti_3);
				if (min_distance > distance) { //최소값 찾기
					min_distance = distance;
				}
			}
		}
	}
	return min_distance;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int N;
		cin >> N;
		vector<vector<int>> mbti;
		for (int j = 0; j < N; j++) { //MBTI 입력 받기
			string tmp;
			cin >> tmp;
			mbti.push_back(change_num(tmp));
		}
		if (N >= 33) { //33개이상인 경우 반드시 거리가 0이다. MBTI의 종류가 16개이기 때문에 최대한 멀게 하려고 해도 중복되는 3개가 존재하기 때문이다.
			cout << 0 << '\n';
		}
		else { //32개 이하인 경우 최소 거리 측정
			int min_distance = solve(mbti);
			cout << min_distance << '\n';
		}
		
	}

	return 0;
}

コード2

//난이도 : 실버1
//시작 : 18:10
//끝 : 
#include <iostream>
#include <vector>

using namespace std;

//두 MBTI의 거리를 출력하는 함수
int get_distance(string a, string b) {
	int distance = 0;
	for (int i = 0; i < 4; i++) {
		if (a[i] != b[i]) { //문자가 다를경우 거리 +1
			distance += 1;
		}
	}
	return distance;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		vector<string> str;
		int N;
		cin >> N;
		for (int j = 0; j < N; j++) { //MBTI를 입력 받는다.
			string tmp;
			cin >> tmp;
			str.push_back(tmp);
		}
		if (N > 32) { //받은 MBTI개수가 32개를 넘는 경우 아무리 거리를 멀리 하려고 해도 MBTI는 16 종류이기 때문에 반드시 3개가 중복되는 것이 발생한다.
			//이 때는 거리가 무조건 0이기 때문에 거리를 측정할 필요가 없다.
			cout << 0 << '\n';
		}
		else { //32개 이하이면 다양한 거리가 나올 수 있기 때문에 최소 거리를 직접 계산한다.
			int min_distance = 100;
			for (int i = 0; i < N - 2; i++) {
				for (int j = i + 1; j < N - 1; j++) {
					for (int k = j + 1; k < N; k++) { //최소 값 찾기를 한다.
						min_distance = min(min_distance, get_distance(str[i], str[j]) + get_distance(str[j], str[k]) + get_distance(str[i], str[k]));
					}
				}
			}
			cout << min_distance << '\n'; //최소 거리 출력
		}

	}

	return 0;
}

🌟 ハトの巣の原理

定義＃テイギ＃

n+1個の物品をn個の箱に入れる場合、少なくとも1個の箱に2個以上の物品が入っている原理

アテステーション

n個のハト舎とn+1羽のハトがあると仮定した.

ハトの家に1羽以下のハトがいる場合、ハトの家全体には最大n羽のハトがいます.しかしハトはみなn+1羽で矛盾している.

なので、ハトの店が2羽以上あります.

例文

5人が

ソフトボールをしたいと言ったとき、お互い同じチームで試合をしたくないが、チームが4つしかない場合は考えられます.この人たちが違うチームに入りたいなら、ハトの巣の原理によって、5人を4つのチームに分けて、グループごとに1つにすることはできないことがわかります.

ハッシュ・テーブルでは、可能なすべてのキーの数がテーブル・インデックスの数よりも大きいため、競合は避けられない.したがって、ハッシュ関数は競合を回避することはできません.ハッシュ競合

を参照
すべてのファイルを任意の大きいS以下に圧縮する無損圧縮アルゴリズムは存在しない.Sより小さいサイズのファイル数は固定されているため、このようなアルゴリズムが存在する場合、同じファイルに圧縮された2つの異なるファイルが存在しなければならないため、2つのファイルを復元することはできません.

のいずれかのグループで、同じ誕生日の人がペア以上存在しなければならないといえば、そのグループの人数は367人以上でなければなりません.誕生日の場合は2月29日を含めて366種類ありますから.

前の見えない部屋で、4足の異なる靴下が散らばっているときに、5足以上の靴下を選ぶと、靴下と合わせて着ることができます.

13人のうち、同じ月に生まれた人は少なくとも2人以上いる.