A. Nastya and an Array$\!$배열이 주어지는데 하나의 연산을 할 수있다. 배열에 0이 아닌 모든 값에 똑같은 숫자를 더하거나 뺄 수 있다. 그렇게 모든 배열이 0이 되면 멈추는데, 최소연산 횟수를 구하는 문제다. 한번에 연산마다 하나의 숫자를 0으로 바꿀 수 있다. 배열이 똑같은 숫자를 가지면 똑같은 숫자도 모두 0이 되므로 distinct한 숫자의 개수를 세어주면 된다. 숫자가 작으니 bool형 배열로 깔끔하게 처리가능하고, 느리지만 set으로 해도 가능하다. B. Nastya Studies Informatics어떤 수 $a, b$의 $gcd$가 $x$이고, $lcm$이 $y$이다. $a, b$의 범위가 $[l, r]$이다. $l, r, x, y$가 주어졌을 때 가능한 $a, b$쌍의..
A. A Blend of Springtime $\!$꽃 $A, B, C$가 한 줄로 피어있다. 꽃이 시들면 꽃이 있던 위치와 그 양 옆 한 자리에 꽃잎이 떨어진다. 꽃잎이 모두 떨어졌을 때, 한 위치에라도 $A, B, C$의 꽃잎이 모두 떨어져 있으면 Yes를 아니면 No를 출력하는 문제다. 문제 그대로 구현하면 된다. 꽃잎 3개가 모두 있는지 판단하기 위해 배열 3개를 쓸 필요 없이 bit로 처리해주면 하나의 배열로 간단하게 처리 가능하다. B. A Tide of Riverscape$1, 0, '.'$으로 이루어진 기록이 있다. '.'은 각각 0이나 1롤 바꿀 수 있다. 그리고 정수 $p$가 주어지는데 이 정수는 주어진 기록의 주기이다. 여기서 '주기'란 모든 $0
A. Commentary Boxes총 $m$개의 참가팀에게 경품상자를 주는데 $n$개의 상자가 있다. 모든 참가팀에게 동등하게 나누어 주어야하므로 상자수는 $m$으로 나누어 떨어져야만한다. 그러기 위해서 $n$개의 상자 중 몇 개를 버릴 수 있고, 또는 몇 개를 더 만들 수도 있다. 만드는데 드는 비용 $a$와 버리는데 드는 비용 $b$이 주어질 때 $상자수 % m$이 0이 되기위한 최소 비용을 구하는 문제다. 문제 그대로 $(n \% m) * b$와 $(n - (n \% m)) * a$의 최소값을 구하면 된다. B. Micro-World접시에 $n$마리의 박테리아가 살고 있다. 박테리아들은 서로를 잡아먹을 수 있는데, $i$박테리아의 크기 $a_i$가 $j$박테리아의 크기 $a_j$에 대해 $a_i >..
A. Tetriscolumn이 $n$인 맵에서 테트리스를 한다. 테트리스의 블럭은 항상 $1 * 1$짜리가 들어온다. 블럭이 떨어지는 column이 전부 주어지면 총 지워지는 줄 수를 출력하는 문제다. 풀이는 생략. 문제제목을 안 보고 문제부터 읽었는데 문제이해가 너무 어려웠다. 테트리스의 규칙자체를 전부 설명하다보니 이해가 잘 안 됬는데 문제 풀고나니 문제제목이 보여서 실소가 났다. B. Lecture Sleep강의를 듣는데 총 $n$분 듣는다. 매 $i_{th}$분 마다 $a_i$개의 공식을 교수님이 설명해준다. 강의중간에 졸게 되는 경우가 있는데, $t_i$가 1이면 $i_{th}$분에 깨어있는 것이고, 0이면 $i_{th}$분에 졸고 있는 것이며 공식을 듣지 못한다. 강의 중간에 딱 한 번 $k$..
A. Chess Placing$1*n$크기의 체스판이 있다.($n$은 짝수) 체스판은 검흰검흰검흰...순서로 색칠되어있다. 정확히 $n / 2$개의 돌이 체스판위에 놓여져있다. 이 돌들을 움직여서 모두 같은 색깔위에 놓이게 하고싶다. 모두 검정색위에 놓이든 흰색위에 놓이든 상관없다. 이때 돌들이 움직이는 거리의 합의 최소값을 구하는 문제다. 모두 검정칸에 놓는 경우와 흰색칸에 놓는 경우 두 경우를 모두 해보아야한다. 검정칸이든 흰색칸이든 첫 번째 색깔칸에는 가장 왼쪽에 있는 돌이 가야 최소다. 두 번째 색깔칸에는 가장 왼쪽에서 두 번째 있는 돌이 가야 최소다. 난 엄청 복잡하게 풀었는데 풀이보니 엄청 간단하게 풀었다.두 번 틀렸는데 첫 번째는 조금 복잡하게 푸는 바람에 초기에 들어온 돌들은 다른 배열에 ..
A. Infinity Gauntlet인피니티스톤의 색깔이 입력으로 들어오면 앞으로 더 모아야하는 인피니티스톤의 이름을 출력하는 문제다. 넘어가자. B. High School: Become Human$x$와 $y$가 주어진다. $x^y$와 $y^x$의 값을 비교해야하는 문제다. $1 2, 2 -> 4, 5 - > 3, 1 -> 4, 5 -> 3 으로 graph를 만들 수 있고, (1, 2, 4) 와 (3, 5)가 사이클을 이룸을 알 수 있다. cycle내에서는 cycle의 크기 - 1 만큼 swap하면 정렬된 순열을 만들 수 있으므로 $n - 사이클의 개수$가 최소 swap횟수이다.최소 swap횟수를 알았으면 petr인지 Um_nik인지 알 수 있는데, 사이클의 개수 $k$라 하고, 먼저 $n$이 홀일 때..
A. Equator$\!$ 배열이 주어지면, 배열의 값을 더하다가 지금까지 더한 값이 배열값의 총 합 $/ 2$ 보다 크거나 같을때 그 index를 출력하는 문제이다. 설명필요없다. B. Students in Railway Carriage 일렬의 좌석이 주어지고, 컴공생과 체대생이 자리에 앉으려한다. 컴공생은 컴공생옆에 앉지 못 하며, 체대생은 체대생옆에 안지 못 한다. 이때 최대한 앉을 수 있는 학생수를 구하는 문제다. 앉을 수 있는 자리 component를 각각 보자. component의 크기가 짝수이면 아무렇게나 서로 건너 앉으면 된다. component가 홀수 이면 컴공생이나 체대생 중 많은 숫자먼저 앉고 건너 앉으면 최대로 앉을 수 있다. 자리가 *...*일때 $a, b$가 1, 2라고 하면 *..
A. Splits $\!$ 숫자 $n$이 주어진다. $n$의 영혼은 증가하지않는 양의 정수의 수열을 의미하고, 이 수열의 합은 $n$이다. 영혼의 무게는 영혼의 가장 첫 번째 원소(즉, 가장 큰 수)와 같은 원소의 개수를 의미한다. 이때, $n$의 영혼의 무게의 개수를 구하는 문제다. 문제를 딱 보고 이거 너무 어려운데? 생각했는데 예제를 보니 간단하게 풀린다는걸 알 수 있었다. 모든 수 $n$에 대해 무게가 1인 영혼은 무조건 존재한다. $[n]$의 수열이 있으니까. 무게가 2인 영혼은? $[n / 2, n / 2]$ 또는 $[n / 2, n / 2, 1]$이 있으면 있을 것이다. 무게 3.. 4.. 모두 마찬가지로 $[n / k .... n / k, 1,1...1,1,1]$로 만들 수 있다.(1은 $..
A. Row $\!$ 0과 1로 이루어진 string이 주어지는데, 1이 인접해 있거나 1을 인접하게 하지 않고 0 자리에 1을 넣을 수 있으면 No를, 그 외에는 Yes를 출력하는 문제이다. 문제에서 얘기한 대로 구현하면 된다. 문제에서 Yes인 경우를 "maximal"하다고 표현했는데 아마 이 표현때문에 많은 사람이 헷갈렸을 것이다.(물론 나도) 1이 최대로 포함되어있지 않은 경우도 문제조건만 맞으면 Yes를 출력하면 된다. 예를들어서 01010 같은 경우는 10101이여야 1이 최대가 되지만 01010에서 1이 인접하지않고, 또한 1을 넣을 수 없으므로 Yes다. B. Bus of Characters distinct한 배열과 0과 1로 이루어진 string이 주어진다. string을 순서대로 돌며 ..
A. Minimum Binary Number $\!$ 1과 0으로 구성된 문자열에 두 가지 연산을 할 수 있다. 인접한 두 문자의 자리를 바꾸거나, 인접한 두 1을 한 개의 1로 바꿀 수 있다. 이 문자열을 2진 숫자로 본다고 했을 때, 두 연산을 잘 사용하여 가장 작은 숫자로 바꾸어서 출력하는 문제이다. 인접한 두 문자의 자리를 바꾼단 말은 문자를 자유로이 움직일 수 있단 말과 같다. 따라서 모든 1을 왼쪽으로, 모든 0을 오른쪽으로 몰아넣으면 인접한 1은 한 개의 1로 바꿀 수 있으므로 1이 1개로 바뀔것이다. 더 이상 1을 없앨 수 없으므로 이때의 숫자가 가장 작은 숫자가 된다. 따라서 0의 개수만 세고난 뒤, 1 한 번 출력, 0의 개수만큼 0을 출력 해주면 된다.예외가 하나 있는데 0이 들어오는..
