import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(2**27)
sys.setrecursionlimit(300000)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
class TreeNode:
def __init__(self, k, v):
self.key = k
self.value = v
self.left = None
self.right = None
self.parent = None
self.height = 1
self.num_left = 1
self.num_total = 1
class AvlTree:
def __init__(self):
self._tree = None
def add(self, k, v):
if not self._tree:
self._tree = TreeNode(k, v)
return
node = self._add(k, v)
if node:
self._rebalance(node)
def _add(self, k, v):
node = self._tree
while node:
if k < node.key:
if node.left:
node = node.left
else:
node.left = TreeNode(k, v)
node.left.parent = node
return node.left
elif node.key < k:
if node.right:
node = node.right
else:
node.right = TreeNode(k, v)
node.right.parent = node
return node.right
else:
node.value = v
return
@staticmethod
def get_height(x):
return x.height if x else 0
@staticmethod
def get_num_total(x):
return x.num_total if x else 0
def _rebalance(self, node):
n = node
while n:
lh = self.get_height(n.left)
rh = self.get_height(n.right)
n.height = max(lh, rh) + 1
balance_factor = lh - rh
n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
n.num_left = 1 + self.get_num_total(n.left)
if balance_factor > 1:
if self.get_height(n.left.left) < self.get_height(n.left.right):
self._rotate_left(n.left)
self._rotate_right(n)
elif balance_factor < -1:
if self.get_height(n.right.right) < self.get_height(n.right.left):
self._rotate_right(n.right)
self._rotate_left(n)
else:
n = n.parent
def _remove_one(self, node):
replacement = node.left or node.right
if node.parent:
if AvlTree._is_left(node):
node.parent.left = replacement
else:
node.parent.right = replacement
replacement.parent = node.parent
node.parent = None
else:
self._tree = replacement
replacement.parent = None
node.left = None
node.right = None
node.parent = None
self._rebalance(replacement)
def _remove_leaf(self, node):
if node.parent:
if AvlTree._is_left(node):
node.parent.left = None
else:
node.parent.right = None
self._rebalance(node.parent)
else:
self._tree = None
node.parent = None
node.left = None
node.right = None
def remove(self, k):
node = self._get_node(k)
if not node:
return
if AvlTree._is_leaf(node):
self._remove_leaf(node)
return
if node.left and node.right:
nxt = AvlTree._get_next(node)
node.key = nxt.key
node.value = nxt.value
if self._is_leaf(nxt):
self._remove_leaf(nxt)
else:
self._remove_one(nxt)
self._rebalance(node)
else:
self._remove_one(node)
def get(self, k):
node = self._get_node(k)
return node.value if node else -1
def _get_node(self, k):
if not self._tree:
return None
node = self._tree
while node:
if k < node.key:
node = node.left
elif node.key < k:
node = node.right
else:
return node
return None
def get_at(self, pos):
x = pos + 1
node = self._tree
while node:
if x < node.num_left:
node = node.left
elif node.num_left < x:
x -= node.num_left
node = node.right
else:
return (node.key, node.value)
raise IndexError("Out of ranges")
@staticmethod
def _is_left(node):
return node.parent.left and node.parent.left == node
@staticmethod
def _is_leaf(node):
return node.left is None and node.right is None
def _rotate_right(self, node):
if not node.parent:
self._tree = node.left
node.left.parent = None
elif AvlTree._is_left(node):
node.parent.left = node.left
node.left.parent = node.parent
else:
node.parent.right = node.left
node.left.parent = node.parent
bk = node.left.right
node.left.right = node
node.parent = node.left
node.left = bk
if bk:
bk.parent = node
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
node.num_left = 1 + self.get_num_total(node.left)
def _rotate_left(self, node):
if not node.parent:
self._tree = node.right
node.right.parent = None
elif AvlTree._is_left(node):
node.parent.left = node.right
node.right.parent = node.parent
else:
node.parent.right = node.right
node.right.parent = node.parent
bk = node.right.left
node.right.left = node
node.parent = node.right
node.right = bk
if bk:
bk.parent = node
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
node.num_left = 1 + self.get_num_total(node.left)
@staticmethod
def _get_next(node):
if not node.right:
return node.parent
n = node.right
while n.left:
n = n.left
return n
class SegmentTree1:
def __init__(self, data, default=-10**15, func=lambda a, b: max(a,b)):
self._default = default
self._func = func
self._len = len(data)
self._size = _size = 1 << (self._len - 1).bit_length()
self.data = [default] * (2 * _size)
self.data[_size:_size + self._len] = data
for i in reversed(range(_size)):
self.data[i] = func(self.data[i + i], self.data[i + i + 1])
def __delitem__(self, idx):
self[idx] = self._default
def __getitem__(self, idx):
return self.data[idx + self._size]
def __setitem__(self, idx, value):
idx += self._size
self.data[idx] = value
idx >>= 1
while idx:
self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
idx >>= 1
def __len__(self):
return self._len
def query(self, start, stop):
if start == stop:
return self.__getitem__(start)
stop += 1
start += self._size
stop += self._size
res = self._default
while start < stop:
if start & 1:
res = self._func(res, self.data[start])
start += 1
if stop & 1:
stop -= 1
res = self._func(res, self.data[stop])
start >>= 1
stop >>= 1
return res
def __repr__(self):
return "SegmentTree({0})".format(self.data)
class SegmentTree:
def __init__(self, data, default=10**15, func=lambda a, b: min(a,b)):
self._default = default
self._func = func
self._len = len(data)
self._size = _size = 1 << (self._len - 1).bit_length()
self.data = [default] * (2 * _size)
self.data[_size:_size + self._len] = data
for i in reversed(range(_size)):
self.data[i] = func(self.data[i + i], self.data[i + i + 1])
def __delitem__(self, idx):
self[idx] = self._default
def __getitem__(self, idx):
return self.data[idx + self._size]
def __setitem__(self, idx, value):
idx += self._size
self.data[idx] = value
idx >>= 1
while idx:
self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
idx >>= 1
def __len__(self):
return self._len
def query(self, start, stop):
if start == stop:
return self.__getitem__(start)
stop += 1
start += self._size
stop += self._size
res = self._default
while start < stop:
if start & 1:
res = self._func(res, self.data[start])
start += 1
if stop & 1:
stop -= 1
res = self._func(res, self.data[stop])
start >>= 1
stop >>= 1
return res
def __repr__(self):
return "SegmentTree({0})".format(self.data)
class Factorial:
def __init__(self, MOD):
self.MOD = MOD
self.factorials = [1, 1]
self.invModulos = [0, 1]
self.invFactorial_ = [1, 1]
def calc(self, n):
if n <= -1:
print("Invalid argument to calculate n!")
print("n must be non-negative value. But the argument was " + str(n))
exit()
if n < len(self.factorials):
return self.factorials[n]
nextArr = [0] * (n + 1 - len(self.factorials))
initialI = len(self.factorials)
prev = self.factorials[-1]
m = self.MOD
for i in range(initialI, n + 1):
prev = nextArr[i - initialI] = prev * i % m
self.factorials += nextArr
return self.factorials[n]
def inv(self, n):
if n <= -1:
print("Invalid argument to calculate n^(-1)")
print("n must be non-negative value. But the argument was " + str(n))
exit()
p = self.MOD
pi = n % p
if pi < len(self.invModulos):
return self.invModulos[pi]
nextArr = [0] * (n + 1 - len(self.invModulos))
initialI = len(self.invModulos)
for i in range(initialI, min(p, n + 1)):
next = -self.invModulos[p % i] * (p // i) % p
self.invModulos.append(next)
return self.invModulos[pi]
def invFactorial(self, n):
if n <= -1:
print("Invalid argument to calculate (n^(-1))!")
print("n must be non-negative value. But the argument was " + str(n))
exit()
if n < len(self.invFactorial_):
return self.invFactorial_[n]
self.inv(n) nextArr = [0] * (n + 1 - len(self.invFactorial_))
initialI = len(self.invFactorial_)
prev = self.invFactorial_[-1]
p = self.MOD
for i in range(initialI, n + 1):
prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
self.invFactorial_ += nextArr
return self.invFactorial_[n]
class Combination:
def __init__(self, MOD):
self.MOD = MOD
self.factorial = Factorial(MOD)
def ncr(self, n, k):
if k < 0 or n < k:
return 0
k = min(k, n - k)
f = self.factorial
return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
def powm(a, n, m):
if a == 1 or n == 0:
return 1
if n % 2 == 0:
s = powm(a, n // 2, m)
return s * s % m
else:
return a * powm(a, n - 1, m) % m
def sort_list(list1, list2):
zipped_pairs = zip(list2, list1)
z = [x for _, x in sorted(zipped_pairs)]
return z
def product(l):
por = 1
for i in range(len(l)):
por *= l[i]
return por
def binarySearchCount(arr, n, key):
left = 0
right = n - 1
count = 0
while (left <= right):
mid = int((right + left) / 2)
if (arr[mid] < key):
count = mid + 1
left = mid + 1
else:
right = mid - 1
return count
def countdig(n):
c = 0
while (n > 0):
n //= 10
c += 1
return c
def binary(x, length):
y = bin(x)[2:]
return y if len(y) >= length else "0" * (length - len(y)) + y
def countGreater(arr, n, k):
l = 0
r = n - 1
leftGreater = n
while (l <= r):
m = int(l + (r - l) / 2)
if (arr[m] >= k):
leftGreater = m
r = m - 1
else:
l = m + 1
return (n - leftGreater)
for ik in range(int(input())):
n,k=map(int,input().split())
l=list(map(int,input().split()))
ans=0
for i in range(n):
ans+=l[i]//k
l=[l[i]%k for i in range(n)]
l.sort()
start=0
ansq=0
for i in range(n-1,-1,-1):
while(start<i and l[start]+l[i]<k):
start+=1
if start>=i:
break
if start<i:
ansq+=1
start+=1
print(ans+ansq)#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define pop pop_back
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define gcd __gcd
#define sort(vec) sort(vec.begin(),vec.end())
#define rev(vec) reverse(vec.begin(),vec.end())
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const int inf=1e18;
// const ld eps=1e-9
// const int mod=1e9+7;
// int binaryexp(int x,int n){
// if(n==0)
// return 1;
// if(n&1)
// return (x*(binaryexp((x*x)%mod,(n-1)/2)))%mod;
// else
// return binaryexp((x*x)%mod,n/2);
// }
// int lcm(int a,int b){
// return ((a*b)/gcd(a,b));
// }
// void accept(vi &vec){
// for(auto &i:vec)
// cin>>i;
// }
// void display(vi &vec){
// for(auto i:vec)
// cout<<i<<" ";
// cout<<endl;
// }
void disp_set(multiset<int>&st){
for(auto it:st)
cout<<it<<" ";
cout<<endl;
}
// void disp_map(map<int,int>&mp){
// for(auto it:mp){
// cout<<(it).fi<<" "<<(it).se<<endl;
// }
// }
bool check(vi &vec,int n,int val,int c,int d){
}
int32_t main(){
fast;
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vi vec(n);int maxm=-1;
multiset<int>st;
int cost=0;
for(auto &i:vec){
cin>>i;maxm=max(maxm,i);
if(i>k){
cost+=(i/k);
i%=k;
}
st.insert(i);
}
// cout<<"loop"<<endl;
for(int i=1;i<=(n/2);i++){
// if(i==1)
// break;
auto it2=st.end();
it2--;
int temp=*it2;
st.erase(it2);
// cout<<"temp"<<" "<<temp<<endl;
int d=temp/k;
int minm=k*(d+1)-temp;
// cout<<"minm"<<" "<<minm<<endl;
auto it1=st.lower_bound(minm);
// cout<<"lowerbound"<<" "<<(*it1)<<endl;
if((*it1)>maxm){
auto it3=st.begin();
cost+=((temp+(*it3))/k);
st.erase(it3);
it2--;
}
else{
cost+=((temp+(*it1))/k);
st.erase(it1);
it2--;
// cout<<"cost"<<cost<<endl;
}
// cout<<"contents of set"<<endl;
// disp_set(st);
}
cout<<cost<<endl;
}
return 0;
}
1452A - Robot Program | 344A - Magnets |
96A - Football | 702B - Powers of Two |
1036A - Function Height | 443A - Anton and Letters |
1478B - Nezzar and Lucky Number | 228A - Is your horseshoe on the other hoof |
122A - Lucky Division | 1611C - Polycarp Recovers the Permutation |
432A - Choosing Teams | 758A - Holiday Of Equality |
1650C - Weight of the System of Nested Segments | 1097A - Gennady and a Card Game |
248A - Cupboards | 1641A - Great Sequence |
1537A - Arithmetic Array | 1370A - Maximum GCD |
149A - Business trip | 34A - Reconnaissance 2 |
59A - Word | 462B - Appleman and Card Game |
1560C - Infinity Table | 1605C - Dominant Character |
1399A - Remove Smallest | 208A - Dubstep |
1581A - CQXYM Count Permutations | 337A - Puzzles |
495A - Digital Counter | 796A - Buying A House |