공작소

문제 아날로그 다이얼이란 0부터 9까지 각 숫자 중 하나를 항상 표시하고 있는 작은 기계이다. 다이얼에는 화면에 보이는 숫자를 1 증가시킬 수 있는 버튼도 있다. (9를 1 증가시키면 0이 된다) 상근이는 이러한 아날로그 다이얼을 N개 가지고 있고, 모두 책상에 일렬로 올려 놓았다. 왼쪽 기계부터 1번기계이며, 가장 오른쪽 기계는 N번 기계이다. 또, 기계의 앞에 무엇인가를 작성할 수 있도록 종이 두 장을 놓았다. 가장 처음에 상근이는 다이얼에 보이는 숫자를 첫 번째 종이에 적는다. 그 다음 다음과 같은 행동을 M번 반복한다. 1. 두 정수 A와 B를 고른 다음, 첫 번째 종이에 작성한다. (1 ≤ A ≤ B ≤ N) 2. A번째 다이얼부터 B번째 다이얼에 적혀있는 숫자의 합을 구한 다음에 두 번째 종이..

문제 최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을 잡고자 인기있는 N개의 DVD들로 구성된 시리즈를 구매한다(각 DVD들은 0번부터 N-1 까지 이루어져 있다). ACM 대여점의 주인 원주연 또한 울며 겨자먹기로 인기있는 시리즈물을 구매했고, 진열을 하기 위해 맞춤형 선반을 주문제작 하였다(맟춤제작이기 때문에 선반의 번호 또한 0번부터 N-1 까지 이루어져 있다). 주연이는 매우 정갈한 사람이기 때문에 DVD를 진열할 때 i번 DVD는 i번 선반에 진열을 한다. 이 시리즈의 열렬한 팬인 민호는 주연이네 대여점에 시리즈가 입고되었다는 소식을 듣고 찾아왔다. 시리즈물은 연속으로 봐야 흥미가..

문제 In Oddland, the leader of the country is determined by a democratic election. The country is divided into an odd number of regions, in which each region has an odd number of voters. There are two (an even number!) political parties in Oddland, and the winning party is the one that wins the most number of regions. A party wins a region if it receives more votes than the other party in that reg..

문제 1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라. 입력 첫째 줄에 수열 원소의 개수 (1 ≤ N ≤100,000)이 주어진다. 그리고 두 번째 줄부터 N+1 번째 줄까지 차례로 A[i]가 주어진다. 출력 N개의 줄에 걸쳐서 수열을 출력한다. (i번째 줄에는 i번째 원소를 의미한다) 풀이 과정 1부터 시작해서, 1보다 큰 수들이 앞에 최소한 A[1] 개 있다, 2보다 큰 수들이 앞에 최소한 A[2] 개 있다, 이런 식으로 수열을 작은 수부터 차례대로 배치한다. 모든 노드를 1로 설정하고 수를 배치했으면 0으로 바꿔 몇 번째에 수를 배치해야 하..

문제 За участието в национално състезание върху тениската на всеки спортист е бродирана малка буква от латинската азбука, която е отличителният му знак. На различните състезатели е бродирана различна буква. Напишете програма sport, която намира всички начини за класиране на състезателите и за всяко класиране отпечатва подредбата на буквите от екипите им. 입력 На стандартния вход се въвеждат малки бу..

문제 대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다. 대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다) 고속도로가 서로 교차하는 곳에는 휴게소를 지으려고 한..

문제 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다. 모든 올바른 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다. '('와 ')'로 이루어진 괄호 문자열 S = s1s2...sN과 M개의 쿼리가 주어진다. 쿼리는 두 정수 i, j (1 ≤ i ≤ j ≤ N)로 이루어져 있고, 쿼리가 의미하는 것은 다음과 같다. S의 부분 문자열 SiSi+1...Sj가 올바른 괄호 문자열이면 1, 아니면 0 모든 쿼리를 수행하고, 쿼리의 결과를 누적한 값을 구해보자. 입력 첫째 줄에 문자열 S가 주..

문제 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. 입력 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000) 셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 1번 쿼리의 경우 1 ≤ i ≤ N, 1 ≤ v ≤ 1,000,000 이고, 2번 쿼리의 경우 1 ≤ i ≤ j ≤ N이고, 0 ≤ k ≤ (쿼리가 주어..

문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다. 입력 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |..

문제 그래프 G는 정점의 집합 V와 간선의 집합 E로 이루어져 있고, G = (V, E)로 나타낸다. 대부분의 경우에 V와 E는 명시되어 있다. 일부 그래프의 경우에는 집합이 명시되어 있지 않다. 예를 들어, 순열 그래프는 간선의 집합이 명시되어 있지 않다. {1, 2, 3, 4, 5}로 이루어진 두 순열 (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)가 있다. 평행선을 그리고, 그 위에 순열에 적힌 숫자 순서대로 정점을 그린다. 그 다음 같은 숫자끼리 선분을 연결한다. 아래 그림과 같이 교차하는 선분의 쌍은 총 여섯 개라는 것을 알 수 있다. 교차하는 쌍은 순열 그래프의 간선이 된다. 순열 그래프의 정점은 숫자가 되고, 간선은 교차하는 쌍이 된다. 위의 예를 이용해 순열 그래프를 만들면 V ..