3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

첫째 줄에 경우의 수를 출력한다.

아래 그림은 3×12 벽을 타일로 채운 예시이다.

방금 막 프로그래밍을 배우기 시작한 찬우는 acmicpc.net에 있는 회원들이 모두 신같이 보였다. 그래서 찬우는 모든 회원의 닉네임 앞에 ‘갓’을 붙이려고 한다.

찬우가 ‘koosaga’라는 닉네임을 가진 회원을 갓으로 바꿔 부른다면 ‘godsaga’가 된다. 또, 찬우가 ‘acka’라는 닉네임을 가진 회원을 갓으로 바꿔 부른다면 ‘godka’가 될 것이다. 찬우는 닉네임을 갓으로 바꾸는 알고리즘을 생각하다가, 아래와 같이 2단계 방법을 사용하면 될 것으로 생각했다.

• 닉네임을 음절 단위로 쪼갠다.
• 가장 첫 음절을 ‘god’으로 바꾼 후 쪼갠 음절을 합친다.

찬우는 수작업으로 N명의 닉네임을 모두 음절 단위로 쪼갰다. 찬우를 도와 이 닉네임들에 갓을 붙이는 프로그램을 작성하자.

첫 번째 줄에는 닉네임의 수 N(1 ≤ N ≤ 100)이 주어진다. 두 번째 줄부터 N개의 줄에는 음절 단위로 쪼갠 닉네임이 주어진다. 각 줄은 알파벳 소문자와 공백만으로 이루어지며, 쪼갠 닉네임의 총 길이(공백 포함)는 100을 넘지 않는다. 쪼갠 닉네임에는 1개 이상의 공백이 존재한다.

각 줄에 하나씩 갓을 붙인 닉네임을 출력한다.

창영이는 노래 여러 개를 이어서 부르는 가수이다. 유명한 노래의 비슷한 멜로디를 이어서 부르면서 언제 곡이 넘어갔는지 모르게 만드는 것이 창영이 노래의 특징이다. 이런 노래로 상업적으로 엄청난 성공을 거둔 창영이에게 큰 시련이 찾아왔다. 그것은 바로 저작권이었다.

창영이의 노래에 포함되어 있는 멜로디는 모두 저작권이 다른 사람에게 있는 노래이다. 따라서, 이 음악으로 상업적인 활동을 했기 때문에, 저작권 협회에 저작권료를 내야한다.

창영이는 자신의 앨범에 포함되어있는 저작권이 있는 멜로디의 평균값을 구해보기로 했다. 이 값은 아래와 같이 구할 수 있다.

(창영이 앨범에 수록된 곡에 포함되어 있는 저작권이 있는 멜로디의 개수) / (앨범에 수록된 곡의 개수)

이 때, 평균값은 항상 올림을 해서 정수로 만들어야 한다. 예를 들어, 창영이의 1집 앨범 "영창에서 영원히 영창피아노를 친다"에 총 38개 곡이 수록되어 있고, 이 앨범에 저작권이 있는 멜로디가 894개가 있다면, 평균값은 23.53이 되고 올림해서 24가 된다.

매니저 강산이는 얼마나 많은 사람에게 저작권료를 주어야 하는지 궁금해졌다. 강산이가 알고 있는 정보는 앨범에 수록되어 있는 곡의 개수와 위에서 구한 평균값이다. 이 때, 적어도 몇 곡이 저작권이 있는 멜로디인지 구하는 프로그램을 작성하시오.

첫째 줄에 앨범에 수록된 곡의 개수 A와 평균값 I가 주어진다. (1 ≤ A, I ≤ 100)

첫째 줄에 적어도 몇 곡이 저작권이 있는 멜로디인지 출력한다.

상근이는 2863번에서 표를 너무 열심히 돌린 나머지 5와 6을 헷갈리기 시작했다.

싱근이가 숫자 5를 볼 때, 5로 볼 때도 있지만, 6으로 잘못 볼 수도 있고, 6을 볼 때는, 6으로 볼 때도 있지만, 5로 잘못 볼 수도 있다.

두 수 A와 B가 주어졌을 때, 상근이는 이 두 수를 더하려고 한다. 이 때, 상근이가 구할 수 있는 두 수의 가능한 합 중, 최소값과 최대값을 구해 출력하는 프로그램을 작성하시오.

첫째 줄에 두 정수 A와 B가 주어진다. (1 <= A,B <= 1,000,000)

첫째 줄에 상근이가 구할 수 있는 두 수의 합 중 최소값과 최대값을 출력한다.

