TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)

A번

n이 주어졌을 때 아래를 만족하는 자연수 (x, y)를 찾는 문제이다.

 

 

n이 짝수면 (1, n/2)이다.

n이 홀수면 정답은 존재하지 않는다.

 

B번

a를 모두 곱한 것을 A라고 한다. p[0] = 0

(a[i], p[i])를 pi에 대해 정렬하고 1부터 n까지 정답에 A*(p[i] - p[i-1])을 더해주고 A를 a[i]로 나누는 것을 반복하면 풀린다.

 

C번

dp로 풀린다.

아이디어1: a[i]를 최대한 큰 값과 작은 값의 합으로 표현한다.

p: y[i+1]

dp[i][s] = min(dp[i-1][0] + maxvalue*p, dp[i-1][1] +minvalue*p) 

 

D번

dfs문제이다.

 

어려워요

잘 풀고 싶어진다