A. Mishka and Contestps대회에 참가하는데 나의 ps스킬이 수치상으로 $k$이다. $k$보다 어려운 난이도의 문제는 풀지 못 한다. 문제를 효율적으로 풀기위해 왼쪽부터 $k$보다 작거나 같은 문제들을 풀다가 $k$보다 높은 난이도의 문제를 만나면 오른쪽부터 $k$보다 작거나 같은 문제들을 쭉 푼다. 다시 $k$보다 높은 난이도의 문제를 만나면 문제 풀기를 멈춘다. 총 푸는 문제 수를 구하는 문제다. for문 1개와 bool형 배열 하나면 해결된다. B. Reversing Encryption길이 $n$의 문자열 $s$를 암호화하는 방법은 $n$의 약수를 모두 구하고, 약수를 오름차순으로 정렬한 뒤 각 약수마다 $s$의 부분문자열 $s[1, d]$를 뒤집는다. 암호화된 문자열이 주어지면 문자..
A. Fingerprints0~9까지 적혀 있는 키패드가 있다. 수열과 키패드에 지문이 묻어있는 숫자가 주어진다. 비밀번호는 지문이 묻어있는 숫자들로 이루어져있고, 주어진 수열의 가장 긴 부분수열이다. 단, 부분수열은 연속적이지 않아도 된다. 이때 비밀번호를 구하는 문제다. 간단하다. 설명이 필요없다. B. Knights of a Polygonal Table검사들이 서로를 죽이는데, 자기보다 힘이 약한 기사만 죽일 수 있다. 헌데 검사들은 양심이 있어서 $k$명 초과로 죽이지 못 한다. 그리고 검사들은 다른 검사를 죽이고 나면 그 검사의 돈을 모두 가져올 수 있다. 각 검사가 얻을 수 있는 돈의 최대값을 구하는 문제다. 검사들의 power를 오름차순으로 정렬한 뒤 for문으로 올라가면서 가장 큰 $k$개..
A. Mahmoud and Ehab and the even-odd game먼저 내가 숫자 $n$을 선택하고, 상대방 부터 1보다 크거나 같고 $n$보다 작거나 같은 숫자 하나를 말해서 $n$에 뺀다. 나는 홀수만, 상대방은 짝수만 뺄 수 있는데, $n$에 뺄 숫자를 말 할 수 없는 경우 진다. 모두가 최선을 다해서 게임을 할 때 누가 이기는지 구하는 문제다. $n$이 홀수면 상대방먼저 얘기할 수 있으므로 $n$보다 작은 짝수를 뺄 것이다. 그러면 홀수가 남을 것이고, 내가 그 수를 빼버리면 0이 되어 상대방은 더 이상 수를 뺄 수 없으므로 내가 이긴다.$n$이 짝수면 상대방먼저 얘기할 수 있으므로 $n$을 얘기하면 바로 내가 진다. 따라서 $n$이 홀수면 내가, 짝수면 상대방이 이긴다. B. Mahmou..
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. 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. 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. Pizza, Pizza, Pizza!!! $\!$ $n$이 주어지면 피자를 칼로 균등하게 $(n + 1)$조각 시키려한다. 칼은 피자 도우부분에서 시작해서 도우까지 또는, 중간에 멈출 수도 있고, 중간에서 시작해서 중간에서 멈출수도 있다. 단, 직선으로만 잘라야한다. 칼질횟수를 구하여라. 정말 간단하다. $(n + 1)$이 짝수면 그냥 중간을 쑥 쑥 지나가게 잘라버리면된다. 한번 중앙을 가로지르는 칼질을 반복하면 한번 칼질에 같은 크기의 피자가 2개씩 나오기 때문이다. $(n + 1)$이 홀수면 중앙을 가로지르는 칼질로는 피자를 균등하게 자를수가 없다. 그냥 중앙에서 시작해서 $(n + 1)$번 잘라야 모두 같은 크기로 자를 수 있다. 너무 간단해서 2줄코딩했는데 $n$이 0일때 예외가 생겨버린다...
A. Help Farmer$\!$ $A*B*C$의 값이 주어졌을 때, $(A + 1) * (B + 2) * (C + 2) - A * B * C$의 값의 최대, 최솟값을 구하는 문제이다. $A*B*C$의 값은 상수이므로 $(A + 1) * (B + 2) * (C + 2)$를 결정해주면 되는데, $A*B*C$의 값 $n$의 약수를 모두 돌아보며 $A$, $B$의 값을 결정해주면 된다. ($A$, $B$가 결정되면 $C$는 알아서 결정되므로 고려할 필요가 없다.)2중 for문 으로 해결되는데, 약수를 결정하고나면 그 반대 쌍도 $A$나 $B$값으로 고려하여 체크해봐야한다.(예제를 돌려보면 무슨 뜻인지 이해가 갈 것이다.) 문제는 이게 시간내에 돌아가느냐인데.. 약수결정에 O($sqrt(n)$)이 걸리고, 또 ..
