qjatn0120

A. We Need the Zero code 길이가 \(N\)인 배열이 주어진다. 이제 이 배열의 모든 값에 특정 \(x\)를 XOR해서 배열의 모든 원소를 XOR한 값이 0이 될 수 있는지 확인하고 싶다. 가능하면 XOR 결과가 0이 되도록 하는 \(x\)를, 불가능하면 -1을 출력해야 한다. XOR을 많이 다뤘다면 빠르게 풀 수 있는 문제이다. XOR의 가장 큰 특징은 \(a \oplus x \oplus x = a\)라는 점이다. 일단 처음 주어진 배열의 모든 원소의 XOR값을 \(A\)라 하고, 모든 원소에 \(x\)를 XOR하자. 만약 \(N\)이 짝수라면 모든 원소의 XOR값은 여전히 \(A\)일거고, \(N\)이 홀수라면 XOR값은 \(A \oplus x\)가 될 것이다. 따라서 \(N\)이 ..

들어가기에 앞서 올 해부터 대학원 생활을 시작했는데, 아무래도 밤 늦게 있는 코포를 치면 시간표가 망가지게 된다... 그래서 학기 중 평일 밤 늦게 있는 코포는 거의 안칠 것 같다. A. Alternately code H와 F로 이루어진 문자열이 주어진다. 이웃하는 두 문자가 같은 경우가 있으면 No, 아니면 Yes를 출력하면 된다. 단순 for문 문제이다. B. Chessboard code 8x8 체스판에 말이 딱 하나 존재한다. 말이 없는 칸은 점(.), 있는 칸은 별(*)로 주어진다. 말의 위치를 A4, D5와 같은 형식으로 출력해야 한다. 행과 열 번호를 구하고, 이에 대응하는 알파벳 + 숫자 조합을 출력하면 된다. C. Gap Existence code 길이가 \(N\)인 정수 배열이 주어진다...

A. Garland code 색깔이 있는 전구가 4개 주어진다. 4개의 전구는 모두 꺼져있다. 각 전구의 색깔은 0이상 9이하의 정수로 표현된다. 이제 4개의 전구를 하나씩 스위치(킨 전구를 끄거나 꺼져있는 전구를 키는 것)해서 모두 킬 것이다. 그런데 연속해서 같은 색깔의 전구를 스위치할 수는 없다. 최소 몇 번의 스위치를 해야 모든 전구를 킬 수 있는지 출력하면 된다. 만약 모든 전구를 킬 수 없으면 -1을 출력하면 된다. 일단 모든 전구의 색깔이 같으면 모든 전구를 킬 수 없다. 만약 세 전구의 색깔이 똑같고 나머지 하나가 다르다면, 총 6번 스위치를 해야 모든 전구를 킬 수 있다. 그 이외의 경우에는 4번의 스위치만으로도 모든 전구를 킬 수 있다. 따라서 모든 전구의 색깔이 같으면 -1, 세 전구..

처음으로 codechef에 가입하고 대회를 쳐보았다. 처음에는 Div 4.에서 치라길래 싱글벙글 빨리풀고 잘 생각으로 쳤는데, 생각보다 오래걸렸다;; 시간 남으면 Div 4. 이외의 문제들도 풀어보려고 했는데, 한 문제에서 너무 시간을 많이 잡아먹어서 Div 4. 문제만 푸는 선에서 마쳤다. Candy Division code \(N\)을 입력받아 3으로 나눈 나머지가 0이면 YES, 아니면 NO를 출력하라는 문제이다. 그냥 하면 된다. Reach Home code \(x, y\)를 입력받아 \(5x \ge y\)이면 YES, 아니면 NO를 출력하라는 문제이다. 역시 그냥 하면 된다. Min To Max code 길이가 \(N\)인 배열 \(A\)가 주어진다. \(A\)의 minimum 값을 \(M\)이..

A. Plus or Minus code \(a\), \(b\), \(c\)가 주어진다. \(a + b = c\) 또는 \(a - b = c\)를 만족한다. 둘 중 어느것을 만족하는 지 출력하면 된다. 문제에서 시키는대로 하면 된다. B. Grab the Candies code \(N\)개의 가방이 있고, \(i\)번째 가방에는 \(a_i\)개의 사탕이 있다. 이제 가방을 특정한 순서대로 열 것이다. 만약 가방에 짝수 개의 사탕이 있다면, Mihai가 그 가방에 있는 사탕을 모두 가진다. 반대의 경우에는 Bianca가 모두 가져간다. 이제 가방을 여는 순서를 잘 배열해서 처음부터 모든 가방을 열 때까지 항상 Mihai가 Bianca보다 사탕을 많이 가지고 있도록 하게 하고 싶다. 가능하면 Yes, 불가능하..

