Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef has a memory machine. It has one layer for data storage and another layer for cache. Chef has stored an array with length $N$ in the first layer; let's denote its elements by $A_{0}, A_{1}, \ldots, A_{N-1}$. Now he wants to load some elements of this array into the cache.

The machine loads the array in blocks with size $B$: $A_{0}, A_{1}, \ldots, A_{B-1}$ form a block, $A_{B}, A_{B+1}, \ldots, A_{2B-1}$ form another block, and so on. The last block may contain less than $B$ elements of Chef's array. The cache may only contain at most one block at a time. Whenever Chef tries to access an element $A_{i}$, the machine checks if the block where $A_{i}$ is located is already in the cache, and if it is not, loads this block into the cache layer, so that it can quickly access any data in it. However, as soon as Chef tries to access any element that is outside the block currently loaded in the cache, the block that was previously loaded into the cache is removed from the cache, since the machine loads a new block containing the element that is being accessed.

Chef has a sequence of elements $A_{x_{1}}, A_{x_{2}}, \ldots, A_{x_{M}}$ which he wants to access, in this order. Initially, the cache is empty. Chef is wondering how many times the machine will need to load a block into the cache layer. Can you help him calculate this number?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $B$ and $M$.
The second line contains $M$ space-separated integers $x_{1}, x_{2}, \ldots, x_{M}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of times the machine loads a block into the cache.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N, B, M ≤ 5,000$
$0 ≤ x_{i} < N$ for each valid $i$

----- Sample Input 1 ------ 
1

5 3 3

0 3 4
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Example case 1: The machine stores elements $[A_{0}, A_{1}, A_{2}]$ in one block and $[A_{3}, A_{4}]$ in another block. When accessing $A_{0}$, the block $[A_{0}, A_{1}, A_{2}]$ is loaded. Then, accessing $A_{3}$ removes the previous block from the cache and loads the block $[A_{3}, A_{4}]$. Finally, when Chef accesses $A_{4}$, a new block is not loaded, since the block containing $A_{4}$ is currently loaded in the cache.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Implementation

Complete search


Solutions:
t = int(input())
for ni in range(t):
	(n, b, m) = map(int, input().split())
	l = [int(i) for i in input().split()]
	pres = -1
	count = 0
	for i in l:
		req = i // b
		if req != pres:
			count = count + 1
			pres = req
	print(count)


t = int(input())
for ni in range(t):
	(n, b, m) = map(int, input().split())
	l = [int(i) for i in input().split()]
	l1 = list()
	i = 0
	l1.append(0)
	while i <= n + b:
		i = i + b
		l1.append(i)
	count = 0
	pres = 0
	for i in range(m):
		for j in l1:
			if l[i] < j:
				if j == pres:
					break
				else:
					pres = j
					count = count + 1
					break
	print(count)


