ゴールド3-16438サル運動
8870 ワード
サル運動
https://www.acmicpc.net/problem/16438
方法
最初は順番にグループ分けを考えていたが、ふと半分を考えた.
Nの最大個数は99個なので、2^7なら完全に7チームに分けられ、分割征服で解けました.
に答える
organization関数に範囲を追加します.この範囲の半分は「A」で、残りの入力「B」はゲームベクトルに保存されます.次に、分割された範囲を各組織関数に再追加し、対戦テーブルを再帰的に求めます.
最後になって、これ以上分けられなければ全て「B」と入力し、全てのサルが同じチームにならないので、その中の1匹だけをAチームに変えて答えを出します.
コード#コード#
https://www.acmicpc.net/problem/16438
方法
最初は順番にグループ分けを考えていたが、ふと半分を考えた.
Nの最大個数は99個なので、2^7なら完全に7チームに分けられ、分割征服で解けました.
に答える
organization関数に範囲を追加します.この範囲の半分は「A」で、残りの入力「B」はゲームベクトルに保存されます.次に、分割された範囲を各組織関数に再追加し、対戦テーブルを再帰的に求めます.
最後になって、これ以上分けられなければ全て「B」と入力し、全てのサルが同じチームにならないので、その中の1匹だけをAチームに変えて答えを出します.
コード#コード#
#include <iostream>
#include <vector>
using namespace std;
vector<string> games;
bool flag = false;
void organization(int layer, int start, int end)
{
if (layer == 7)
return;
int mid = (start + end) / 2;
for (int i = start; i < mid; i++)
games[layer] += 'A';
for (int i = mid; i < end; i++)
games[layer] += 'B';
organization(layer + 1, start, mid);
organization(layer + 1, mid, end);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
string s = "";
string temp = "";
for (int i = 0; i < 7; i++)
games.push_back("");
organization(0, 0, N);
for (int i = 0; i < N; i++)
{
s += 'B';
if (i == 0)
temp += 'A';
else
temp += 'B';
}
for (int i = 0; i < 7; i++)
{
if (games[i] == s)
cout << temp << endl;
else
cout << games[i] << endl;
}
}
Reference
この問題について(ゴールド3-16438サル運動), 我々は、より多くの情報をここで見つけました https://velog.io/@wooky9633/골드3-백준-16438-원숭이-스포츠テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol