[코드포스 - 2] 929 Div.3 A, B, C 풀이

A. Turtle Puzzle: Rearrange and Negate (1분)

가능한 연산은 다음과 같습니다.

• 수열 $a$를 임의로 재정렬
• $1 \leq l \leq r \leq n$인 구간에 대해 부호를 바꿈. (음수 -> 양수, 양수 -> 음수)

재정렬이 가능하므로 음수를 한쪽에 몰아넣고 음수들의 모든 부호를 바꾸면 됩니다.
입력으로 음수가 들어오면 양수로 바꿔주면 됩니다.

B. Turtle Math: Fast Three Task (8분)

$a$의 합을 3으로 나눈 나머지가 $0$이 되도록 다음 연산을 반복해서 수행할 수 있습니다.

• $a$의 임의의 원소를 제거
• $a$의 임의의 원소에 $1$을 더함

따라서 다음 경우로 나눠볼 수 있습니다.

• 현재 합의 나머지가 $0$인 경우
  • 연산이 필요 없습니다. 따라서 정답은 $0$입니다.
• 현재 합의 나머지가 $1$인 경우
  • 3으로 나눈 나머지가 1인 원소를 제거하는 방법
    • 이때의 연산 횟수는 $1$입니다.
  • 3으로 나눈 나머지가 1인 원소가 없는 경우 
    • 1을 2번 더해주면 됩니다. 이때의 연산 횟수는 $2$입니다.
• 현재 합의 나머지가 $2$인 경우
  • 나머지가 $2$인 원소를 제거하나, $1$을 임의의 원소에 더해도 연산 횟수는 $1$로 동일합니다.

 

C. Turtle Fingers: Count the Values of k (26분)

$a$, $b$, $l$이 주어질 때, $a^x \times b^y \times k = l$인 중복되지 않는 $k$의 개수를 구하는 문제입니다.

$1 \leq l \leq 10^{6}$이고, $2 \leq a,b \leq 100$이므로 $2^{20}$이 $a^x$, $b^y$가 가질 수 있는 최댓값입니다.
따라서 $x, y = 0$부터 $x, y = 20$까지 2중 반복문을 통해 $k$를 set등에 넣어 개수를 구해주면 됩니다.

이때 주의할점은, 식이 $\displaystyle k = \frac{l}{a^x \times b^y}$가 되는데 단순히 나눠서는 소숫점이 절삭되기 때문에 나머지가 $0$인지 먼저 체크해주어야 합니다.

 

레이팅 변화

1218 -> 1219(+1)