5개의 댓글이 있습니다.
-
-
astein -
http://felix-halim.net/tc/index.php?rd=10659 을 이용하시면 됩니다 'ㅁ'
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
SINCE 2007
astein
오늘의 스탠딩입니다.
음.. 150등 안에 한국인이 다섯명이 있긴 하지만 성적은 썩 좋지 않네요.
개인적으로는 다들 맞은 Level 1 틀린게 좀 컸네요 -.-;;
Easy (250 pts.)
#define sz(a) ((a).size()) word, int w, int h, int fontsize) {
bool go(vector
int lines = h / (2 * fontsize); // panel에 채울 수 있는 최대 line
int chars = w / (fontsize + 2); // 한 줄에 채울 수 있는 최대 글자수
// 어떤 단어도 height제한 때문에 panel에 들어가지 않는 경우
if (lines == 0) return false;
int a = 1, b = -1; // a는 몇 개의 line을 사용했는지, b는 현재 line에 몇 개의 character를 사용했는지 count합니다.
for (int i = 0; i < sz(word); i++) {
// panel의 width제한 때문에 단어를 채울 수 없는 경우
if (sz(word[i]) > chars) return false;
b += sz(word[i]) + 1;
if (b > chars) {
a++;
if (a > lines) return false; // height 제한 초과
b = sz(word[i]);
}
}
return true;
}
[/spoiler]
Hard (1000 pts.)
문제설명
어떤 점들의 집합이 주어졌을 때, 아래의 조건을 만족시키는 나선(Spiral)을 구성하는 최대 점의 개수를 구하시오.
<< 조건 >>
위와 같이 정의된 table에서 최근에 a - b 가 연결되었고, 아직 사용되지 않는 점들의 집합 S가 있습니다. 그러면 이 중에서 S - p를 연결할 수 있고, table[b][p][S - p] + 1 중에서 제일 큰 값이 table[a][b][S]에 들어가게 됩니다.
4가지 규칙 중 마지막 규칙을 해결하는 것이 제일 까다롭지만, 이 규칙은 "제일 마지막에 연결되는 선분(위의 설명에서, 선분b - p)이 현재까지의 spiral에서 사용했던 점들 모두 strict하게 left side에 있다"를 체크함으로서 해결 가능합니다. 만약 b - p와 같은 선 상에 점이 있다면, b - p 다음 점은 항상 반시계 방향(혹은 일직선)으로 꺾여야 하므로 spiral 안쪽으로 휘어들어가는 모양이 됩니다. 결국 위를 반복해도, 마지막 반직선은 spiral 어딘가에 부딪치게 되므로, 어떻게 하더라도 규칙 4를 만족시킬 수 없게 됩니다.
P.S) 일단 소스를 첨부하긴 합니다만, 매크로에 익숙하지 않은 경우, 읽으시는 데 약간 어려움이 있으실 수도 있겠네요 ㅜㅜ
다음에 시간나면 수정하겠습니다 orz
#define EPS 1e-10 a;
points) {
#define pb push_back
#define sz(a) ((int)a.size())
#define REP(i,n) FOR(i,0,n)
struct Point {
int x, y;
Point(int ix = 0, int iy = 0) : x(ix), y(iy) {}
bool operator == (const Point &a) const {
return abs(x - a.x) < EPS && abs(y - a.y) < EPS;
}
};
char table[16][16][1 << 16];
vector
int N;
struct SpiralConstruction {
// a, b, c가 일직선상에 있다고 가정했을 때 a -- b -- c => true
bool between(Point a, Point b, Point c) {
int X = (a.x - b.x) * (c.x - b.x);
int Y = (a.y - b.y) * (c.y - b.y);
return (X <= 0 && Y <= 0);
}
// a-b-c가 counter clockwise꺾임인가? (일직선 상이라면, 현재 방향 그대로 직진인 경우 true)
bool left(Point a, Point b, Point c) {
int p = (a.x * b.y + b.x * c.y + c.x * a.y);
p -= (a.x * c.y + b.x * a.y + c.x * b.y);
if (p < 0) return false;
if (p == 0 && !between(b, a, c)) return false;
return true;
}
// for memoization.
int go(int q, int w, int bit) {
if (table[q][w][bit] != -1) return table[q][w][bit];
int ret = 0;
REP(i, N) {
if (bit & (1 << i)) {
bool flag = true;
REP(j, N + 1) {
if (!(bit & (1 << j)) && j != w && j != i && !left(a[w], a[i], a[j]) ) flag = false; // (w - i - 현재까지 사용한 점)이 strict 왼쪽꺾임이 아닌 경우 더 이상 진행하지 않으면 되므로, flag = false;
}
if (flag) ret >?= go(w, i, bit - (1 << i)) + 1; // >?=는 ret = max(ret, go(w, i, bit - (1 << i)) + 1) 과 같습니다. ㅠㅠ
}
}
return (table[q][w][bit] = ret);
}
int longestSpiral(vector
memset(table, -1, sizeof(table));
N = sz(points);
a.resize(N + 1);
REP(i, N) {
istringstream sin(points[i]);
sin >> a[i].x >> a[i].y;
}
a[N] = Point(0, 0); // N번째 점은 (0,0)
int ret = 0;
REP(i, N)
ret >?= go(N, i, (1 << N) - 1 - (1 << i)) + 1; // N-i로 시작
return ret;
}
};
16년 전