gshscs

'X'로 표시되어 있는 세 영역을 하나의 영역으로 합치기 위해서 'X'를 추가적으로 칠해야 하는 최소값을 구하는 문제이다.

세 영역밖에 없으므로, 연결하는 경우의 수는 두 가지밖에 없다. 영역을 두개씩 각각 연결하거나(예제), 세 영역의 중간지점에서 세 영역을 동시에 연결하는 경우가 있다. 격자가 최대 50*50=2500개밖에 없으므로, 모든 점들 사이의 경우를 다 따져봐도 2500^2=625만가지이다. 따라서 단순하게 모든 경우를 따져도 시간 안에 답을 구할 수 있다.

매서운 겨울이 지나가고, FJ는 농장의 울타리를 다시 페인트칠하기로 했다. 농장은 모든 성분이 x축과 y축에 평행한 직사각형으로 되어 있는 N개(1 <= N <= 50,000)의 구역으로 나뉘어져 있다. 모든 구역은 울타리로 경계를 표시한다. 어떤 구역이 다른 구역 안에 포함될 수 있지만, 두 구역의 경계가 서로 겹치지는 않는다.

다른 구역 안에 포함되어 있는 구역은 밖에서 볼 수 없기 때문에, FJ는 다른 어떤 구역에도 포함되지 않는 구역만 칠하려고 한다. FJ가 칠해야 하는 구역의 수를 구하는 프로그램을 만드시오.

PROBLEM NAME : painting

INPUT FORMAT

Line 1 : 구역의 수 N이 주어진다.

Line 2~N+1 : 각 직사각형 구역의 정보 x1, y1, x2, y2가 주어진다. (x1, y1)은 구역의 왼쪽 아래 점, (x2, y2)는 구역의 오른쪽 위 점을 나타낸다. 모든 정보는 0과 1,000,000사이의 정수이다.

OUTPUT FORMAT

Line 1 : 다른 어떤 구역에도 포함되지 않는 구역의 수를 구한다.

SAMPLE INPUT

3 2 0 8 9 10 2 11 3 4 2 6 5

SAMPLE OUTPUT

2

http://www.usaco.org/index.php?page=viewproblem2&cpid=263

여러가지 해법들이 있지만, O(N)의 시간 안에 답을 구할 수 있는 간단한 그리디 알고리즘을 소개하겠다.
최소 실행 수는 a[i]와 a[i-1], a[i+1]의 차이의 합의 절반과 같다는 것에 주목할 필요가 있다. 왜 그런지는 잘 생각해보자.

a[i]-a[i-1]은 i등급부터 straight가 시작되는 수를 나타낸다. a[i]와 a[i+1]의 경우에서도 마찬가지이다. 따라서 최소 실행 수는 abs(a[i+1]-a[i])의 합에서 2로 나눈 값이다.

Bessie와 친구들은 1부터 N(1 <= N <= 100,000)까지 등급이 매겨진 카드를 가지고 특이한 방식의 포커를 하고 있다(보통은 N = 13). 게임 방식은 간단하다. i부터 j까지 등급의 카드가 한 개씩 있으면 “straight”라고 하고, 그 카드들은 없앤다.

Bessie는 i등급의 카드를 a_i개씩 가지고 있다. 모든 카드를 없애기 위해서 필요한 최소 실행 수를 구하여라.

PROBLEM NAME : poker

INPUT FORMAT

Line 1 : 정수 N이 주어진다.

Line 2~N+1 : i등급의 카드의 개수 a_i가 주어진다.

OUTPUT FORMAT

Line 1 : 모든 카드를 없애기 위해서 필요한 최소의 실행 수를 출력한다.

SAMPLE INPUT

5 2 4 1 2 3

SAMPLE OUTPUT

6

http://www.usaco.org/index.php?page=viewproblem2&cpid=262

가장 쉬운 방법은 재귀적으로 모든 경우를 다 살펴보는 것이다. 재귀함수에서는 소의 번호 x만 있으면 된다. 1번 소부터 시작해서 조건을 만족하는지 차례로 살펴보면, 최악의 경우 O(K*3^N)의 시간 안에 답을 구할 수 있다. 하지만 적절히 커팅을 하면 대략 O(3^N)의 시간 안에 답을 구할 수 있을 것이다.

재귀함수를 쓰지 않고 답을 구할 수도 있는데, 3진법의 N자릿수를 생각해본다. 그리고 0부터 3^N-1까지 모든 경우를 반복문으로 확인해도 O(3^N)의 시간 안에 답을 구할 수 있다.

FJ에게는 세 가지 다른 품종(Holstein, Jersey, Guernsey)의 소 N마리(2 <= N <= 15)가 있다.

