본문 바로가기

PS/Educational Codeforces

 (12)
Educational Codeforces Round 011 A. Co-prime Array 문제 https://codeforces.com/contest/660/problem/A Problem - A - Codeforces codeforces.com 문제요약 n개의 수열이 주어질 때 수열 내의 임의의 인접한 두 수의 gcd가 1이 아닌 경우 사이에 수들을 넣어 수열 전체에서 임의의 인접한 두 수의 gcd가 모두 1이 되도록 만든다. 풀이 앞에서부터 보면서 인접한 두 수의 gcd가 2이상일 때 사이에 1을 넣는걸 반복한다. 소스코드 #include using namespace std; typedef long long ll; int gcd(int a,int b){ if(a%b==0) return b; return gcd(b,a%b); } int main(){ int n, k=0, a; int v[1..
Educational Codeforces Round 010 A. Gabriel and Caterpillar 문제 https://codeforces.com/contest/652/problem/A Problem - A - Codeforces codeforces.com 문제요약 가브리엘 친구가 애벌레 관찰하는데 낮시간(10am~10pm)은 한시간에 a cm씩 오르고 밤시간엔 b cm씩 내려간다. 현재 h1 cm위치에 있고, h2 cm위치에 가고싶을 때 며칠 걸리는지 알아보자. 처음 시작은 2pm이다. 풀이 a
Educational Codeforces Round 009. A A. Grandma Laura and Apples 문제 https://codeforces.com/contest/632/problem/A Problem - A - Codeforces codeforces.com 문제요약 할머니가 사과를 파는데 half로 팔면 절반 딱 떨어지게 팔고 halfplus로 팔면 홀수개라 자투리는 선물로 주는 상황 사과 하나 값(항상 짝수)이 주어질 때 판 번 돈(사과개수X사과값) 구하기 (반쪽을 팔수도 있음) 풀이 half면 짝수개일 때 딱 떨어지게 절반 팔았고 halfplus면 홀수개일 때 덤을 줬다는 말 즉 뒤에서부터 보면서 계산하면 됨 개수에 대해서 halfplus면 +1 후 2배 아니라면 그냥 2배하면서 판 사과개수 확인 단 개수가 클 수 있으므로 long long을 쓸 것..
Educational Codeforces Round 008. A A. Tennis Tournament 문제 https://codeforces.com/contest/628/problem/A Problem - A - Codeforces codeforces.com 문제요약 토너먼트식 경기를 한다. 사람 수가 n일 때 k=2^i1;n-=k>>1){ for(k=2; k
Educational Codeforces Round 007. A A. Infinite Sequence 문제 https://codeforces.com/contest/622/problem/A 문제요약 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ... 의 규칙으로 나열되는 수열의 n번째 수는 얼마인가? ex) 55번째는 10이다. 풀이 n(n+1)/2번째 수는 n이다. 그리고 그 이후 n+1개 수만큼 나열된다. 즉 55번째를 구하려면 45번째 이후부터 10개의 수가 각각 1, 2, 3, ~, 10임을 알고 10을 찾으면 된다. 수 범위가 10^14이므로 long long을 써주자 소스코드 #include typedef long long ll; int main(){ ll n, k; scanf("%lld",&n); for(k=1; k*(k..
Educational Codeforces Round 006. A A. Professor GukiZ's Robot 문제 https://codeforces.com/contest/620/problem/A Problem - A - Codeforces codeforces.com 문제요약 2차원 좌표상에서 시작점과 끝점을 받는데, 한 점에서 8방향으로 갈 수 있다고 할 때 시작점에서 끝점까지 몇 번만에 갈 수 있는가? 풀이 8방향이므로 x축 distance가 a, y축 distance가 b일 때 min(a,b)만큼은 대각선으로 간 후 abs(a-b)만큼은 x축이든 y축으로 직선으로 가면 시작점에서 끝점에 도달할 수 있다. 소스코드 #include int abs(int a){ return a
Educational Codeforces Round 005. A A. Comparing Two Long Integers 문제 https://codeforces.com/contest/616/problem/A 문제요약 긴 문자열 두개 a, b를 입력받아 정수로 나타냈을 때 어느게 더 큰지 나타내라 풀이 간단하게 둘 다 0이아닌곳부터 시작해서 우선 길이가 더 큰거 비교해서 대소 나타내고 길이가 같다면 반목문 돌면서 앞에서부터 각 문자 중 더 큰거 비교해서 대소를 나타낸다. 마지막까지 같다면 '=' 출력 소스코드 #include #include char a[1100000], b[1100000]; int main(){ scanf("%s\n%s",a,b); int x=0, y=0, n, m; n = strlen(a); m = strlen(b); for(;a[x] && a[x]=..
Educational Codeforces Round 004. A A. The Text Splitting 문제 https://codeforces.com/contest/612/problem/A Problem - A - Codeforces codeforces.com 문제 요약 n, p, q를 입력받고 n개 길의 문자를 p, q개 문자들로 쪼개어 그 개수 및 단어들을 출력한다 풀이 i) Naive Solution 반복문 돌면서 k = 1, 2, ... 에 대해 ( n - k * p ) % q == 0인 경우를 찾아 첫줄에 k + ( n - k * p ) / q, 둘째줄부터 p단어씩 k개 q단어씩 ( n - k * p ) / q개 출력한다. 이때의 시간복잡도는 대강 O(n)이라 할 수 있다. ii) Faster Solution 조금 더 빠른 방법이 없는가 생각해봤는데 디오판토..

티스토리툴바