본문 바로가기

문제 풀이/Codeforces

문제 풀이/Codeforces 2020. 8. 3. Codeforces Round #660 (Div. 2) A - Captain Flint and Crew Recruitment Problem - A - Codeforces codeforces.com 정수 \(n\)이 주어진다. nearly prime은 서로 다른 두 소수의 곱으로 나타낼 수 있는 정수를 말한다. \(n\)을 서로 다른 4개의 양의 정수의 합으로 나타내야 하는데, 그 중 적어도 3개가 nearly prime일 수 있는지 여부를 알아내고, 가능하다면 실해를 출력해야 한다. 가장 작은 3개의 nearly prime인 6, 10, 14와 \(n-30\)을 하면 일반적으로 답이다. \(n-30\)이 6, 10, 또는 14와 같거나 양의 정수가 아닐 경우 각각 예외처리를 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..
문제 풀이/Codeforces 2020. 7. 30. Educational Codeforces Round 92 A - LCM Problem Problem - A - Codeforces codeforces.com 정수 \(l, r\)이 주어진다. \(l \le x \lt y \le r\)을 만족하면서, \(l \le LCM(x,y) \le r\)을 만족하는 \(x,y\)가 존재하는지 알아내고, 존재한다면 출력해야 한다. 서로 다른 \(x,y\)에 대해서, \(LCM(x,y)\)가 가장 작아지는 경우는 \(y = 2x\)인 경우이다. \(2l \le r\)이면 \(l, 2l\)을 출력하면 되고, 그렇지 않다면 불가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef unsigned long l..
문제 풀이/Codeforces 2020. 7. 22. Codeforces Round #658 (Div. 1, Div. 2) A - Common Subsequence Problem - A - Codeforces codeforces.com \(n\)길이의 수열 \(a\)와 \(m\)길이의 수열 \(b\)가 주어진다. 두 수열의 길이가 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 34 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll..
문제 풀이/Codeforces 2020. 7. 18. Codeforces Round #656 (Div. 3) A - Three Pairwise Maximums Problem - A - Codeforces codeforces.com 세 정수 \(x,y,z\)가 주어진다. 이 때, 다음을 만족하는 세 정수가 존재하는지 여부를 알아내고, 존재한다면 출력해야 한다. \(x = \max(a,b)\), \(y = \max(a,c)\), \(z = \max(b,c)\) 먼저, \(a,b,c\)중 가장 큰 수를 \(a\)라고 가정하자. 그러면 \(x,y,z\)중 두 수는 \(a\)여야 한다. 따라서 \(x,y,z\)중 두 수가 같고 (이를 \(x,y\)라고 가정하자), \(z\)가 \(x,y\)보다 크지 않다면 해가 존재하며, 해는 \(x, z, 1\)이다. 그렇지 않다면 해가 없다. 1 2 3 4 5 6 7 8 9 10 1..
문제 풀이/Codeforces 2020. 7. 12. Codeforces Round #655 (Div. 2) A - Omkar and Completion Problem - A - Codeforces codeforces.com 어떤 배열 \(a\)의 원소가 1000이하인 양수이고, 어떤 세 인덱스 \(x,y,z\)에 대해서도 \(a_x + a_y = a_z\)를 만족하지 않는다면, 이 배열을 complete하다고 한다. 주어진 \(n\)에 대해, complete한 \(n\)길이의 배열 하나를 출력해야 한다. 모든 원소가 같은 배열은 위 조건을 만족한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll..
문제 풀이/Codeforces 2020. 7. 5. Codeforces Global Round 9 A - Sign Flipping Problem - A - Codeforces codeforces.com \(n\)이 홀수인 배열 \(a\)가 주어진다. \(n\)은 홀수이다. 배열의 원소의 부호를 원하는대로 바꿀 수 있는데, 결과가 다음을 만족해야 한다. 인접한 원소의 차이를 \(a_{i+1} - a_i\)로 정의할 때, 1. 적어도 \(\frac {n-1}{2}\)개의 인접한 원소의 차이는 양수여야 한다. 2. 적어도 \(\frac {n-1}{2}\)개의 인접한 원소의 차이는 음수여야 한다. 홀수번째 원소는 양수, 짝수번째 원소는 음수로 바꾸면 위 조건을 무조건 만족한다. (반대도 물론 가능하다) 양수에서 음수를 빼면 무조건 양수, 음수에서 양수를 빼면 무조건 음수이기 때문이다. 1 2 3 4 5 6 ..
문제 풀이/Codeforces 2020. 7. 3. Codeforces Round #654 (Div. 2) A - Magical Sticks Problem - A - Codeforces codeforces.com 각 \(1\)부터 \(n\)까지의 길이를 가지는 막대가 하나씩 있다. 이 막대를 2개씩 붙여 새로운 막대를 만들 수도 있을 때, 같은 길이를 가지는 막대들의 최대 개수를 구해야 한다. 길이 \(1\)과 \(n-1\)인 막대, \(2\)와 \(n-2\)인 막대... 를 각각 붙여 \(n\) 길이의 막대를 만드는 것이 최선임을 알 수 있다. 따라서 답은 \(\lceil \frac n2 \rceil\)이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std; typedef long long ll; typede..
문제 풀이/Codeforces 2020. 6. 24. Codeforces Round #652 (Div. 2) A - FashionabLee Problem - A - Codeforces codeforces.com 어떤 정다각형을 좌표평면 위에 놓았을 때, 이 정다각형을 회전시켜서 X축과 평행한 변과 Y축과 평행한 변이 동시에 있을 수 있다면 이 정다각형을 아름답다고 하자. \(n\)이 주어지면, 정 \(n\)각형이 아름다운지 여부를 알아내야 한다. \(n\)이 4로 나눠 떨어지면 이 정다각형은 아름답다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b;..

티스토리툴바