본문 바로가기

문제 풀이/Codeforces

문제 풀이/Codeforces 2020. 5. 15. Codeforces Round #642 (Div. 3) A - Most Unstable Array Problem - A - Codeforces codeforces.com 정수 \(n\)과 \(m\)이 주어진다. 길이가 \(n\)이고 원소들의 합이 \(m\)인 수열을 만들려고 한다. 각 원소는 모두 0 이상인 정수이다. 이때 각각의 인접한 원소의 차의 합이 최대값을 알아내야 한다. 먼저 \(n\)이 1일 때 답은 0이고, \(n\)이 2일 때 답이 \(m\)임은 쉽게 알 수 있다. \(n\)이 3 이상일 때는 \(\{0,m,0,0,\cdots\}\) 와 같이 수열을 만들었을 때 \(2m\)이 답이 되고, 이보다 값이 큰 경우는 존재하지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #incl..
문제 풀이/Codeforces 2020. 5. 13. Codeforces Round #641 (Div. 1, Div. 2) A - Orac and Factors Problem - A - Codeforces codeforces.com \(n \ge 2\)에 대해 \(f(n)\)을 \(n\)의 1이 아닌 가장 작은 약수로 정의하자. 어떤 수 \(n\)이 주어지고 이 수에 \(f(n)\)을 더하는 작업을 \(k\)번 반복했을 때, 결과값을 출력해야 한다. \(n\)이 짝수라면, \(f(n)\)은 항상 2이다. \(n\)이 홀수라면, \(f(n)\)은 항상 홀수인데, 홀수에 홀수를 더하므로 그 다음 값은 짝수가 된다. 따라서 맨 처음만 \(f(n)\)을 구해서 더해준 다음, \(2(k-1)\)을 더해주면 답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2..
문제 풀이/Codeforces 2020. 5. 10. Codeforces Round #640 (Div. 4) A - Sum of Round Numbers Problem - A - Codeforces codeforces.com 양의 정수 \(n\)이 주어진다. 어떤 양의 정수가 가장 큰 자리수를 제외한 숫자가 모두 0일 때, 이 정수를 round라고 한다. \(n\)을 가장 적은 수의 round의 합으로 나타내야 한다. 당연하게도 모든 자리수의 숫자들을 분리하면 답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ..
문제 풀이/Codeforces 2020. 5. 8. Codeforces Round #639 (Div. 1, Div. 2) A - Puzzle Pieces Problem - A - Codeforces codeforces.com 퍼즐 조각 하나가 주어진다. 이 퍼즐 조각을 \(n\)행 \(m\)열로 늘어 놓을 때, 맞닿는 면이 서로 완벽히 맞도록 할 수 있는지 알아내야 한다. 먼저 행이나 열이 1개라면, 무조건 가능함이 자명하다. 그렇지 않다면, 행과 열이 각각 2개인 경우를 제외하고는 만드는 것이 불가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; ..
문제 풀이/Codeforces 2020. 5. 4. Codeforces Round #638 (Div. 2) A - Phoenix and Balance Problem - A - Codeforces codeforces.com 무게가 \(2^1, 2^2, \dots, 2^n\)인 동전 \(n\)개가 있다. \(n\)은 짝수이다. 이 동전을 \(\frac n2\)개 씩 두 묶음으로 나눠서 두 묶음의 동전의 무게의 차가 최소가 되도록 해야 한다. 무게가 \(2^n\)인 동전 하나가 나머지 동전의 무게를 다 합친 것보다 무게가 많이 나간다. 따라서 \(2^n\)동전 하나와 가장 무게가 가벼운 동전 \(\frac n2 - 1\)개를 한 묶음으로 하고, 나머지 동전을 한 묶음으로 하면 최적이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ..
문제 풀이/Codeforces 2020. 4. 27. Educational Codeforces Round 86 A - Road To Zero Problem - A - Codeforces codeforces.com 두 수 \(x, y\)가 주어진다. 이 두 수중 하나에 1을 더하거나 빼는 연산을 하는데 \(a\)의 비용이, 둘 다 1을 더하거나 빼는 연산을 하는데 \(b\)의 비용이 든다. 두 수를 모두 0으로 만들기 위한 최소 비용을 구해야 한다. \(b > 2a\) 라면 두번째 연산을 할 필요가 없다. 그렇지 않다면, 두번째 연산을 \(min(a,b)\)번 해서 둘 중 하나를 0으로 만든 다음, 나머지 수에 첫번째 연산을 해서 0으로 만들면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #i..
문제 풀이/Codeforces 2020. 4. 24. Codeforces Round #637 (Div. 1, Div. 2) A - Nastya and Rice Problem - A - Codeforces codeforces.com \(n\)개의 쌀알이 있다. 쌀알 하나의 무게는 최소 \(a-b\) 최대 \(a+b\)이고, 쌀알 전체의 무게는 최소 \(c-d\) 최대 \(c+d\)이다. \(n,a,b,c,d\)가 주어질 때, 이 값들이 올바른지 알아내야 한다. 쌀알 전체의 무게를 \(a\)와 \(b\)를 이용해 나타내면 \([n\cdot (a-b), n\cdot (a+b)]\)가 된다. 이 범위가 \([c-d, c+d]\)와 한 점이라도 겹치면 올바른 값이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; t..
문제 풀이/Codeforces 2020. 4. 22. Codeforces Round #636 (Div. 3) A - Candies Problem - A - Codeforces codeforces.com 양의 정수 \(n\)이 주어진다. \(x+2x+4x+\cdots+2^{k-1}x=n\), (\(k \gt 1\))을 만족하는 \(x\)를 출력해야 한다. 단순히 가능한 모든 \(k\)에 대해 계수의 합을 만든다음 \(n\)이 나눠떨어지는지 확인하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll ..

티스토리툴바