Codeforces Round #538 (Div. 2) A ~ C

codeforces.com/contest/1114

Dashboard - Codeforces Round #538 (Div. 2) - Codeforces

 

 

풀은 문제: A, B

못 풀은 문제: C, D, E, F

풀이만 보고 풀은 문제: 

풀이와 코드를 보고 풀은 문제: C

 

 

난이도

A - 800

B - 1500

C - 1700

D - 1900

E - 2200

F - 2400

 

 

 

17분동안 풀고 그 이후로 풀은 문제가 없다.

 

수학 들어가면 문제가 어려운 것 같다.

 

 

 

 

 

A. Got Any Grapes?

 

Andrew, Dmitry, Michal과 초록색 포도, 보라색 포도, 검은색 포도가 있다.

Andrew는 초록색 포도만 먹는다.

Dmitry는 초록색 포도와 보라색 포도만 먹는다.

Michal은 다 좋아한다.

 

이때 Andrew, Dmitry, Michal이 먹고 싶은 포도의 수를 각각 a, b, c로 입력받고, 초록색 포도와 보라색 포도, 검은색 포도의 개수를 각각 x, y, z로 입력 받을 때, 세 명 전부 원하는 포도의 수에 맞게 먹을 수 있는지 구하는 문제이다.

 

일단 Andrew는 초록색 포도만 먹으니 a > x이면 'NO'

Dmitry는 초록색 포도와 보라색 포도만 먹는데, Andrew가 먹고 남은 초록색 포도의 개수를 세서 b > (x+y) - a이면 'NO'

Michal은 전부다 좋아하므로 모든 포도의 수에 Andrew와 Dmitry가 먹은 포도의 수를 빼서 c > (x+y+z) - a - b이면 'NO'

이고 이렇게 3개의 if문을 통과하면 YES를 출력하게 만들면 된다.

 

def main():
    def NO():
        print('NO')
        exit()
    x,y,z = map(int,input().split())
    a,b,c = map(int,input().split())
    if x > a:NO()
    a -= x
    if y > a + b:NO()
    k = (a+b)-y
    if z > k + c:NO()
    print('YES')

 

 

B - Yet Another Array Partitioning Task

 

n개로 이루어진의 수열 a를 k개의 구역으로 쪼갤 때, 각 구역에 있는 가장 큰 수부터 m번째로 큰 수까지의 합들을 모두 더하여 출력하고, 마지막 구역을 제외한 각 구역의 마지막 숫자의 index를 출력하면 되는 문제이다.

 

이건 그냥 [a[i], i]로 구성된 배열 D를 하나 만들어서 내림차순이나 오름차순으로 정렬하여 제일 큰 수부터 k*m번째로 큰 수까지 있는 구역으로 D를 수정시킨다음 index번호로 오름차순으로 정렬하면 끝이다.

 

왜냐하면 beauty의 값은 제일 큰 수여야하므로 무조건 a배열의 제일 큰 수부터 k*m번쨰로 큰 수까지의 합이다.

이제 이걸 구역으로 나누자면 저 숫자들로 구역을 짜맞춰서 예를 들어서 m=2라고하면 [...,1번째로 큰 수,..., 2번째로 큰 수], [...,3번째로 큰 수, ... , 4번째로 큰 수], .... , [ ....., k*m-1번째로 큰 수,..., k*m번째로 큰 수,....]로 짜맞춰주면 된다.

이러면 출력할 때 짝수번째로 큰 수의 인덱스만 출력하면 되므로 편하다.

 

def main():
    n,m,k = map(int,input().split())
    a = [*map(int,input().split())]
    D = []
    for i in range(n):
        D.append([a[i],i])
    D = sorted(D)[len(D)-m*k:]
    D.sort(key = lambda z: z[1])
    val = 0
    for i in range(len(D)):
        val += D[i][0]
    ans = []
    for i in range(m-1,len(D)-1,m):
        ans.append(D[i][1]+1)
    print(val)
    print(*ans)

 

 

 

 

 

C. Trailing Loves (or L'oeufs?)

 

n!을 b진법으로 변환하였을때, 맨뒤에서부터 연속되는 0의 개수를 구하는 문제이다.

 

이건 처음 알았는데, b가 소수 일 때 n!을 b로 몇 번 나눌 수 있는지 확인할 수 있는 함수를 f(n, b)라고두면 f(n, b) =  n//b + f(n//b, b)라고 하고, 소수가 아니라면 b를 소인수 분해를 하여 얻은 값들을 모음을 x배열이라고 할 경우 min(f(n, x[i])/(x[i]의 지수))로 하면 된다는 것이다.

 

그래서 일단 b를 소인수분해를 하여 소인수와 지수를 배열에 저장해두고, 배열의 크기만큼 for문을 돌려서 while문으로 f(n, b) = f(n//b, b)를 구한다.

그리고 미리 준비해둔 변수 ans = 무한대로 ans = min(ans, f(n, x[i]/(x[i]의 지수))로 ans의 값을 업데이트하면 된다.

 

def main():
    n, b = map(int,input().split())
    i = 2
    prime = []
    while i**2 <= b:
        x,y = i,0
        while b % i == 0:
            y += 1
            b //= i
        if y: prime.append([x,y])
        i += 1
    if b > 1: prime.append([b,1])
    ans = float('inf')
    for D in prime:
        x, y, z = D[0], D[1], 0
        i = x
        while i <= n:
            z += n // i
            i *= x
        ans = min(ans, z // y)
    print(ans)

 

팩토리얼 문제가 나온다면 충분히 자주 나올만한 방법 같다.