Problem:


Score : 700 points

Problem Statement

Takahashi is playing with N cards.

The i-th card has an integer X_i on it.

Takahashi is trying to create as many pairs of cards as possible satisfying one of the following conditions:

The integers on the two cards are the same.

The sum of the integers on the two cards is a multiple of M.

Find the maximum number of pairs that can be created.

Note that a card cannot be used in more than one pair.

Constraints

2≦N≦10^5

1≦M≦10^5

1≦X_i≦10^5

Input

The input is given from Standard Input in the following format:

N M
X_1 X_2 ... X_N

Output

Print the maximum number of pairs that can be created.

Sample Input 1

7 5
3 1 4 1 5 9 2

Sample Output 1

3

Three pairs (3,2), (1,4) and (1,9) can be created.

It is possible to create pairs (3,2) and (1,1), but the number of pairs is not maximized with this.

Sample Input 2

15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99

Sample Output 2

6



Sample input:
7 5
3 1 4 1 5 9 2


Sample output:
3

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
x=map(int,raw_input().split())
cnt=[0]*(max(x)+1)
for i in xrange(n):
    cnt[x[i]]+=1
samemod=[0]*m
for i in xrange(n):
    samemod[x[i]%m]+=1
ans=0
for i in xrange((m+1)/2):
    if i==0:
        ans+=samemod[0]/2
        samemod[0]=0
    else:
        ans+=min(samemod[i],samemod[m-i])
        if samemod[i]>=samemod[m-i]:
            samemod[i]-=samemod[m-i]
            samemod[m-i]=0
        else:
            samemod[m-i]-=samemod[i]
            samemod[i]=0
if (m+1)%2==1:
    ans+=samemod[(m+1)/2]/2
    samemod[(m+1)/2]=0
mp=[[] for _ in xrange(m)]
for i in xrange(1,max(x)+1):
    mp[i%m].append(cnt[i])
for i in xrange(m):
    mp[i].sort()
    mp[i].reverse()

for i in xrange(m):
    for j in xrange(len(mp[i])):
        if mp[i][j]>=2:
            if samemod[i]>=mp[i][j]:
                ans+=mp[i][j]/2
                if mp[i][j]%2==0:
                    samemod[i]-=mp[i][j]
                else:
                    samemod[i]-=mp[i][j]-1
            else:
                ans+=samemod[i]/2
                samemod[i]=0
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
n, m = map( int, raw_input().strip().split() )
data = map( int, raw_input().strip().split() )

ans = 0

freq1 = [0] * ( max( data ) + 1 )
for x in data:
	freq1[ x ] += 1

freq2 = [0] * m
freq3 = [0] * m

for i in range( len( freq1 ) ):
	freq2[ i % m ] += freq1[i]
	freq3[ i % m ] += 2 * ( freq1[i] / 2 )

for i in range(m) :
	if ( i + i ) % m == 0:
		ans += freq2[i] / 2
	else:
		mx = 0
		val = min( freq2[i], freq2[m-i] )
		ans += val
		ans += min( freq3[i], freq2[i] - val ) / 2
		ans += min( freq3[m-i], freq2[m-i] - val ) / 2
		freq2[i] = freq2[ m-i ] = 0
		freq3[i] = freq3[ m-i ] = 0

print ans

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
x=map(int,raw_input().split())
d={}
for i in xrange(m):
    d[i] = []
for i in xrange(n):
    d[x[i]%m].append(x[i])
c=0
c+=len(d[0])/2
if m%2==0:
    c+=len(d[m/2])/2
for i in xrange(1,(m-1)/2+1):
    a=d[i]
    b=d[m-i]
    if len(a)==len(b):
        c+=len(a)
    elif len(a)<len(b):
        b=sorted(b)
        tmp=0
        i=0
        while i<len(b)-1:
            if b[i] == b[i+1] and len(a)<=len(b)-(tmp+1)*2:
                tmp+=1
                i+=1
            i+=1
        c+=tmp+len(a)
    else:
        a=sorted(a)
        tmp=0
        i=0
        while i<len(a)-1:
            if a[i] == a[i+1] and len(b)<=len(a)-(tmp+1)*2:
                tmp+=1
                i+=1
            i+=1
        c+=tmp+len(b)

print c

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, M = map(int, raw_input().split())
X = map(int, raw_input().split())

cnt = [0]*100005
for x in X:
    cnt[x] += 1

pair = [0]*M
for i in xrange(100005):
    pair[i%M] += cnt[i]/2
    cnt[i] %= 2

mod = [0]*M
for i in xrange(100005):
    mod[i%M] += cnt[i]

ans = sum(pair)
for i in xrange(M):
    if i == 0 or i == M - i:
        ans += mod[i]/2 
        mod[i] %= 2
    else:
        m = min(mod[i], mod[M - i])
        ans += m
        mod[i] -= m
        mod[M - i] -= m

for i in xrange(1, M):
    while pair[i] >= 1 and mod[M - i] >= 2:
        ans += 1
        pair[i] -= 1
        mod[M - i] -= 2


print ans

Submission status: Accepted

Solution code:
import numpy as np
import collections

N, M = map(int, raw_input().split())
X = map(int, raw_input().split())

dupM = np.zeros(M, dtype='int')
modM = np.zeros(M, dtype='int')

# count dup
X_count = collections.Counter(X)
for x in X_count.keys():
    dupM[x % M] += int(X_count[x] / 2)
# count mod
for x in X:
    modM[x % M] += 1

res = 0
for m in range(M):
    if m == 0:
        res += int(modM[m] / 2)
    elif 2*m < M:
        res += min(modM[m], modM[M-m])
        if modM[M-m] < modM[m]:
            res += min(int((modM[m] - modM[M-m]) / 2), dupM[m])
        else:
            res += min(int((modM[M-m] - modM[m]) / 2), dupM[M-m])
    elif 2*m == M:
        res += int(modM[m] / 2)
    else:
        pass
print res

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, M = map(int, raw_input().split())
X = map(int, raw_input().split())

cnt = [0]*100005
for x in X:
    cnt[x%M] += 1

ans = 0
for i in xrange(M):
    if i == M - i:
        ans += cnt[i]/2
        print "=", cnt[i]
        cnt[i] %= 2
    else:
        m = min(cnt[i], cnt[M - i])
        print min(cnt[i], cnt[M - i])
        ans += m
        cnt[i] -= m
        cnt[M - i] -= m
for i in xrange(M):
    ans += cnt
print ans