수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

영식이는 숫자를 셀 때, 왼손을 이용한다. 엄지손가락부터 시작해서 새끼손가락까지 차례대로 하나씩 센다. 그다음에 새끼손가락까지 센 다음에는 반대로 엄지손가락으로 다시 역방향으로 센다. 영식이는 자기가 원하는 숫자가 나올 때 까지 계속해서 이 방법으로 센다. 영식이는 절대 손가락을 건너뛰지 않는다. 예를 들어 숫자 10을 셀 때는, 엄지->검지->중지->약지->새끼->약지->중지->검지->엄지->검지 이렇게 센다.

슬프게도, 영식이는 민식이와 싸우다가 손가락을 하나 다쳤다. 멍청한 영식이는 오른손으로는 셀 수 없기 때문에, 오늘도 역시 왼손으로 세야 한다. 영식이는 다친 손가락을 아얘 쓸 수 없는 것은 아니고, 셀 수 있는 횟수가 제한되어 있는 것이다.

영식이가 셀 수 있는 최대 숫자를 출력하는 프로그램을 작성하시오.

첫째 줄에 영식이가 다친 손가락이 주어진다. 엄지부터 차례대로 1,2,3,4,5로 번호가 매겨져 있다. 둘째 줄에는 영식이가 다친 손가락으로 몇 번 셀수 있는지 주어진다. 이 수는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

첫째 줄에 영식이가 셀 수 있는 수의 최대값을 출력한다. 만약 시작도 할 수 없으면 0을 출력한다.

1,2,3,4,5,4,3,2,1,2,3,4,5,4,3 위와같이 세면 총 15를 셀 수 있다. 2번째 손가락을 3번 이용했으므로 더 이상 이용할 수 없기 때문에 여기가 영식이의 한계이다.

인하대학교에 다니는 토쟁이는 y축과 평행한 w개의 도로, x축과 평행한 h개의 도로가 있는 도시에 살고 있다. 토쟁이의 집은 이 도시의 맨 왼쪽 아래에 위치하며 좌표로는 (1, 1)로 표시할 수 있다. 매일 아침 토쟁이는 등교를 하며, 등굣길에 토스트 가게에 들러 토스트를 사 먹는다. 이때 학교의 위치는 토쟁이의 집 반대쪽 맨 오른쪽 위에 위치하며 좌표로는 (w, h)로 표시할 수 있다. 토쟁이는 늦장 부리는 것을 좋아하여 수업 시작 시간에 맞게 도착하게끔 출발한다. 따라서 토스트 가게를 거쳐 학교로 가는 경로는 항상 최소의 시간이 걸려야 한다. (토쟁이는 토스트를 매우 빠르게 먹어 0초 만에 먹으며, 토스트 가게 아주머니 역시 토스트 장인이기 때문에 0초 만에 토스트를 만든다고 가정한다) 이 때, 토쟁이가 토스트를 먹고 학교에 늦지 않게 도착할 수 있는 경로는 몇 가지일까??

예를 들면, y축과 평행한 도로가 3개 있으며, x축과 평행한  도로가 2개 있다고 했을 때, 도시는 아래의 그림과 같이 그려진다.

이 때, 토스트 가게가 (2,2)에 위치하면, 토쟁이의 집은 (1,1)에 위치하고, 학교는 (3,2)에 위치하므로, 이 때 경로들은

위와 같이 2가지이다.

입력의 첫째 줄에 도시의 y축과 평행한 도로의 개수 w와 x축과 평행한 도로의 개수 h가 주어진다. (2 ≤ w, h ≤ 200)

둘째 줄에는 토스트 가게의 (x, y)좌표가 주어진다. (1 ≤ x ≤ w,1 ≤ y ≤ h) x, y는 항상 정수이다.

첫째 줄에 토쟁이가 학교에 늦지 않게 도착할 수 있는 등굣길의 개수를 1,000,007로 나눈 나머지 값을 출력한다. 

어떠한 자연수 N에 대해서 N을 제외한 약수(진약수)의 합이 N이 되는 자연수를 완전수라고 한다. 예를 들어, 6의 약수는 1, 2, 3, 6인데 1+2+3은 6이기 때문에 완전수이다. 또 진약수의 합이 자기 자신보다 작은 경우를 부족수, 진약수의 합이 자기 자신보다 큰 경우를 과잉수라고 한다.

이 때, 어떤 수가 주어질 때 이 수가 완전수인지, 부족수인지, 과잉수인지를 구하는 프로그램을 작성하시오.

첫째 줄에 자연수의 개수 T가 주어진다. T은 1000보다 작은 수이다.

둘째 줄에는 공백을 사이에 두고 완전수인지 구해야 되는 자연수 N이 주어진다.(N<10000)

T개 줄에 걸쳐서 각 자연수에 대해서 완전수면 ‘Perfect’, 부족수면 ‘Deficient’, 과잉수면 ‘Abundant’를 출력한다.

28의 경우 약수가 1, 2, 4, 7, 14, 28 이고, 1+2+4+7+14=28이기 때문에 완전수이다.

21의 경우 약수가 1, 3, 7, 21 이고, 1+3+7=11<21이기 때문에 부족수이다.

36의 경우 약수가 1, 2, 3, 4, 6, 9, 12, 18, 36 이고, 1+2+3+4+6+9+12+18=55>36이기 때문에 과잉수 이다.

상근이와 친구들은 MT에 가서 아래 설명과 같이 재미있는 게임을 할 것이다.

각 플레이어는 1이상 100 이하의 정수를 카드에 적어 제출한다. 각 플레이어는 자신과 같은 수를 쓴 사람이 없다면, 자신이 쓴 수와 같은 점수를 얻는다. 만약, 같은 수를 쓴 다른 사람이 있는 경우에는 점수를 얻을 수 없다.

상근이와 친구들은 이 게임을 3번 했다. 각 플레이어가 각각 쓴 수가 주어졌을 때, 3번 게임에서 얻은 총 점수를 구하는 프로그램을 작성하시오.

첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다.

각 플레이어가 3번의 게임에서 얻은 총 점수를 입력으로 주어진 순서대로 출력한다.

플레이어 1 : 0 + 0 + 0 = 0

플레이어 2 : 0 + 0 + 92 = 92

플레이어 3 : 63 + 89 + 63 = 215

플레이어 4 : 99 + 0 + 99 = 198

플레이어 5 : 89 + 0 + 0 = 89

Mickey의 뒷마당에는 특정 수의 양이 있다. 그가 단단히 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 정사각형 모양에 행과 열로 이루어진 필드이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 펜스를, 글자 'o'는 양, 'v'는 늑대를 의미한다.

우리는 수평, 수직으로만 이루어지고 펜스가 없는 경로에 한하여 한 필드에서 다른 필드로 이동할 수 있다면 같은 영역이라고 간주한다. 우리가 "탈출"할 수 있는 영역은 그 어떠한 영역의 부분으로도 간주하지 않는다.

다행히 우리의 양은 카라테 검은 띠 보유자여서 늑대에게 싸움을 걸 수 있고 영역에 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 아직 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

R개의 줄은 C개의 글자를 가진다. 이들 모두는 마당의 구조(마당의 펜스, 양, 늑대의 위치)를 의미한다.

참고: 50%의 입력은 간단한 구조로, 모든 영역은 직사각형 형태를 가지고 영역 내에 펜스가 없다.

오직 하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이 때, 개똥벌레가 파괴해야하는 장애물의 최소값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최소값과 그러한 구간의 수를 공백으로 구분하여 출력한다.