투 명 테 잎

두 종류의 부등호 기호 ‘<’와 ‘>’가 k 개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다.

예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A ⇒ < < < > < < > < >

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다.

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

프로그램의 실행시간은 0.5초를 넘을 수 없다.

입력

• 첫 줄에 부등호 문자의 개수를 나타내는 정수 가 주어진다.
• 그 다음 줄에는 k 개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k 의 범위는 2 <= k <= 9이다.

출력

단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

입출력 예

입력

2
< > 

출력 

897
021

입력 

9
> < < < > > > < <

출력 

9567843012
1023765489

출처:2012 지역 본선 초등 5/5

여러 층으로 이루어진 직사각형 모양의 건물이 있다. 아래 그림 1은 5 개의 층으로 이루어진 직사각형 건물의 예이다. 각 층에는 하나의 막대기가 있는데, 각 막대기의 길이는 서로 다를 수 있다. 그리고 막대기들은 시간 0 에서 시작해서 동시에 왼쪽에서 오른쪽으로 혹은 오른쪽에서 왼쪽으로 움직인다. 시간은 정수시간 단위(0,1,2,...)로 흐르고, 모든 막대기들은 단위시간당 길이 1 만큼 움직인다.

아래 그림 1에서처럼 초기(시간 0)에 각 막대기는 직사각형의 왼쪽 변 또는 오른쪽 변에 닿아있다. 시간이 지남에 따라 각 막대기는 주어진 방향으로 움직이고 막대기의 양쪽 끝 중에 하나가 직사각형의 왼쪽 변 또는 오른쪽 변에 닿으면 진행하는 방향과 반대 방향으로 계속해서 움직인다.

철수(그림 1의 검정색 원)는 초기에 가장 아래층막대기 위에 위치하고 있다. 그리고 아래 조건 1)을 만족하면서 현재 막대기 위에서 움직일 수 있고, 조건 2)를 만족한다면, 하나 위층의 막대기로 올라 갈 수 있다.

• 조건 1) 현재 위치하고 있는 막대기 위에서는 0 시간에 움직일 수 있다. (즉, 막대기 위에서의 움직임은 시간이 걸리지 않는다.)
• 조건 2) 철수가 현재 위치하고 있는 막대기의 임의의 위치에서 수직으로 이동 했을 때, 바로 위 층의 막대기 구간 안에 있으면(구간의 양쪽 끝 포함) 0 시간에 바로 위 층의 막대기로 수직으로 올라갈 수 있다. (즉, 이 조건을 만족해서 하나 위층으로 올라 갈 수 있다면, 올라가는 움직임은 시간이 걸리지 않는다.)

예를 들어서, 아래 그림 2에서처럼 철수는 시간 2 에 두 번째 층을 지나 세 번째 층의 막대기로 움직일 수 있다. 그리고 그림 3에서처럼 시간 4 에 네 번째 층을 지나 다섯 번째 층의 막대기에 도달할 수 있다.

시간 0 의 초기 상태에서 출발해서 철수가 가장 아래층의 막대기에서 가장 위층의 막대기로 올라가는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에 층 수 N ( 1 <= N <= 3000) 과 층의 길이 L ( 1 <= L <= 3000, L 은 짝수)이 주어진다. 가장 아래층은 1 층이고 가장 위층은 N층이다.
• 다음 N개의 줄 중 i 번째 줄에는 i 층의 막대기의 길이 l ( 1 <= l <= L ,l 은짝수) 과 초기에 막대기가 움직이는 방향 d (d=0,1) 가 주어진다. 여기서, d 의 값 0 은 왼쪽에서 오른쪽, 1 은 오른쪽에서 왼쪽을 의미한다. 또한 초기에 막대기들은 방향이 0 인 경우 층의 왼쪽 벽에, 1 인 경우 층의 오른쪽 벽에 닿아 있다고 가정한다.

출력

입출력 예

입력 

4 6
4 1
2 0
4 0
2 1

출력 

0

입력 

5 12
4 1
4 0
2 0
2 1
6 0

출력 

4

출처:2012 지역 본선 초등 4/5

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x,y) 와 오른쪽 위 꼭짓점 좌표 (p,q) 로 주어진다.

이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x,y,p,q 로 표현된다. 단 항상 x < p , y < q 이다.

예를 들어 위 그림에 제시된 직사각형이라면 아래와 같이 표현된다.

3 2 9 8

두 개의 직사각형은 그 겹치는 부분의 특성에 따라 다음 4가지 경우로 분류될 수 있다.

• 먼저 두 직사각형의 겹치는 부분이 직사각형인 경우이다. 아래 그림(a)는 공통부분이 직사각형인 경우의 3가지 예를 보여준다,

  

• 또는 겹치는 부분이 아래 그림 (b)와 같이 선분이 될 수도 있고, 그림 (c)와 같이 점도 될 수 있다.

  

• 마지막으로 아래 그림 (d)와 같이 공통부분 없이 두 직사각형이 완전히 분리된 경우도 있다.

  

여러분은 두 직사각형의 겹치는 부분이 직사각형인지, 선분인지, 점인지, 아니면 전혀 없는 지를 판별해서 해당되는 코드 문자를 출력해야 한다.

입력

각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사각형의 좌표 값은 1이상 50,000 이하의 정수로 제한된다.

출력

입출력 예

입력

3 10 50 60 100 100 200 300
45 50 600 600 400 450 500 543
11 120 120 230 50 40 60 440
35 56 67 90 67 80 500 600    

출력 

d
a
a
b

출처:2012 지역 본선 초등 3/5