https://codeforces.com/contest/1497/problem/C1
https://codeforces.com/contest/1497/problem/C2
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 104)
- n k (3 ≤ n ≤ 109, k)
output :
- For each test case print k positive integers a1, a2, ..., ak, for which all conditions are satisfied.
각 테스트 케이스에서 조건을 만족하는 k개의 숫자를 출력하시오.
조건 :
-
Find k positive integers a1, a2, ..., ak, such that:
a1 + a2 + ... + ak = n
LCM(a1, a2, ..., ak) ≤ n // 2
k개의 양수를 찾으시오. 모든 원소들을 더했을 때 n이 되는 것과 최소공배수가 n // 2보다 작거나 같은 것으로. -
Here LCM is the least common multiple of numbers a1, a2, ..., ak
LCM의 경우 최소공배수를 의미함.
3을 제외하고 가장 작은 최소공배수를 만드려면 어떻게 해야 할까?
우선적으로 3개로 나눠져야 할 것이다.
모두 동일한 값으로 주는 것도 당연히 작아지겠지만 모든 경우에 이것을 설정할 수 없다.
특정 숫자를 4 k로 나타낼 때, 4 k + 1, 4 k + 2, 4 k + 3으로 규칙적으로 나타낼 수 있다. 이 때 이 숫자들을 3개로 나눈다 한다면
[k, k, 2 * k][2 * k, 2 * k, 1]
[2 k, 2 k, 2][2 * k + 1, 2 * k + 1, 1]
로 규칙적으로 나타낼 수 있다.
직관적으로 느낌을 받지 못하면 어렵지 않을까 싶다. 그래서 어려웠고 ㅋㅋㅋㅋㅋㅋㅋㅋ
hard 버젼의 경우 k를 3으로 만든다는 생각으로 나머지를 1로 만들고 나서 그 값을 easy버젼에서 구한 코드를 사용한다.
import sys
for _ in range(int(sys.stdin.readline())):
n, a = map(int, sys.stdin.readline().split())
ans = [1] * (a - 3)
num = n - (a - 3)
temp = []
if num == 3:
temp = [1, 1, 1]
else:
k = num // 4
if num % 4 == 0:
temp = [k, k, 2 * k]
elif num % 4 == 1:
temp = [2 * k, 2 * k, 1]
elif num % 4 == 2:
temp = [2 * k, 2 * k, 2]
else:
temp = [2 * k + 1, 2 * k + 1, 1]
ans += temp
print(*ans)
