2012 TCO Algorithm-Round 1 A
5063 ワード
Links: http://community.topcoder.com/tco12/algorithm-schedule/
スコア250
Simulation.
Math.
Search.
スコア250
Simulation.
class EllysJuice
{
public:
vector <string> getWinners(vector <string> players) {
sort(players.begin(), players.end());
vector <string> ans; ans.clear();
do {
// for(int i = 0; i < (int)players.size(); ++i)
// cout << players[i] << " ; ";
// cout << endl;
double x = 1.0, y = 1.0;
map <string, double> g; g.clear();
double maxv = -1.0;
for(int i = 0; i < (int)players.size(); ++i) {
if( i & 1 ) {
x *= 0.5;
g[ players[i] ] += x;
maxv = max(maxv, g[ players[i] ] );
} else {
y *= 0.5;
g[ players[i] ] += y;
maxv = max(maxv, g[ players[i] ] );
}
}
//cout << " maxv = " << maxv << endl;
int ip = -1;
for(int i = 0; i < (int)players.size(); ++i)
if( (g[ players[i] ] + 1e-9 > maxv) && (maxv + 1e-9 > g[ players[i] ]) ) {
bool ok = 1;
for(int j = i + 1; j < (int)players.size(); ++j)
if( (g[ players[j] ] + 1e-9 > maxv) && (maxv + 1e-9 > g[ players[j] ]) && (players[i] != players[j]) ) {
ok = 0; break;
}
if( ok ) ip = i;
else break;
}
if( ip != -1 ) {
//cout << " [ " << players[ip] << " ] " << endl;
ans.push_back( players[ip] );
}
} while( next_permutation(players.begin(), players.end()) );
sort(ans.begin(), ans.end());
vector <string> ret; ret.clear();
for(int i = 0; i < (int)ans.size(); ++i)
if( i == 0 || ans[i] != ans[i - 1] )
ret.push_back( ans[i] );
return ret;
}
};
スコア.500Math.
typedef long long i64d;
class EllysFractions
{
public:
bool isPrime(int N) {
for(int i = 2; i * i <= N; ++i)
if( N % i == 0 )
return 0;
return 1;
}
i64d getCount(int N) {
i64d ans = 0LL;
for(int i = 2; i <= N; ++i) {
int tot = 0;
for(int j = 2; j <= i; j++)
if( isPrime(j) )
++tot;
ans += 1LL << (tot - 1);
}
return ans;
}
};
スコア1000Search.
const int maxN = 50 + 2;
class EllysLights
{
public:
vector<int> v1[maxN], v2[maxN];
int sgn1[maxN], sgn2[maxN], Len;
void dfs(int ip, int &ans, int dep) {
if( ip == Len ) {
if( ans == -1 || ans > dep ) ans = dep;
return ;
}
if( ans != -1 && dep >= ans ) return ;
if( sgn1[ip] == 1 ) {
for(int i = 0; i < (int)v2[ip].size(); ++i) {
int d = v2[ip][i];
if( sgn2[ d ] ) continue;
bool ok = 1;
for(int j = 0; j < (int)v1[d].size(); ++j)
if( v1[d][j] < ip ) {
ok = 0; break;
}
if( !ok ) continue;
for(int j = 0; j < (int)v1[d].size(); ++j)
sgn1[ v1[d][j] ] ^= 1;
sgn2[d] = 1;
dfs(ip + 1, ans, dep + 1);
sgn2[d] = 0;
for(int j = 0; j < (int)v1[d].size(); ++j)
sgn1[ v1[d][j] ] ^= 1;
}
}
if( sgn1[ip] == 0 ) {
dfs(ip + 1, ans, dep);
for(int i = 0; i + 1 < (int)v2[ip].size(); ++i) {
int d1 = v2[ip][i], d2 = v2[ip][i + 1];
if( sgn2[d1] || sgn2[d2] ) continue;
bool ok = 1;
for(int j = 0; j < (int)v1[d1].size(); ++j)
if( v1[d1][j] < ip ) {
ok = 0; break;
}
if( !ok ) continue;
for(int j = 0; j < (int)v1[d2].size(); ++j)
if( v1[d2][j] < ip ) {
ok = 0; break;
}
if( !ok ) continue;
for(int j = 0; j < (int)v1[d1].size(); ++j)
sgn1[ v1[d1][j] ] ^= 1;
for(int j = 0; j < (int)v1[d2].size(); ++j)
sgn1[ v1[d2][j] ] ^= 1;
sgn2[ d1 ] = sgn2[ d2 ] = 1;
dfs(ip + 1, ans, dep + 2);
sgn2[ d1 ] = sgn2[ d2 ] = 0;
for(int j = 0; j < (int)v1[d1].size(); ++j)
sgn1[ v1[d1][j] ] ^= 1;
for(int j = 0; j < (int)v1[d2].size(); ++j)
sgn1[ v1[d2][j] ] ^= 1;
}
}
}
int getMinimum(string initial, vector <string> switches) {
int L1 = (int)initial.length(), L2 = (int)switches.size();
Len = L1;
memset(sgn1, 0, sizeof(sgn1)); memset(sgn2, 0, sizeof(sgn2));
for(int i = 0; i < L1; ++i) sgn1[i] = (initial[i] == 'Y') ? 1 : 0;
for(int i = 0; i < maxN; ++i) { v1[i].clear(); v2[i].clear(); }
for(int i = 0; i < L2; ++i)
for(int j = 0; j < L1; ++j)
if( switches[i][j] == 'Y' ) {
v1[i].push_back(j);
v2[j].push_back(i);
}
bool ok = 1;
for(int i = 0; i < L1; ++i)
if( !sgn1[i] ) {
ok = 0; break;
}
if( ok ) {
for(int i = 0; i < L1 && ok; ++i)
if( (int)v2[i].size() != 2 ) {
ok = 0; break;
}
for(int i = 0; i < L2 && ok; ++i)
if( (int)v1[i].size() != 2 ) {
ok = 0; break;
}
}
if( ok ) {
return L2 >> 1;
}
int ans = -1;
dfs(0, ans, 0);
return ans;
}
};
Author@SWJTU@2012-04-01.