겨울 방학에 달에 다녀온 상근이는 여름 방학 때는 화성에 갔다 올 예정이다. (3996번) 화성에서는 지구와는 조금 다른 연산자 @, %, #을 사용한다. @는 3을 곱하고, %는 5를 더하며, #는 7을 빼는 연산자이다. 따라서, 화성에서는 수학 식의 가장 앞에 수가 하나 있고, 그 다음에는 연산자가 있다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄에는 화성 수학식이 한 줄에 하나씩 주어진다. 수학식은 100자를 넘지 않는다.

각 테스트 케이스에 대해서, 화성 수학식의 결과를 계산한 다음에, 소수점 둘째 자리까지 출력한다.

1부터 N - 1까지의 정수가 하나씩 정렬되지 않은 채로 저장되어 있는 어떤 수열 A가 있다. 수열 A에 임의의 정수 M(1 ≤ M ≤ N – 1)을 넣어 크기가 N인 수열로 만들었을 때, 임의의 정수 M을 찾는 프로그램을 작성하라.

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

둘째줄에 수열 A의 원소인 N개의 정수가 주어진다. 입력으로 주어지는 정수는 모두 1부터 N – 1 사이의 정수이며 문제의 답인 M을 제외하고는 모두 서로 다른 정수이다.

M을 출력하라.

프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다.  즉 한 번 주문에 막걸리 용량이 802ml 이기도 1002ml가 나오기도 한다.  은상은 막걸리 N 주전자를 주문하고, 자신을 포함한 친구들 K명에게 막걸리를 똑같은 양으로 나눠주려고 한다.  그런데 은상과 친구들은 다른 주전자의 막걸리가 섞이는 것이 싫어서, 분배 후 주전자에 막걸리가 조금 남아 있다면 그냥 막걸리를 버리기로 한다.  (즉, 한 번 주문한 막걸리에 남은 것을 모아서 친구들에게 다시 주는 경우는 없다.  예를 들어 5명이 3 주전자를 주문하여 1002, 802, 705 ml의 막걸리가 각 주전자에 담겨져 나왔고, 이것을 401ml로 동등하게 나눴을 경우 각각 주전자에서 200ml, 0m, 304ml 만큼은 버린다.) 이럴 때 K명에게 최대한의 많은 양의 막걸리를 분배할 수 있는 용량 ml는 무엇인지 출력해주세요.

첫째 줄에는 은상이가 주문한 막걸리 주전자의 개수 N, 그리고 은상이를 포함한 친구들 K명이 입력된다. N은 10000이하의 정수이고, K는 1,000,000이하의 정수이다. 막걸리의 용량은 231 -1 보다 작거나 같은 자연수이다. (단, 항상 N ≤ K 이다. 즉, 주전자의 개수가 사람 수보다 많을 수는 없다 ) .

첫째 줄에 K명에게 나눠줄 수 있는 최대의 막걸리 용량 ml 를 출력한다.

2번째 예제에서 205ml로 나눌 경우 2,2,3,4 가 된다. 하지만 206ml라고 하면 각각 2, 2, 2, 3 으로 나눌 수 있기 때문에 나누는 용량을 조금 줄여야한다.

야바위를 잘하는 재열이는 축제기간동안 홍문관 앞에 부스를 열어 돈을 벌어보려 한다. 

재열이는 컵 네 개를 일렬로 탁자 위에 올려놓고, 가장 왼쪽 컵에 작은 공 하나, 가장 오른쪽 컵에 큰 공 하나를 넣어놓았다. 이제 재열이는 컵 2개의 위치를 바꿔가면서 여러번 섞을 것이고, 모두 섞은 뒤에 상대방에게 어떤 컵에 공이 들어있는지 말하라고 할 것이다. 컵이 4개가 있을 때, 위치를 바꿀 수 있는 가능한 방법은 아래와 같이 6가지가 있다.

떼돈을 벌기 위해 3개월을 연습한 재열이에게 내기를 이길 수 있는 사람은 거의 없다.  그러나, 마침 엄청난 동체시력의 보유자 영범이 홍문관 앞을 지나고 있었다.  영범은 내기를 제안하고, 아무것도 모르는 재열이는 말없이 컵을 섞기 시작한다.  재열이의 손놀림이 아무리 빠르더라도, 영범이의 동체시력을 속일 수는 없다. 영범이는 동체시력뿐만 아니라, 기억력도 뛰어나서 재열이가 컵을 섞은 순서를 다 기억할 수 있다.  이것을 모르는 재열이의 운명은 당신이 작성할 프로그램에 달려있다.