항상 앳코더랑 코포는 계속 참가했는데 풀이를 쓰는 게 귀찮아서 계속 블로그를 방치하고 있었다. 너무 블로그를 방치하는 거 같아서 이제부터 대회 이후 간단히라도 쓰려고 한다. A. Filter code 길이가 \(N\)인 배열을 입력받은 뒤 짝수인 원소만 출력하면 되는 문제이다. 문제에서 시키는대로 하면 된다. B. ASCII Art code \(H\times W\)크기의 정수 배열을 입력받는다. 각 배열은 0이상 26 이하의 정수이다. 각 정수 \(x\)를 \(x\)번째 대문자 알파벳으로 치환하여 출력하고, \(x\)가 0이면 마침표로 치환하려 출력하면 된다. 역시 문제에서 시키는대로 하면 된다. C. Merge Sequences code 길이가 \(N\), \(M\)인 두 배열 \(A\), \(B\)가..

A. Medium Number code 문제 설명 3개의 수를 입력받아 중앙값을 출력해야 한다. 알고리즘 세 수를 정렬하고, 2번째 숫자를 출력하였다. B. Atilla's Favorite Problem code 문제 설명 주어진 문자열을 적을 때, 1번째 알파벳인 a부터 몇 번째 알파벳까지 사용해야 하는지를 출력해야 한다. 알고리즘 문자열 \(s\)에 있는 모든 문자 \(c\)에 대해 \(c - 'a' + 1\)의 최댓값을 출력하면 된다. C. Advantage code 문제 설명 길이가 \(n\)이고 각 원소가 정수인 배열이 주어진다. 모든 원소에 대해 자신에서 자신을 제외한 값들 중 최대인 값을 뺀 결과를 구해 출력해야 한다. 알고리즘 먼저 최댓값을 가지는 원소를 하나 찾는다. 해당 원소를 제외한 ..

A. The Ultimate Square code 문제 설명 총 \(N\)개의 직사각형이 있다. \(i\)번째 직사각형은 세로의 길이가 1이고, 가로의 길이가 \([\frac{N}{2}]\)이다. \(N\)개의 직사각형을 회전시키지 않고 만들 수 있는 가장 큰 정사각형의 한 변의 크기를 출력해야 한다. 알고리즘 먼저 \(2N\)개의 직사각형이 있다고 하자. 이 \(2N\)개의 직사각형을 서로 다른 \(N\)개 직사각형 묶음으로 쪼개자. 그렇다면 각 묶음은 \(1 \times 1\) 크기의 직사각형부터 \(1 \times N\) 크기의 직사각형까지 총 \(N\)개의 서로 다른 모양의 직시각형이 있다. 이 \(N\)개의 직사각형을 아래와 같이 계단 모양으로 배열해보자. \(2N\)개의 직사각형으로는 위 계단..

A. ^{-1} code 문제 설명 길이 \(N\)의 순열과 정수 \(X, 1 \le X \le N\)이 주어진다. \(A_i = X\)를 만족하는 \(i\)를 찾아 출력해야 한다. 알고리즘 for문으로 탐색하면서 \(A_i = X\)를 찾아 출력하면 된다. B. Playing Cards Validation code 문제 설명 길이가 2인 문자열이 \(N\)개 주어진다. 이 \(N\)개의 문자열이 카드 묶음에 해당하는 지를 출력해야 한다. 카드 묶음이란 각 문자열이 카드에 해당해야 하고 모든 카드가 서로 달라야 한다. 알고리즘 먼저 각 문자열이 카드에 해당하는 지를 검사하고, 이후 set과 같은 자료구조를 이용해 중복이 있는지를 확인하면 된다. C. Ladder Takahashi code 문제 설명 \(..

A. Indirect Sort code 문제 설명 길이가 \(n\)이고 1부터 \(n\)까지 한 번만 등장하는 배열이 입력으로 주어진다. \(1\le i a_k\)이면 \(a_i\)에 \(a_j\)만큼 더하고, 그렇지 않다면 \(a_j\)와 \(a_k\)를 swap한다. 여러 번의 연산을 통해 배열을 오름차순으로 정렬할 수 있는지 여부를 출력해야 한다. 알고리즘 이 문제는 배열의 첫 번째 원소에 집중하면 빠르게 풀 수 있다. 먼저 배열의 첫 번째 원소가 1이라 가정하자. 그렇다면 \(i = 1\)을 고르면, 두 번째 원소부터 마지막 원소까지 원하는 대로 변경할 수 있어 무조건 바꿀 수 있다. 하지만 첫 번째 ..