Codeforces problem -Teleporters (Easy Version)

Link -https://codeforces.com/problemset/problem/1791/G1

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N = 1e5 + 10;
int dp[N];

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        int n, c;
        cin >> n >> c;
        vector<int> a(n, 0);
        vector<int> temp;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            temp.push_back(a[i] + i + 1);
        }

        int count = 0;
        sort(temp.begin(), temp.end());
        int idx = 0;

        while (idx != n and c > 0)
        {
            if (temp[idx] <= c)
            {

                c -= temp[idx];
                temp[idx] = INT_MAX;
                idx = 0;
                count++;
            }
            else if (temp[idx] > c)
            {

                idx++;
            }
        }

        cout << count << endl;
    }

    return 0;
}

explanation :

Here`s the few points that i can conclude from the problems for problem solving

-> as it take 1 points to move from one index to another

-> is the a[i] is smaller then current coin then i can use it to teleport

-> we have to output the max teleporters i can use , so we can conclude from this that we have to spend minimum coins

Code implementation :

-> first we take input from the user.

-> now we make temp vector to store the a[i] + i + 1 sum and sort it.

-> now iterate to temp vector if current coin is greater than or equal to temp[i] then use that coin to teleport and make temp[i] to max integer so that we can't use that again else if temp[i] greater then coin then go to next index until n.