gshscs

매서운 겨울이 지나가고, 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

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

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

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

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