Alex and his coins

2.8

4 votes
Math, C++, Observation, Basic Math
Problem

Alex loves to collect coins. He has been doing so since his childhood. He has a total of N different types of coins, numbered from 0 to N1. The ith type has A[i] coins. Since, Alex is free right now, he wishes to keep these coins in order but in a specific way.

Initially no coins are in their place.

In one move, he can keep at most K[i] coins of the ith type back in their place. Help him in finding the minimum number of moves it will take to re-order these coins.

Input Format:

  • The first line of input contains a single integer T, which denotes the number of test cases.
  • The first line of each test case contains an integer N, denoting the number of types of coins.
  • The second line of each test case contains N space-separated integers, where the ith integer denotes the value of A[i].
  • The third line of each test case contains N space-separated integers, where the ith integer denotes the value of K[i].

Output Format: For each test case, print an integer that denotes the minimum number of moves Alex will take to re-order coins.

Constraints:

1T101N1051A[i]1091K[i]109

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1:
In the first move, he keeps 3 coins of type 0, 1 coin of type 1, 3 of type 2, and 1 of type 3. So the remaining coins are {2, 0, 6, 1}.
In the second move, he keeps 2 coins of type 0, 3 of type 2, and 1 of type 3. So the remaining coins are {0, 0, 3, 0}.
In the third move, he keeps 3 coins of type 2. Now there are no remaining coins.
Hence, it takes him 3 moves to re-order.

For test case 2:
In the first move, he keeps 1 coin of type 0. Now there are no remaining coins.
Hence, it takes him 1 move to re-order.

Editor Image

?