PS2009 에서 돌음. Individual / first 4 hours. 6/793 으로 당시 랭크리스트 7등 성적. 하나만 더 풀었으면 4등인데 아깝당.. 잉 당시 1등인 Warsaw Eagles 는 9문제였는데 (시발) 당시 월드챔피언 -__ -
앞에서부터 풀겠다는 그릇된 욕망 때문에 괜히 C잡고 삽질하다가 고생했다. 코딩 매우 더러움.. ㅜㅜ 아직도 implementation 때문에 삽질을 많이 하는구나...
A: Strange Billboard
Classic problem: 으로 첫 번째 row 를 모두 검사한 뒤 그리디.
lang:cpp
const int INF = 9999;
const int dy[5] = { 0, 1, -1, 0, 0 };
const int dx[5] = { 0, 0, 0, 1, -1 };
void flip(vector<string>& board, int y, int x)
{
for(int k = 0; k < 5; ++k)
{
int ny = y + dy[k], nx = x + dx[k];
if(ny < 0 || nx < 0 || ny >= board.size() || nx >= board[0].size()) continue;
board[ny][nx] = int('X') + int('.') - board[ny][nx];
}
}
int complete(vector<string> board)
{
int ret = 0;
for(int y = 1; y < board.size(); ++y)
for(int x = 0; x < board[y].size(); ++x)
if(board[y-1][x] == 'X')
{
++ret;
flip(board, y, x);
}
if(board.back() == string(board.back().size(), '.')) return ret;
return INF;
}
int go(int x, vector<string>& board)
{
if(x == board[0].size())
return complete(board);
int ret = go(x+1, board);
flip(board, 0, x);
ret = min(ret, go(x+1, board) + 1);
flip(board, 0, x);
return ret;
}
int main()
{
int width, height;
while(cin >> height >> width)
{
if(height == 0) break;
vector<string> board(height);
for(int i = 0; i < height; ++i)
cin >> board[i];
int sol = go(0, board);
if(sol >= INF)
printf("Damaged billboard.\n");
else
printf("You have to tap %d tiles.\n", sol);
}
}
B: Phone Cell
/geometry/sweeping/good
2D 평면에 점들이 N개 주어질 때, 반지름 R 로 덮을 수 있는 최대 점의 수. 역시 클래식한 스위핑 문제. 각도별로 소트해서 스윕한다.
lang:cpp
struct point
{
double y, x;
point(double y = 0, double x = 0) : y(y), x(x) {}
double dot(const point& rhs) const { return y * rhs.y + x * rhs.x; }
double cross(const point& rhs) const { return y * rhs.x - x * rhs.y; }
double polar() const { return atan2(y, x); }
point operator + (const point& rhs) const { return point(y + rhs.y, x + rhs.x); }
point operator - (const point& rhs) const { return point(y - rhs.y, x - rhs.x); }
point operator * (double f) const { return point(y * f, x * f); }
point normalized() const { double d = norm(); return point(y / d, x / d); }
double norm() const { return hypot(y, x); }
};
int n, r;
vector<point> p;
const double PI = 2.0 * acos(0.0);
double fmod(double a, double b)
{
while(a > b) a -= b;
return a;
}
bool cmp(const pair<double,int>& a, const pair<double,int>& b)
{
if(fabs(a.first - b.first) > 1e-7) return a.first < b.first;
return a.second < b.second;
}
int solve(int here)
{
vector<pair<double,int> > events;
// printf("here %d\n", here);
for(int there = 0; there < n; ++there)
if(there != here)
{
point displace = p[there] - p[here];
double dist = displace.norm();
if(dist > 2*r) continue;
double theta = acos((dist/2)/r);
double ang = fmod(displace.polar() + 2*PI, 2*PI);
// printf("\tthere %d, ang %.4lf, theta %.4lf\n", there, ang, theta);
double a = fmod(ang - theta + 2 * PI, 2 * PI);
double b = fmod(ang + theta + 2 * PI, 2 * PI);
if(a > b) swap(a, b);
// printf("\t[%.2lf, %.2lf]\n", a, b);
if(b - a > PI)
{
events.push_back(make_pair(0, -1));
events.push_back(make_pair(a, 1));
events.push_back(make_pair(b, -1));
events.push_back(make_pair(2*PI, 1));
}
else
{
events.push_back(make_pair(a, -1));
events.push_back(make_pair(b, 1));
}
}
sort(all(events), cmp);
// for(int i = 0; i < events.size(); ++i)
// printf("#%d, %.4lf, %d\n", i, events[i].first, events[i].second);
int ret = 0, cur = 0;
for(int i = 0; i < events.size(); ++i)
{
cur -= events[i].second;
ret = max(ret, cur);
}
return ret + 1; // include me
}
int main()
{
while(scanf("%d %d", &n, &r) == 2)
{
if(n == 0 && r == 0) break;
p.resize(n);
for(int i = 0; i < n; ++i)
scanf("%lf %lf", &p[i].x, &p[i].y);
int ret = 1;
for(int i = 0; i < n; ++i)
ret = max(ret, solve(i));
printf("It is possible to cover %d points.\n", ret);
}
}
C: Key Task
/bfs/exponential/graph
지수공간에서의 BFS.
lang:cpp
int c[1<<4][100][100];
string m[100];
int height, width;
const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, 1, -1 };
int ord(char ch)
{
ch = tolower(ch);
const char rep[5] = "byrg";
for(int i = 0; i < 4; ++i) if(rep[i] == ch) return i;
assert(0);
return -1;
}
int solve(int sy, int sx)
{
queue<pair<int, pair<int,int> > > q;
CLEAR(c,-1);
c[0][sy][sx] = 0;
q.push(make_pair(0, make_pair(sy, sx)));
while(!q.empty())
{
int keys = q.front().first;
int hy = q.front().second.first;
int hx = q.front().second.second;
q.pop();
for(int k = 0; k < 4; ++k)
{
int ny = hy + dy[k], nx = hx + dx[k];
if(ny < 0 || ny >= height || nx < 0 || nx >= width) continue;
if(m[ny][nx] == 'X') return c[keys][hy][hx];
if(m[ny][nx] == '#') continue;
if(isupper(m[ny][nx]) && (keys & (1<<ord(m[ny][nx]))) == 0) continue;
int nkeys = keys;
if(islower(m[ny][nx])) nkeys |= (1<<ord(m[ny][nx]));
if(c[nkeys][ny][nx] == -1)
{
c[nkeys][ny][nx] = c[keys][hy][hx] + 1;
q.push(make_pair(nkeys, make_pair(ny, nx)));
}
}
}
return -1; // oops
}
int main()
{
while(cin >> height >> width)
{
for(int i = 0; i < height; ++i)
cin >> m[i];
for(int i = 0; i < height; ++i)
for(int j = 0; j < width; ++j)
{
if(m[i][j] == '*')
{
int ret = solve(i, j);
if(ret == -1)
printf("The poor student is trapped!\n");
else
printf("Escape possible in %d steps.\n", ret+1);
}
}
}
}
F: Weird Numbers
negative base 를 갖는 진수변환. 이런건 경험상 무식하게 예제만 끼워넣으면 어떻게든 나온다고 믿고 있었기 때문에... 무식하게 풀었다. -_-;;;;;
lang:cpp
string toString(int n)
{
char buf[64]; sprintf(buf, "%d", n);
return buf;
}
int signum(long long n)
{
if(n == 0) return 0;
if(n > 0) return 1;
return -1;
}
string to(int r, long long num)
{
if(num == 0) return "0";
int pow = 0;
{
long long digit = 1, sum = 0;
while(true)
{
if(signum(digit) == signum(num))
sum += (abs(r)-1) * digit;
if(abs(sum) >= abs(num)) break;
digit *= r;
pow ++;
}
}
vector<long long> digit(pow+1), minSum(pow+1), maxSum(pow+1);
int rr = abs(r) - 1;
digit[0] = 1; maxSum[0] = rr;
minSum[0] = 0;
for(int i = 1; i <= pow; ++i)
{
digit[i] = digit[i-1] * r;
minSum[i] = minSum[i-1] + min(0LL, digit[i] * rr);
maxSum[i] = maxSum[i-1] + max(0LL, digit[i] * rr);
}
// printf("pow %d\n", pow);
string ret;
while(pow >= 0)
{
// printf("pow %d, num %Ld, digit %Ld, maxSum %Ld minSum %Ld\n", pow, num, digit[pow], maxSum[pow], minSum[pow]);
// printf("ret so far: %s\n", ret.c_str());
if(signum(num) == signum(digit[pow]))
{
long long dig = min<long long>(abs(r)-1, abs(num) / abs(digit[pow]));
long long rem = num - digit[pow] * dig;
// printf("dig before %Ld ", dig);
if(pow > 0 && dig < abs(r)-1)
{
if(rem < 0 && minSum[pow-1] > rem) ++dig;
else if(rem > 0 && maxSum[pow-1] < rem) ++dig;
}
// printf("dig final %Ld\n", dig);
num -= digit[pow] * dig;
ret += toString(dig);
}
else
ret += "0";
--pow;
}
return ret;
}
long long from(int r, string num)
{
long long ret = 0, base = 1;
for(int i = 0; i < num.size(); ++i)
{
ret += base * (num[num.size() - 1 - i] - '0');
base *= r;
}
return ret;
}
int main()
{
/*
printf("%d\n", RAND_MAX);
srand(1547);
for(int test = 0; test < 1000000; ++test)
{
int a = rand() % 9 + 2;
long long b = rand() % 2000001 - 1000000;
string encoded = to(-a, b);
long long decoded = from(-a, encoded);
if(b != decoded)
{
printf("Ooops %d %Ld => %s => %Ld\n", a, b, encoded.c_str(), decoded);
break;
}
}*/
string a, b;
while(cin >> a >> b)
{
if(a == "end") break;
if(a[0] == 't')
cout << to(-atoi(a.c_str() + 3), atoi(b.c_str())) << endl;
else
cout << from(-atoi(a.c_str() + 5), b) << endl;
}
}
H: Reaux! Sham! Beaux!
가위바위보 시뮬레이션.
lang:cpp
const string rock[] = { "kamen", "rock", "pierre", "stein", "ko", "koe", "sasso", "roccia", "guu", "kamien", "piedra", "_" };
const string scissors[] = { "nuzky", "scissors", "ciseaux", "schere", "ollo", "olloo", "forbice", "choki", "nozyce", "tijera", "_" };
const string paper[] = { "papir", "paper", "feuille", "papier", "papir", "carta", "rete", "paa", "papier", "papel", "_" };
bool find(const string* array, const string& move)
{
for(int i = 0; array[i] != "_"; ++i)
if(array[i] == move) return true;
return false;
}
int identify(string move)
{
for(int i = 0; i < move.size(); ++i)
move[i] = tolower(move[i]);
if(find(rock, move)) return 0;
if(find(scissors, move)) return 1;
if(find(paper, move)) return 2;
assert(0);
return -1; //oops
}
int main()
{
string pa, pb, la, lb;
int cc = 0;
while(cin >> la >> pa >> lb >> pb)
{
string ma, mb;
int sa = 0, sb = 0;
while(cin >> ma)
{
if(ma == "." || ma == "-") break;
cin >> mb;
int a = identify(ma), b = identify(mb);
if((a+1) % 3 == b) ++sa;
if((b+1) % 3 == a) ++sb;
}
printf("Game #%d:\n", ++cc);
printf("%s: %d point%s\n", pa.c_str(), sa, sa != 1 ? "s" : "");
printf("%s: %d point%s\n", pb.c_str(), sb, sb != 1 ? "s" : "");
if(sa != sb)
printf("WINNER: %s\n", (sa > sb ? pa.c_str() : pb.c_str()));
else
printf("TIED GAME\n");
printf("\n");
if(ma == ".") break;
}
}
G: Rectangular Polygons
/geometry/good
2차원 평면상에 정수좌표를 갖는 점들이 주어지는데, 이들은 사실 rectilinear polygon 의 코너들이다. degenerate case 혹은 hole 이 없을 때, 이 벽에 오른손을 대고 걸었을 때 이동하는 방향을 N,S,E,W 로 출력하기. 같은 세로선 혹은 가로선 위에 있는 인접한 애들끼리 이어주면 된다. 시계방향 판단이 좀 귀찮음.
lang:cpp
struct point
{
int y, x;
point(int y = 0, int x = 0) : y(y), x(x) {}
int dot(const point& rhs) const { return y * rhs.y + x * rhs.x; }
int cross(const point& rhs) const { return y * rhs.x - x * rhs.y; }
point operator + (const point& rhs) const { return point(y + rhs.y, x + rhs.x); }
point operator - (const point& rhs) const { return point(y - rhs.y, x - rhs.x); }
bool operator < (const point& rhs) const
{
if(y != rhs.y) return y < rhs.y;
return x < rhs.x;
}
};
bool cmpXY(const point& a, const point& b)
{
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool cmpYX(const point& a, const point& b)
{
if(a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
const char dirName[] = "NESW";
int n;
vector<point> p, q;
vector<int> adj[1001];
map<point,int> serial;
int other(int here, int there)
{
if(adj[here][0] == there) return adj[here][1];
return adj[here][0];
}
char identify(int a, int b)
{
if(q[a].x == q[b].x)
return (q[a].y > q[b].y ? 'S' : 'N');
return (q[a].x < q[b].x ? 'E' : 'W');
}
string walk(int here, int there)
{
int start = here;
string before, after;
bool seenFirst = false;
while(true)
{
// printf("here (%d,%d : %d) there (%d,%d : %d) => %c\n", q[here].y, q[here].x, here, q[there].y, q[there].x, there, identify(here, there));
if(here == 0) seenFirst = true;
if(seenFirst)
after += identify(here, there);
else
before += identify(here, there);
int next = other(there, here);
here = there;
there = next;
if(here == start) break;
}
return after + before;
}
int main()
{
while(cin >> n)
{
if(n == 0) break;
serial.clear();
p.resize(n);
for(int i = 0; i < n; ++i)
adj[i].clear();
for(int i = 0; i < n; ++i)
{
cin >> p[i].x >> p[i].y;
serial[p[i]] = i;
}
q = p;
// horz segments
sort(all(p), cmpYX);
int i = 0;
while(i < p.size())
{
int y = p[i].y;
vector<int> line;
while(i < p.size() && p[i].y == y)
{
line.push_back(serial[p[i]]);
++i;
}
/*
printf("at y=%d,", y);
for(int j = 0; j < line.size(); ++j) printf(" (%d,%d : %d)", q[line[j]].y, q[line[j]].x, line[j]);
printf("\n");
*/
for(int j = 0; j < line.size(); j += 2)
{
adj[line[j]].push_back(line[j+1]);
adj[line[j+1]].push_back(line[j]);
}
}
// vert segments
sort(all(p), cmpXY);
i = 0;
while(i < p.size())
{
int x = p[i].x;
vector<int> line;
while(i < p.size() && p[i].x == x)
{
line.push_back(serial[p[i]]);
++i;
}
/* printf("at x=%d,", x);
for(int j = 0; j < line.size(); ++j) printf(" (%d,%d : %d)", q[line[j]].y, q[line[j]].x, line[j]);
printf("\n");*/
for(int j = 0; j < line.size(); j += 2)
{
adj[line[j]].push_back(line[j+1]);
adj[line[j+1]].push_back(line[j]);
}
}
/*
for(int i = 0; i < n; ++i)
{
assert(adj[i].size() == 2);
printf("%d (%d,%d) connects to:", i, q[i].y, q[i].x);
for(int j = 0; j < adj[i].size(); ++j)
{
int k = adj[i][j];
printf(" %d (%d,%d)", k, q[k].y, q[k].x);
}
printf("\n");
}*/
cout << walk(serial[p[0]], serial[p[1]]) << endl;
}
}
