https://codeforces.com/contest/1497/problem/B
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 1000)
- n, m (1 ≤ n, m ≤ 105)
- a1, a2, ..., an(1 ≤ ai ≤ 109)
output :
- For each test case print the answer to the problem.
각 문제에 대한 정답을 출력하시오.
조건 :
-
You should divide elements of this array into some arrays. You can order the elements in the new arrays as you want.
입력받은 배열을 부분 배열들로 나눠야 한다. 이 때 원소들을 임의로 정렬할 수 있다. -
Let's call an array m-divisible if for each two adjacent numbers in the array (two numbers on the positions i and i+1 are called adjacent for each i) their sum is divisible by m. An array of one element is m-divisible.
원소 기준으로 인접한 두 숫자의 합이 m으로 나누어 질 때 이 배열을 m - divisible이라 부른다.
인접한 두 숫자를 더했을 떄 m으로 나눠져야 한다.
그렇다면 숫자들도 경우가 존재하는데 m으로 나눴을 때 나오는 나머지를 통해 생각할 수 있다.
0인 경우에는 이 숫자들만 모으면 되니까 부분 배열은 1개가 된다.
1인 경우에는 m - 1짜리 숫자와
2인 경우에는 m - 2짜리 숫자와 ... 그렇게 한다.
그리고 하나의 원소만 있는 부분 배열도 이러한 배열로 치기 때문에 남는 원소의 개수도 기록이 되어야 한다.
다른 사람들의 경우 절대값의 계산과 가장 긴 부분 배열 1개를 빼서 남는 원소의 개수까지 한번에 계산을 하는데 이건 좀 헷갈려서 그냥 반복문을 수행했다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
num = [0] * m
for item in data:
num[item % m] += 1
ans = 0
if num[0] != 0:
ans += 1
num[0] = 0
for start in range(1, m // 2 + 1):
end = m - start
temp = min(num[start], num[end])
if temp != 0:
ans += 1
if start == end:
num[start] = 0
continue
if num[start] == num[end]:
num[end] -= temp
num[start] -= temp
continue
if num[start] == temp:
num[end] -= temp + 1
num[start] -= temp
else:
num[start] -= temp + 1
num[end] -= temp
ans += sum(num)
print(ans)