재열이가 컵을 섞은 방법이 순서대로 주어질 때, 어떤 컵에 작은 공이 있는지, 어떤 컵에 큰 공이 있는지 차례대로 출력하는 프로그램을 작성하시오. 

첫째 줄에 재열이가 컵을 섞는 순서가 주어진다. 이 순서는 위 그림에 있는 A, B, C, D, E, F 중 하나이다. 재열이는 컵을 최대 200번 섞는다.

첫번째 줄에는 작은 공이 있는 위치를, 두번째 줄에는 큰 공이 있는 위치를 출력한다. 공의 위치는 가장 왼쪽부터 1, 2, 3, 4로 표시한다.  

홍익대학교 근처에 있는 오락실에 새로운 게임이 들어왔다. 이 게임을 클리어하려면 방금 막 금은방을 턴 마포구 대도 X가 되어 아무에게도 들키지 않고 X의 집에 무사히 도착해야 한다. 게임은 오직 좌우 버튼 두 개로만 진행되고 규칙은 아래와 같다.

1. 마포구의 모든 건물은 일렬로 나열되어 있고 각 건물에는 1번부터 N번까지 번호가 지정되어 있다. 마포구에는 K개의 경찰서가 있고 경찰 내부에는 이미 X의 얼굴이 알려졌다.
2. 게임이 시작될 때 X는 막 범행을 끝내고 금은방 S에 있다.
3. X는 자신의 집 D에 마포구를 떠날 수 있는 비밀 통로를 만들어놓았다. 따라서 경찰에게 발각되지 않고 무사히 집으로 돌아가야 한다.
4. 좌(←) 버튼을 누르면 후방으로, 우(→) 버튼을 누르면 전방으로 이동한다. X는 마포구 내에서만 이동할 수 있으며, 자신이 오랜 연구 끝에 알아낸 이동 방식을 맹신하여 오직 그 방식으로만 이동한다.
5. X의 달리기는 매우 빨라서 전방으로 F개의 건물, 후방으로 B개의 건물을 얼굴이 보이지 않는 빠르기로 달릴 수 있다. 하지만 자신도 주체할 수 없을 만큼 빨라서 중간에 멈출 수 없으며, 한 번 달리면 너무 힘들어 10초 동안 건물 앞에서 휴식을 취해야 한다.
6. X가 경찰서 앞에서 휴식을 취할 경우 그는 집에 돌아가지 못하고 체포된다.

이 게임은 아직 베타 버전이라 무사히 집으로 가는 방법이 없는 버그도 존재한다.

지언이의 취미는 오락실 게임을 누구보다 빠르게 클리어하는 것이다. 그래서 대도 X가 무사히 집에 도착할 수 있는 여러 방법 중에서도 좌우 버튼을 가장 최소로 눌렀을 때의 횟수를 알고 싶다.

마포구 건물의 개수 N, 털린 금은방 S, 빈집털이범의 집 D, 앞으로 한 번에 달릴 수 있는 건물 수 F, 뒤로 한 번에 달릴 수 있는 건물 수 B, 마포구 경찰서의 개수 K, 각 경찰서의 건물 번호 l1, l2, …, lK가 주어질 때 대도 X가 무사히 집에 도착하기 위해 버튼을 눌러야 하는 최소 횟수를 출력하는 프로그램을 작성해라.

만약 집으로 가는 방법이 없는 경우를 발견했다면 이 데이터를 게임 회사에 알리기 위해 “BUG FOUND”를 출력한다.

첫째 줄에 N, S, D, F, B, K가 주어지고, K > 0인 경우에는 둘째 줄에 경찰서의 위치 l1, l2, …, lK가 주어진다. (1 ≤ S, D, k ≤ N ≤ 100000, 0 ≤ F, B ≤ 100000, 0 ≤ K ≤ N/2, S ≠ D ≠ l) 

첫째 줄에 대도 X가 건물 S에서 자신의 집 D로 무사히 가기 위해 지언이가 버튼을 눌러야 하는 최소 횟수를 출력한다. 만약, D에 도달할 수 없는 데이터인 경우 “BUG FOUND”를 출력한다.

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
2. 입력의 갯수 N은 1 이상 500만 이하이다.

첫째 줄에 A1, A2, ..., AN이 주어진다.

B1, B2, ..., BN’을 출력한다.

메모리 제한에 유의하시오.