불행하게도, FJ는 소들의 품종을 잊어버렸다! 다행히도 FJ는 소들 사이의 관계를 K(1 <= K <= 50)개 알고 있다. 예를 들어, 1번과 2번 소가 같은 품종이거나, 1번과 5번 소가 다른 품종인 것을 알고 있을 수도 있다.

이러한 관계가 입력으로 주어질 때, 소들의 가능한 품종의 가짓수를 구하는 프로그램을 만드시오.(입력된 정보가 모순일 때는 0을 출력한다.)

PROBLEM NAME : assign

INPUT FORMAT

Line 1 : 두 정수 N과 K가 주어진다.

Line 2~K+1 : x번 소와 y번 소의 관계를 나타내는 정보가 주어진다.(1 <= x, y <= N, x != y) 입력은 “S x y”나 “D x y”로 주어지는데, “S x y”는 x번 소와 y번 소가 같은 품종임을 나타내고, “D x y”는 x번 소와 y번 소가 다른 품종임을 나타낸다.

OUTPUT FORMAT

Line 1 : 소들의 가능한 품종의 가짓수를 출력한다.

SAMPLE INPUT

4 2 S 1 2 D 1 3

SAMPLE OUTPUT

18

http://www.usaco.org/index.php?page=viewproblem2&cpid=261

소들의 거리가 K 이하일 때 혼잡하다는 데 주의할 필요가 있다. 거리가 K 이하인 모든 경우를 찾으면 될 것이고, 그러면 O(NK)의 시간이 소요될 것이다. 하지만 Sliding Window를 쓰면 계산량을 크게 줄일 수 있다.

[7 3 4 2] 3 4 
7 [3 4 2 3] 4 -> 최대 혼잡도 3
7 3 [4 2 3 4] -> 최대 혼잡도 4

한 Window 안에서 품종이 같은지 확인하기 위해서 해싱을 쓰면 된다.

FJ의 N마리(1 <= N <= 50,000) 소들이 한 줄로 서 있다. 모든 소는 정수로 표시된 품종 ID가 있다.

품종이 같은 소들은 너무 가까이 붙어있을 경우 싸울 수도 있다.

품종이 같은 소들의 거리가 K(1 <= K < N) 이하일 때 “혼잡”하다고 말한다.

“혼잡”한 소들의 품종 ID 중 최댓값을 구하는 프로그램을 만드시오.

PROBLEM NAME : proximity

INPUT FORMAT

Line 1 : N, K가 한 줄에 주어진다.

Line 2~N+1 : 한 줄로 서 있는 각 소들의 출신지 ID가 주어진다. 모든 정보는 0과 1,000,000 사이의 정수이다.

OUTPUT FORMAT

Line 1 : “혼잡”한 소들의 품종 ID 중 최댓값을 출력하시오. 존재하지 않는 경우 –1을 출력한다.

SAMPLE INPUT

6 3 7 3 4 2 3 4

SAMPLE OUTPUT

4

http://www.usaco.org/index.php?page=viewproblem2&cpid=260

문제의 조건에서, 소들이 달리는 시간은 길어봤자 100만(10^6)임을 알 수 있다.  따라서 모든 시간에서 두 소의 위치를 측정하면서 'leadership change'가 몇번 일어나는지만 구하면 된다.

Bessie과 Elsie는 누가 더 빠른지 정하기 위해 농장에서 경주를 하기로 했다.

두 소는 같은 위치에서 출발하고 같은 시간에 같은 방향으로 달린다. 소들은 일정한 구간을 일정한 속도로 달린다. 예를 들어서, Bessie는 5m/s의 속도로 3초 동안 달리고, 그 다음 10m/s으로 6초 동안 달릴 수 있다.

소들은 당신에게 ‘leadership change’가 일어나는 수를 구해달라고 한다. 어떤 소가 다른 소를 앞지르면 ‘leadership change’라고 한다. 예를 들어서, A가 앞서다가 B가 앞지르거나, A가 앞서다가 B와 일정 시간동안 동등하게 달린 후, B가 앞지르는 경우 모두 ‘leadership change’라고 한다.

PROBLEM NAME : cowrace

INPUT FORMAT

Line 1 : 두 정수 N, M이 주어진다.(1 <= N, M <= 1,000)

Line 2~N+1 : Bessie가 달리는 정보가 두 개의 정수, Bessie의 속도와 그 속도로 달리는 시간으로 주어진다. 모든 정보는 1에서 1,000 사이의 정수이다.

Line N+2~N+M+1 : Elsie의 정보가 위와 동일하게 주어진다.

OUTPUT FORMAT

Line 1 : ‘leadership change’가 일어나는 횟수를 출력하시오.

SAMPLE INPUT

4 3 1 2 4 1 1 1 2 10 2 3 1 2 3 9

SAMPLE OUTPUT

2

http://www.usaco.org/index.php?page=viewproblem2&cpid=259