Educational Codeforces Round 104 (Rated for Div. 2)후기/풀이

후기 : 

수학대회라 2솔만 하자 했었는데 3솔이나 해서 기분이 좋았지만 b랑 c에서 어이없는 실수를 너무 해서 아쉽다.

D는 배웠는데 생각이 안 나서 못 푼 게 아쉽고 일단 3솔해서 좋지만 좀 아쉬운 대회였다.

 

풀이 :

A

A는 요약하면 우승할 수 있는 사람 수다. 그러므로 정렬을 한 다음 가장 작은 값들을 제거하고 남은 값들은 모두 우승할 수 있다.

import sys,math,queue
#sys.setrecursionlimit(10**9)
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    l.sort()
    g=0
    for i in range(1,n):
        if l[i-1]!=l[i]:
            print(n-i)
            g=1
            break
    if g==0:print(0)

B

뇌절은 너무 많이 해서 아쉬운 문제이기도 하다.

이문제는 규칙을 찾아서 풀면 되는데

 

5 4 3 2 1/5 4 3 2 1/5 4 3 2 1/5 4 3 2 1/5 4 3 2 1/5 4 3 2 1/5 4 3 2 1/5 4 3 2 1
1 2 4 5 2/3 5 1 3 4/1 2 4 5 2 3 5 1 3 4/1 2 4 5 2 3 5 1 3 4/1 2 4 5 2 3 5 1 3 4/

6 5 4 3 2 1/6 5 4 3 2 1/6 5 4 3 2 1/6 5 4 3 2 1/6 5 4 3 2 1/
1 2 3 4 5 6 1 2 3 4 5 6

7 6 5 4 3 2 1/7 6 5 4 3 2 1/7 6 5 4 3 2 1/7 6 5 4 3 2 1/7 6 5 4 3 2 1/
1 2 3 5 6 7 2 3 4 6 7 1 3 4 5 7 1 2 4 5 6 2 3 4 5 6 7 2 3 4 5 6 7 1 2

1 2 3/5 6 7/2 3 4/6 7 1/3 4 5/7 1 2/4 5 6/2 3 4 5 6 7/2 3 4 5 6 7 1 2

3 2 1/3 2 1/3 2 1/3 2 1/3 2 1/
1 3 2 1 3 2 1 3 2 1 3 2

9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/
1 2 3 4 6 7 8 9 2 3 4 5 7 8 9 1 3 4 5 6 8 9 1 2 4 5 6 7 9 1 2 3 5 6 7 8 1 2 3 4 6 7 8 9  

이게 규칙이다.(대회 노가다 해서 알아냈다)

일단 짝수일 때 보면 짝수는 절대 겹치는 일이 없다 그러므로 k에 n을 나눈 나머지만 출력하면 되고

홀수 일 때는 

7 6 5 4 3 2 1/7 6 5 4 3 2 1/7 6 5 4 3 2 1/7 6 5 4 3 2 1/7 6 5 4 3 2 1/

1 2 3/5 6 7/2 3 4/6 7 1/3 4 5/7 1 2/4 5 6/1 2 3/5 6 7/2 3 4/6 7 1/3 4

이걸 보면 /는 겹쳐서 한 번 더 앞으로 간 위치인데 이 위치가 3칸씩 일정하게 있다.

그러면 텀이 3이라고 생각할 수 있지만 아니다.

9를 보면

9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/9 8 7 6 5 4 3 2 1/
1 2 3 4/6 7 8 9/2 3 4 5/7 8 9 1/3 4 5 6/8 9 1 2/4 5 6 7/9 1 2 3/5 6 7 8/1 2 3 4/6 7 8 9/2

이렇게 되는데 9는 4칸씩 일정하게 있다.

그리고 5는 2칸씩 있다.

이때 텀의 크기는 n의 홀수번째-1이다. 5는 3번째 홀수고 -1을 해서 텀이 2고 7은 3,9는 4,11는 5.... 이렇게 된다.

이게 k랑 텀을 나눠서 k만큼 움직였을 때 겹쳐도 그냥 갔을 때 나오는 위치에 더 앞으로 가야 되는 값(위에서 구했던 거)을 더해주고 n으로 나눠주면 된다.

 

import sys,math,queue
#sys.setrecursionlimit(10**9)
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n,k=map(int,input().split())
    if n==3:
        if k%3==1:print(1)
        elif k%3==2:print(3)
        else:print(2)
    elif n%2==0:print((k-1)%n+1)
    else:
        #print("#",k%n,k//n)
       # k//((n//2)+1)
        #print(min(n,k//(n//2)))
        print(((k%n-1)+(k-1)//(n//2))%n+1)

 (3은 고치기 전에 따로 해준 거뿐 없애도 상관없다)

C

C는 숫자들의 값이 모두 같으면서 무승부인 횟수를 최소로 해야 된다.

이문제는 생각보다 간단한데 N(N-1)/2개의 숫자들이 모두 1이었을 경우

N이 6일 때

 

15 12 9 6 3 0

숫자들은 이렇게 된다.

숫자들의 값이 모두 같으면서 무승부인 횟수를 최소로 해야 된다.

이때 1번 팀에서 6번 팀이랑 했을 때 이겼던 거를 진거로 바꿔주면

 

12 12 9 6 3 3

이렇게 된다.

이제 또 5번 팀이랑 했을 때 이겼던 거를 진거로 바꿔주면

9 12 9 6 6 3

이 된다.

이때 홀수와 짝수일 때가 좀 다른데 N이 짝수일 때는 무승부가 무조건 들어간다. 이때 1번과 4번이 무승 부였다로 바꿔주면

7 12 9 7 6 3이 되고

이제 2번이랑도 해줘서

7 9 9 7 6 6,

7 7 9 7 7 6

그리고 3번도 6번이랑 무승부로 바꿔주면

7 7 7 7 7 7로 무승부 횟수가 3번이므로 최소가 된다.

 

홀수일 경우는

 

12 9 6 3 0

일 때

똑같이 하는데 대신 마지막에 무승부를 안 해도 된다.

9 9 6 3 3

6 9 6 6 3

6 6 6 6 6

이렇게 바꿔줘서 무승부 횟수가 최소로 할 수 있다.

이제 값이 모두 1일 때 절반 씩 바꿔주면 되는데

절반인 이유는 값이 초기 값들의 평균이 넘으면 안 되기 때문이다.

이제 코드를 짜면 된다.

import sys,math,queue
#sys.setrecursionlimit(10**9)
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    k=n//2
    if n%2!=0:
        for i in range(n-1):
            for g in range(i+1,n):
                if g+k>=n:
                    print(-1,end=" ")
                else:
                    print(1,end=" ")
            k-=1
    else:
        for i in range(n-1):
            for g in range(i+1,n):
                if g+k==n:
                    print(0,end=" ")
                elif g+k>=n:
                    print(-1,end=" ")
                else:
                    print(1,end=" ")
            k-=1
    print()

 

 

D

D도 생각하지 못해서 많이 아쉬웠다.

 

다른 분의 코드를 보면 이렇게 된다.

생각보다 많이 간단한데 생각을 못한 게 너무 아쉽다ㅜㅜ

#import<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
LL i,j,k,m,n,t,a[200040];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(cin>>t;t--;)
    {
        cin>>n;
        cout<<int((sqrt(2*n)-1)/2)<<endl;
    }
}