Level 3를 패스한 사람이 다섯명밖에 없을정도로 풀기싫은[?] 난이도의 문제가 한국인들을 죄다 안드로메다로...
Petr는 언제나 참가했다하면 1등.. ACRush는 그 뒤를 잇는군요. 3900을 바라보는 Petr입니다. 4000을 넘으면 타겟에서 다른걸로 바뀔까요?
Easy (250 pts.)
문제 설명
(문제의 의미만 같게 전달되도록 의역하겠습니다 -_-)
당신은 높이가 같은 상자들을 가지고 있다. 이 상자들을 몇 가지 규칙에 맞게 쌓아올리려고 한다.
규칙 1) 제일 윗 상자는 최대 1, 두번째 상자는 최대 2, ..., k번째 상자의 크기는 최대 k로 제한되어 있다.
규칙 2) 아래쪽 상자의 크기가 위쪽 상자의 크기보다 같거나 커야한다. 위쪽 상자가 더 크다면 안정적이지 못하기 때문이다.
규칙 3) 상자를 쌓을 때에는 항상 왼쪽칸에 맞춰서 쌓는다고 가정한다.
바닥층 상자의 최대 크기 n이 주어졌을 때, 상자를 쌓아 올릴 수 있는 경우의 수를 리턴하시오. 예를 들어 n = 2라고 하면 아래의 4 가지 경우밖에 존재하지 않으므로, 4를 리턴한다. (흰색은 빈칸이다)
[spoiler="더 보기..."]* 문제 풀이
기본적인 Dynamic Programming 문제였습니다. Table(i, j)를 아래와 같이 정의해봅시다.
Table(i, j) = i번째 높이에 크기 j의 상자를 쌓은 경우의 수[/spoiler]
우선, 아무것도 없는 경우가 존재하므로, 초기값 Table(0, 0) = 1로 설정해줍니다.
그런 다음 Table(i, j)에 대한 점화식을 세워봅시다. i번째 높이에 크기 j의 상자를 쌓는 경우의 수는 i-1번째 높이에 크기 0 ~ j의 상자를 쌓는 경우의 수의 합이 됩니다. 여기서 주의해야 할 점은 i와 j가 같은 경우라면 i-1번째 높이에 i 크기의 상자를 쌓을 수가 없으므로, 따로 처리해주어야 한다는 점이지요. (특별히 처리하지 않더라도, i < j 인 경우의 Table(i, j) = 0이기 때문에 답은 같을 것입니다.)
Medium (550 pts.)
문제 설명
3차원 공간에서 움직일 수 있는 입자가 있다. 만약 이 입자가 charged 상태라면 입자는 나선형 궤도를 따라 움직인다. 만약 uncharged 상태라면 입자는 직선 운동을 하게 된다. charged 상태인 입자와 uncharged 상태인 입자가 있을 때, 이 입자들이 충돌하는지 충돌하지 않는지 알고 싶다.
charged 상태인 입자의 운동 경로는 아래와 같다.
x1 = cos(PI * t)
y1 = sin(PI * t)
z1 = t
uncharged 상태인 운동 경로는 아래와 같다.
x2 = vx * t + x0
y2 = vy * t + y0
z2 = vz * t + z0
위의 식에서 t는 임의의 상수이며, 두 입자는 각각 독립적으로 움직인다.
vx, vy, vz, x0, y0, z0가 주어졌을 때, 두 입자가 충돌하는지 충돌하지 않는지 구하는 프로그램을 작성하시오. 만약 한 점에서 충돌한다면 그 때의 x좌표, y좌표, z좌표를 리턴하여라. 두 점 이상에서 충돌한다면 (0, 0, 0)을 리턴하여라. 만약 충돌하지 않는다면 empty값을 반환한다.
[spoiler="더 보기..."] * 문제 풀이
기본적인 수학 지식이 뒷받침되어야 풀 수 있는 문제입니다. charged 입자가 (x1^2 + y1^2) = 1 이라는 것을 알고 있는 상태라야 이 문제를 접근할 수가 있게 되지요. (만약 모르신다면, 고등학교 수학 참고서를 한 번 살펴보는것이.. ^^;; )
x1 = x2, y1 = y2, z1 = z2를 만족해야 충돌하는 것이므로, (x1^2 + y1^2) = 1이라면 (x2^2 + y2^2) = 1이라는 것을 알 수 있습니다. 이를 풀면 t에 대한 2차 방정식을 구할 수가 있지요.
t를 구한 다음의 처리는 간단합니다. t가 구해졌다면 (x1, y1, z1)을 바로 구할 수 있기 때문이지요. 실제로 uncharged 상태인 입자가 (x1, y1, z1)을 지나는지만 처리해 주면 됩니다. 다만 예외처리가 좀 많아서 많은 사람들이 system test를 통과하지 못한 문제이지요. 직접 풀어보시면서 고쳐나가는 것이 도움이 될 것입니다.
[/spoiler]
Hard (950 pts.)
문제 설명
볼록 다각형이 입력으로 주어졌을 때, N-cool Point의 개수를 구하는 프로그램을 작성하시오. 어떤 점이 볼록 다각형 내부에 위치한 정수 좌표의 점이며, N-cool segment의 끝점을 만족할 때 우리는 이 점을 N-cool Point라고 부른다. 어떤 선분이 다각형 내부에 위치한 선분이 N개 이상의 정수좌표를 지나는 경우에 N-cool segment라고 부른다.
아래에 예제가 있다. N = 6 일때 아래의 볼록 다각형에는 총 21개의 (연두색으로 표시된) N-cool Point가 존재한다. 또한 빨간 색 선분은 N-cool segment를 의미한다.
[spoiler="더 보기..."]* 문제 풀이
다섯 명 밖에 풀지 못했던, 어려운 문제입니다. (그나마 다섯 명 중의 한 명은 틀린 솔루션이었지만 Systest를 통과한 경우라, 엄밀하게 말하면 제대로 푼 사람은 네 명이라고 볼 수 있습니다.) 네 개의 소스를 모두 읽어보았는데, 같은 알고리즘이더군요 -_-
아래는 문제에 그려져 있던 예제 데이터입니다. (N - 1) x (N - 1) 크기의 격자로 쪼개보았습니다 (N = 6이므로 5 x 5 단위로 쪼갰습니다).
다각형 내부에 있는 점들을 살펴보겠습니다. 위에서 빨간색으로 표시된 세 개의 점이 있지요, 이 점들은 원점을 기준으로 보았을 때 (2, 1) 위치에 존재함을 알 수 있습니다. 즉 '위상'이 같다고 볼 수 있겠지요. 이러한 점들 사이에는 N개의 (inclusive) 점이 존재함을 알 수 있습니다. (증명은 생각보다 간단합니다. 도전해보세요!) 같은 방법으로 파란 색 점들도 위상이 같고, 두 점을 연결하였을 때 N개의 점이 사이에 있다는 것을 알 수 있지요.
코딩 자체는 생각보다 간단할 것 같습니다. 다각형 내부에 포함되어 있는 점이 50만개 이하라는 조건이 있기 때문이지요, 다각형 내부에 있는 모든 정수좌표들의 Set을 구하는 루틴과 이 Set에서 같은 위상에 있는 점이 둘 이상 있을 때 점의 개수의 합을 구하는 루틴. 둘로 나눠서 구현할 수 있겠지요.
[/spoiler]
astein
Level 3를 패스한 사람이 다섯명밖에 없을정도로 풀기싫은[?] 난이도의 문제가 한국인들을 죄다 안드로메다로...
Petr는 언제나 참가했다하면 1등.. ACRush는 그 뒤를 잇는군요. 3900을 바라보는 Petr입니다. 4000을 넘으면 타겟에서 다른걸로 바뀔까요?
Easy (250 pts.)
문제 설명
(문제의 의미만 같게 전달되도록 의역하겠습니다 -_-)
당신은 높이가 같은 상자들을 가지고 있다. 이 상자들을 몇 가지 규칙에 맞게 쌓아올리려고 한다.
규칙 1) 제일 윗 상자는 최대 1, 두번째 상자는 최대 2, ..., k번째 상자의 크기는 최대 k로 제한되어 있다.
규칙 2) 아래쪽 상자의 크기가 위쪽 상자의 크기보다 같거나 커야한다. 위쪽 상자가 더 크다면 안정적이지 못하기 때문이다.
규칙 3) 상자를 쌓을 때에는 항상 왼쪽칸에 맞춰서 쌓는다고 가정한다.
바닥층 상자의 최대 크기 n이 주어졌을 때, 상자를 쌓아 올릴 수 있는 경우의 수를 리턴하시오. 예를 들어 n = 2라고 하면 아래의 4 가지 경우밖에 존재하지 않으므로, 4를 리턴한다. (흰색은 빈칸이다)
[spoiler="더 보기..."]* 문제 풀이
기본적인 Dynamic Programming 문제였습니다. Table(i, j)를 아래와 같이 정의해봅시다.
Table(i, j) = i번째 높이에 크기 j의 상자를 쌓은 경우의 수[/spoiler]
우선, 아무것도 없는 경우가 존재하므로, 초기값 Table(0, 0) = 1로 설정해줍니다.
그런 다음 Table(i, j)에 대한 점화식을 세워봅시다. i번째 높이에 크기 j의 상자를 쌓는 경우의 수는 i-1번째 높이에 크기 0 ~ j의 상자를 쌓는 경우의 수의 합이 됩니다. 여기서 주의해야 할 점은 i와 j가 같은 경우라면 i-1번째 높이에 i 크기의 상자를 쌓을 수가 없으므로, 따로 처리해주어야 한다는 점이지요. (특별히 처리하지 않더라도, i < j 인 경우의 Table(i, j) = 0이기 때문에 답은 같을 것입니다.)
Medium (550 pts.)
문제 설명
3차원 공간에서 움직일 수 있는 입자가 있다. 만약 이 입자가 charged 상태라면 입자는 나선형 궤도를 따라 움직인다. 만약 uncharged 상태라면 입자는 직선 운동을 하게 된다. charged 상태인 입자와 uncharged 상태인 입자가 있을 때, 이 입자들이 충돌하는지 충돌하지 않는지 알고 싶다.
charged 상태인 입자의 운동 경로는 아래와 같다.
x1 = cos(PI * t)
y1 = sin(PI * t)
z1 = t
uncharged 상태인 운동 경로는 아래와 같다.
x2 = vx * t + x0
y2 = vy * t + y0
z2 = vz * t + z0
위의 식에서 t는 임의의 상수이며, 두 입자는 각각 독립적으로 움직인다.
vx, vy, vz, x0, y0, z0가 주어졌을 때, 두 입자가 충돌하는지 충돌하지 않는지 구하는 프로그램을 작성하시오. 만약 한 점에서 충돌한다면 그 때의 x좌표, y좌표, z좌표를 리턴하여라. 두 점 이상에서 충돌한다면 (0, 0, 0)을 리턴하여라. 만약 충돌하지 않는다면 empty값을 반환한다.
[spoiler="더 보기..."] * 문제 풀이
기본적인 수학 지식이 뒷받침되어야 풀 수 있는 문제입니다. charged 입자가 (x1^2 + y1^2) = 1 이라는 것을 알고 있는 상태라야 이 문제를 접근할 수가 있게 되지요. (만약 모르신다면, 고등학교 수학 참고서를 한 번 살펴보는것이.. ^^;; )
x1 = x2, y1 = y2, z1 = z2를 만족해야 충돌하는 것이므로, (x1^2 + y1^2) = 1이라면 (x2^2 + y2^2) = 1이라는 것을 알 수 있습니다. 이를 풀면 t에 대한 2차 방정식을 구할 수가 있지요.
t를 구한 다음의 처리는 간단합니다. t가 구해졌다면 (x1, y1, z1)을 바로 구할 수 있기 때문이지요. 실제로 uncharged 상태인 입자가 (x1, y1, z1)을 지나는지만 처리해 주면 됩니다. 다만 예외처리가 좀 많아서 많은 사람들이 system test를 통과하지 못한 문제이지요. 직접 풀어보시면서 고쳐나가는 것이 도움이 될 것입니다.
[/spoiler]
Hard (950 pts.)
문제 설명
볼록 다각형이 입력으로 주어졌을 때, N-cool Point의 개수를 구하는 프로그램을 작성하시오. 어떤 점이 볼록 다각형 내부에 위치한 정수 좌표의 점이며, N-cool segment의 끝점을 만족할 때 우리는 이 점을 N-cool Point라고 부른다. 어떤 선분이 다각형 내부에 위치한 선분이 N개 이상의 정수좌표를 지나는 경우에 N-cool segment라고 부른다.
아래에 예제가 있다. N = 6 일때 아래의 볼록 다각형에는 총 21개의 (연두색으로 표시된) N-cool Point가 존재한다. 또한 빨간 색 선분은 N-cool segment를 의미한다.
[spoiler="더 보기..."]* 문제 풀이
다섯 명 밖에 풀지 못했던, 어려운 문제입니다. (그나마 다섯 명 중의 한 명은 틀린 솔루션이었지만 Systest를 통과한 경우라, 엄밀하게 말하면 제대로 푼 사람은 네 명이라고 볼 수 있습니다.) 네 개의 소스를 모두 읽어보았는데, 같은 알고리즘이더군요 -_-
아래는 문제에 그려져 있던 예제 데이터입니다. (N - 1) x (N - 1) 크기의 격자로 쪼개보았습니다 (N = 6이므로 5 x 5 단위로 쪼갰습니다).
다각형 내부에 있는 점들을 살펴보겠습니다. 위에서 빨간색으로 표시된 세 개의 점이 있지요, 이 점들은 원점을 기준으로 보았을 때 (2, 1) 위치에 존재함을 알 수 있습니다. 즉 '위상'이 같다고 볼 수 있겠지요. 이러한 점들 사이에는 N개의 (inclusive) 점이 존재함을 알 수 있습니다. (증명은 생각보다 간단합니다. 도전해보세요!) 같은 방법으로 파란 색 점들도 위상이 같고, 두 점을 연결하였을 때 N개의 점이 사이에 있다는 것을 알 수 있지요.
코딩 자체는 생각보다 간단할 것 같습니다. 다각형 내부에 포함되어 있는 점이 50만개 이하라는 조건이 있기 때문이지요, 다각형 내부에 있는 모든 정수좌표들의 Set을 구하는 루틴과 이 Set에서 같은 위상에 있는 점이 둘 이상 있을 때 점의 개수의 합을 구하는 루틴. 둘로 나눠서 구현할 수 있겠지요.
[/spoiler]
15년 전