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. Chess Placing$1*n$크기의 체스판이 있다.($n$은 짝수) 체스판은 검흰검흰검흰...순서로 색칠되어있다. 정확히 $n / 2$개의 돌이 체스판위에 놓여져있다. 이 돌들을 움직여서 모두 같은 색깔위에 놓이게 하고싶다. 모두 검정색위에 놓이든 흰색위에 놓이든 상관없다. 이때 돌들이 움직이는 거리의 합의 최소값을 구하는 문제다. 모두 검정칸에 놓는 경우와 흰색칸에 놓는 경우 두 경우를 모두 해보아야한다. 검정칸이든 흰색칸이든 첫 번째 색깔칸에는 가장 왼쪽에 있는 돌이 가야 최소다. 두 번째 색깔칸에는 가장 왼쪽에서 두 번째 있는 돌이 가야 최소다. 난 엄청 복잡하게 풀었는데 풀이보니 엄청 간단하게 풀었다.두 번 틀렸는데 첫 번째는 조금 복잡하게 푸는 바람에 초기에 들어온 돌들은 다른 배열에 ..
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은 $..