for _ in range(int(input())):
	(n, b, m) = map(int, input().split())
	x = list(map(int, input().split()))
	(curr, cnt) = (-1, 0)
	for i in x:
		load = i // b
		if load != curr:
			curr = load
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	(n, b, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	current_cache = -1
	ans = 0
	for i in a:
		if i // b != current_cache:
			ans += 1
			current_cache = i // b
	print(ans)


for _ in range(int(input())):
	(N, B, M) = map(int, input().split())
	X = list(map(int, input().split()))
	block = -1
	loads = 0
	for x in X:
		new_block = x // B
		if block != new_block:
			loads += 1
			block = new_block
	print(loads)


a = int(input())
for i in range(a):
	(b, c, d) = map(int, input().split())
	(z, l, f) = ([int(j) for j in input().split()], 0, -1)
	for y in z:
		if y // c != f:
			l += 1
			f = y // c
	print(l)


for tc in range(int(input())):
	(n, b, m) = map(int, input().split())
	x = list(map(int, input().split()))
	curblock = -1
	switch = 0
	for i in x:
		block = i // b
		if block != curblock:
			switch += 1
			curblock = block
	print(switch)


for _ in range(int(input())):
	(n, b, m) = map(int, input().split())
	l = list(map(int, input().split()))
	a = 0
	c = -5
	for i in l:
		x = i - i % b
		if x != c:
			a += 1
			c = x
	print(a)


for i in range(int(input())):
	(n, b, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	c = 0
	k = -1
	for i in lst:
		x = i - i % b
		if k != x:
			c += 1
			k = x
	print(c)


for _ in range(int(input())):
	(n, b, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 1
	iCol = a[0] // b
	for i in range(m):
		k = a[i] // b
		if k == iCol:
			continue
		ans += 1
		iCol = k
	print(ans)


for _ in range(int(input())):
	(n, b, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	(c, d) = (-1, 0)
	for i in a:
		l = i // b
		if l != c:
			c = l
			d += 1
	print(d)


for _ in range(int(input())):
	(N, B, M) = map(int, input().split())
	Lm = list(map(int, input().split()))
	(curr, c) = (-1, 0)
	for i in Lm:
		load = i // B
		if load != curr:
			curr = load
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	(n, b, m) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	c = 0
	bl = -1
	for i in l:
		if i // b != bl:
			c += 1
			bl = i // b
	print(c)


for t in range(int(input())):
	(n, b, m) = map(int, input().split())
	x = list(map(int, input().split()))
	c = 1
	for i in range(1, m):
		if int(x[i] / b) != int(x[i - 1] / b):
			c += 1
	print(c)


tests = int(input())
for i in range(tests):
	(n, b, m) = map(int, input().split())
	l = list(map(int, input().split()))
	prev = -1
	ret = 0
	for i in range(m):
		if l[i] // b != prev:
			prev = l[i] // b
			ret += 1
	print(ret)


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	l = list(map(int, input().split()))
	s = -1
	c = 0
	for i in l:
		lo = i // b
		if lo != s:
			s = lo
			c += 1
	print(c)


for _ in range(int(input())):
	(n, b, m) = map(int, input().split())
	l = list(map(int, input().split()))
	(k, s) = ('', 0)
	for i in l:
		a = i // b
		if a != k:
			s += 1
			k = a
	print(s)


import math
tests = int(input())
for i in range(tests):
	(n, b, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 1
	for j in range(1, m):
		if math.floor(arr[j - 1] / b) != math.floor(arr[j] / b):
			ans += 1
	print(ans)


T = int(input())
for j in range(T):
	(N, B, M) = map(int, input().split())
	integers = list(map(int, input().split()))
	count = 1
	for i in range(M - 1):
		if integers[i + 1] // B != integers[i] // B:
			count += 1
	print(count)


ujju = int(input())
for amma in range(ujju):
	nac = 1
	(d, a, l) = map(int, input().split())
	tree = list(map(int, input().split()))
	sak = tree[0] // a
	for png in tree:
		if png // a != sak:
			sak = png // a
			nac = nac + 1
	print(nac)


for t in range(int(input())):
	(n, b, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 1
	c = arr[0] // b
	for i in range(1, m):
		temp = arr[i] // b
		if c != temp:
			count += 1
			c = temp
	print(count)


T = int(input())
for _ in range(T):
	(n, b, m) = map(int, input().split())
	x = list(map(int, input().split()))
	s = 1
	for i in range(1, m):
		if x[i] // b != x[i - 1] // b:
			s += 1
	print(s)


for t in range(int(input())):
	(N, B, M) = [int(x) for x in input().split()]
	M = [int(x) for x in input().split()]
	loading_count = 0
	prev_block_no = -1
	for m in M:
		block_no = int(m / B)
		if block_no != prev_block_no:
			loading_count += 1
			prev_block_no = block_no
	print(loading_count)


for item in range(int(input())):
	(n, b, m) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 1
	c = l[0] // b
	for i in range(1, m):
		temp = l[i] // b
		if c != temp:
			count += 1
			c = temp
	print(count)


def solve():
	(n, b, m) = (int(x) for x in input().split())
	M = [int(x) for x in input().split()]
	ans = 1
	for i in range(1, m):
		if M[i] // b != M[i - 1] // b:
			ans += 1
	return ans
_t = int(input())
while _t > 0:
	print(solve())
	_t -= 1


def solve(n, b, arr):
	curr_block = None
	cache_hit = 0
	for ind in arr:
		if ind // b != curr_block:
			cache_hit += 1
			curr_block = ind // b
	return cache_hit

def main():
	for _ in range(int(input())):
		(n, b, m) = map(int, input().split())
		arr = map(int, input().split())
		print(solve(n, b, arr))
main()


t = int(input())
while t > 0:
	(n, b, m) = map(int, input().split())
	x = list(map(int, input().split()))
	a = x[0] // b
	c = 1
	for i in range(1, m):
		k = x[i] // b
		if a != k:
			c = c + 1
			a = k
	print(c)
	t = t - 1


total_testcases = int(input())
for testcase in range(total_testcases):
	(n, b, m) = map(int, input().split())
	x = list(map(int, input().split()))
	begin = end = -1
	result = 0
	for value in x:
		if begin <= value < end:
			pass
		else:
			begin = value // b * b
			end = begin + b
			result += 1
	print(result)


try:
	for i in range(int(input())):
		(n, b, m) = map(int, input().split())
		cache = -1
		count = 0
		for j in list(map(int, input().split())):
			if j // b != cache:
				cache = j // b
				count += 1
		print(count)
except:
	pass


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	d = list(map(int, input().split()))
	e = d[0] // b
	f = 1
	for i in d:
		if i // b != e:
			e = i // b
			f += 1
	print(f)


t = int(input())
for i in range(t):
	(n, b, m) = map(int, input().split())
	l = list(map(int, input().split()))
	s = l[0] // b
	c = 1
	for j in range(1, m):
		z = l[j] // b
		if s != z:
			c += 1
			s = z
	print(c)


for _ in range(int(input())):
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	c = b[0] // a[1]
	d = 1
	for i in range(1, a[2]):
		e = b[i] // a[1]
		if c != e:
			d += 1
			c = e
	print(d)


t = int(input())
while t > 0:
	(n, b, m) = map(int, input().split())
	x = list(map(int, input().split()))
	q = x[0] // b
	c = 1
	for i in range(1, m):
		w = x[i] // b
		if q != w:
			c = c + 1
			q = w
	print(c)
	t = t - 1


for _ in range(int(input())):
	(n, x, p) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	a = -1
	for i in l:
		if i // x != a:
			a = i // x
			c = c + 1
	print(c)


for i in range(int(input())):
	(N, B, M) = map(int, input().split())
	L = list(map(int, input().split()))
	(a, b) = (-1, 0)
	for i in L:
		load = i // B
		if load != a:
			a = load
			b += 1
	print(b)