이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 410;
int n;
long long ans = 1e18;
string s;
void generate(int a, int b, int c, string crct)
{
if((int)crct.size() == n)
{
vector<int> v1r, v1g, v1y;
vector<int> v2r, v2g, v2y;
for(int i = 0; i < n; i++)
{
if(s[i] == 'R')
{
v1r.push_back(i);
}
if(s[i] == 'G')
{
v1g.push_back(i);
}
if(s[i] == 'Y')
{
v1y.push_back(i);
}
if(crct[i] == 'R')
{
v2r.push_back(i);
}
if(crct[i] == 'G')
{
v2g.push_back(i);
}
if(crct[i] == 'Y')
{
v2y.push_back(i);
}
}
long long num_dif = 0;
for(int i = 0; i < n; i++)
if(s[i] != crct[i]) num_dif++;
ans = min(ans, num_dif);
return;
}
else
{
if((int)crct.size())
{
if(a)
{
char last = crct[crct.size() - 1];
if(last != 'R') generate(a - 1, b, c, crct + "R");
}
if(b)
{
char last = crct[crct.size() - 1];
if(last != 'G') generate(a, b - 1, c, crct + "G");
}
if(c)
{
char last = crct[crct.size() - 1];
if(last != 'Y') generate(a, b, c - 1, crct + "Y");
}
}
else if((int)crct.size() == 0)
{
if(a) generate(a - 1, b, c, crct + "R");
if(b) generate(a, b - 1, c, crct + "G");
if(c) generate(a, b, c - 1, crct + "Y");
}
}
}
string vazia;
int qt[4];
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
char c;
cin >> c;
int tipo;
if(c == 'R') tipo = 1;
else if(c == 'G') tipo = 2;
else tipo = 3;
qt[tipo]++;
s += c;
}
string crct;
generate(qt[1], qt[2], qt[3], vazia);
cout << (ans == (long long)1e18 ? -1 : ans) << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |