A. Robin Helps time limit per test1 second memory limit per test256 megabytes There is a…
- User
A. Robin Helps time limit per test1 second memory limit per test256 megabytes There is a little bit of the outlaw in everyone, and a little bit of the hero too. The heroic outlaw Robin Hood is famous for taking from the rich and giving to the poor.
Robin encounters n people starting from the 1 -st and ending with the n -th. The i -th person has ai gold. If ai≥k , Robin will take all ai gold, and if ai=0 , Robin will give 1 gold if he has any. Robin starts with 0 gold.
Find out how many people Robin gives gold to.
Input The first line of the input contains a single integer t (1≤t≤104 ) — the number of test cases.
The first line of each test case contains two integers n , k (1≤n≤50,1≤k≤100 ) — the number of people and the threshold at which Robin Hood takes the gold.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤100 ) — the gold of each person.
Output For each test case, output a single integer, the number of people that will get gold from Robin Hood.
Example InputCopy 4 2 2 2 0 3 2 3 0 0 6 2 0 3 0 0 0 0 2 5 5 4 OutputCopy 1 2 3 0 Note In the first test case, Robin takes 2 gold from the first person and gives a gold to the second person.
In the second test case, Robin takes 3 gold and gives 1 gold to each of the next 2 people.
In the third test case, Robin takes 3 gold and so only gives gold to 3 other people.
#include <bits/stdc++.h> #define int long long using namespace std;
signed main() { ios::sync_with_stdio(false); cin.tie(0);
}
- Assistant
Here's the complete solution to the problem:
#include <bits/stdc++.h> #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int n, k; cin >> n >> k; vector<int> a(n); for (int &ai : a) cin >> ai; int robin_gold = 0; int res = 0; for (int ai : a) { if (ai >= k) { robin_gold += ai; } else if (ai == 0 && robin_gold > 0) { robin_gold--; res++; } } cout << res << '\n'; } }Explanation:
The problem requires us to simulate Robin Hood's actions as he encounters each person in order. Here's how we approach it:
-
Initialization:
- Read the number of test cases
t. - Iterate over each test case:
- Read the number of people
nand the thresholdk. - Read the list of gold amounts
afor each person.
- Read the number of people
- Initialize
robin_goldto0to represent the gold Robin currently has. - Initialize
resto0to count the number of people Robin gives gold to.
- Read the number of test cases
-
Simulating Robin Hood's Actions:
- For each person in the list:
- If the person has
ai >= kgold:- Robin takes all their gold.
- Increase
robin_goldbyai.
- Else if the person has
ai == 0gold and Robin has at least 1 gold (robin_gold > 0):- Robin gives 1 gold to the person.
- Decrease
robin_goldby1. - Increase
resby1as we have given gold to one more person.
- Else:
- Robin does nothing.
- If the person has
- For each person in the list:
-
Output:
- After processing all people in a test case, output the value of
res, which is the number of people Robin gave gold to.
- After processing all people in a test case, output the value of
Notes:
- The constraints are small (
nup to50andtup to10^4), so a straightforward simulation is efficient enough. - We use
int(which is defined aslong longdue to#define int long long) to prevent any integer overflow, even though in this problem it's not strictly necessary. - By using
ios::sync_with_stdio(false);andcin.tie(0);, we optimize the input/output operations to make the program run faster.
Example Run:
Let's go through one of the sample inputs to see how the program works.
Input:
2 2 2 2 0 3 2 3 0 0First Test Case:
n = 2,k = 2a = [2, 0]robin_gold = 0,res = 0- Person 1 has
2gold (>= k), so Robin takes it.robin_gold = 2
- Person 2 has
0gold, and Robin has2gold.- Robin gives 1 gold.
robin_gold = 1,res = 1
- Output:
1
Second Test Case:
n = 3,k = 2a = [3, 0, 0]robin_gold = 0,res = 0- Person 1 has
3gold (>= k), so Robin takes it.robin_gold = 3
- Person 2 has
0gold, and Robin has3gold.- Robin gives 1 gold.
robin_gold = 2,res = 1
- Person 3 has
0gold, and Robin has2gold.- Robin gives 1 gold.
robin_gold = 1,res = 2
- Output:
2
Conclusion:
The program correctly counts the number of people that Robin gives gold to based on the problem's rules.
-