8 months ago

PoGo 2.5k

Hyderabad

Question 1:

Maximise Collection

Given N toys in a shop, each with a price represented by an array A. You have a certain amount of money, C, that you can use to buy toys. There are also K toys that are broken and you don't want to buy them.
For each Q query, find the maximum number of toys you can buy with the amount you have while avoiding broken toys.
Notes
• Use 1-based indexing.
•Query definition:
--> The first element represents an integer C, where C =Query[i][0].
-->The second element represents an integer K, where K = Query[i][1].
• The next K integers represent the indices of broken
toys which are Query[i][j] for all j > 1.
• Treat each query independently.

Function description
Complete the solve function. This function takes the following 4 parameters and returns an array of an answer to the query:
• N: Represents the size of array A
• A: Represents the array of costs of each toy
• Q: Represents the number of queries
• Query: Represents the query array
Input format for custom testing
Note: Use this input format if you are testing against custom
input or writing code in a language where we don't provide
boilerplate code.
• The first line contains T, which represents the number of
test cases.
• For each test case:
-->The first line contains a single integer N representing
the size of array.                                                                                                          -->The second line contains N space-seperated integers representing the cost of toys.                                                                                                                            -->The third line contains an  integer Q representing the number of queries.              -->The next Q lines contain the query array.

Output format
For each test case, print Q space-separated integers representing the maximum number of toys you can purchase in a new line.
Constraints
1<T < 10
1 < N < 105
1 < A; < 106 Vi € [1, M]
1 < Q < 101
1 < C < 10°
0 ≤ K < 10
1 < Query[i][j] < =N for every j>1

Sample Input

1
10
7 3 6 8 2 1 4 9 5 10
4
10 3 3 5

Sample Output

3 5 5 10

Question 2:

Triangles

You are given a matrix M with n rows and m columns. The matrix only consists of
either 0 or 1.
A right-angled isosceles triangle is defined as:
• The hypotenuse has to be parallel to the x-axis.
• The length of hypotenuse should be odd and greater than or equal to three.
• All the cells on and inside the triangle should be 0.
Task
Determine the total number of right-angled isosceles triangles, which are formed by
0.
Example
Assumptions
The grid is given as:

Approach

You can see that there is one right-angles isoceles triangle,and the length of the hypotenuse is 3(the three 0s as the hypotenuse).Therefore ans is 1.

Function Description

Complete the find_triangles function provided in the editor.This function takes the following 3 parameters and returns the total number of isoceles right-angles angles:

• Pi : Represents the number of rows in the matrix
• m :Represents the number of columns in the matrix
• M :Represents the matrix

Input Format
Note:This is the input format you must use to provide custom input
pile and Test button)

• The first line contains one integer T denoting the number of test cases.T also specifies the number of times you have to run the find_triangles function on a different set of inputs.
• For each test case:

-->The first line contains an integer n representing the number of rows of the
matrix.                                                                                                                         -->The second line contains an integer m representing the number of
columns of the matrix.
-->The next n lines contain a string of length m representing a row,
Output format
For each test case, print an integer in a new line representing the number of right
angled isosceles triangles.

Sample Input

2
3
5
11111
01010
11011
3
4
1111
1011

Sample Output

0 
1

Explanation
The first line states the number of test cases. Therefore T=2.
The first test case
The input is:

You can clearly see that there is no isosceles right-angled triangle in the matrix,
Therefore, the answer is 0

The second test case

It is explained in the above example

12 weeks ago

Nihal Reddy • 0

Hyderabad

def solve_op():
    t = int(input())
    for _ in range(t):
        n = int(input())
        costs = list(map(int, input().split()))
        q = int(input())
        
        # Precompute indexed costs
        indexed_costs = [(costs[i], i+1) for i in range(n)]
        indexed_costs.sort()
        
        results = []
        for _ in range(q):
            query = list(map(int, input().split()))
            budget = query[0]
            k = query[1]
            broken_set = set(query[2:2+k]) if k > 0 else set()
            
            count = 0
            spent = 0
            for price, idx in indexed_costs:
                if idx not in broken_set:
                    if spent + price <= budget:
                        spent += price
                        count += 1
                    else:
                        break
            
            results.append(count)
        
        print(' '.join(map(str, results)))

if __name__ == "__main__":
    solve_op()

9 days ago

SHASHANK • 0

Dhanbad

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<int> solve(int N, vector<int>& A, int Q, vector<vector<int>>& Query) {
    // Create vector of pairs: {price, index}
    vector<pair<int, int>> toys;
    for (int i = 0; i < N; i++) {
        toys.emplace_back(A[i], i + 1); // 1-based indexing
    }
    
    // Sort by price (ascending)
    sort(toys.begin(), toys.end());
    
    vector<int> result;
    
    // Process each query
    for (int i = 0; i < Q; i++) {
        int C = Query[i][0];  // Budget
        int K = Query[i][1];  // Number of broken toys
        
        set<int> broken;
        for (int j = 0; j < K; j++) {
            broken.insert(Query[i][2 + j]);
        }
        
        int count = 0;
        long long spent = 0;  // Use long long to avoid overflow
        
        // Buy cheapest toys first, skipping broken ones
        for (const auto& toy : toys) {
            int price = toy.first;
            int idx = toy.second;
            
            // Skip if toy is broken
            if (broken.find(idx) != broken.end()) {
                continue;
            }
            
            // Check if we can afford this toy
            if (spent + price <= C) {
                spent += price;
                count++;
            } else {
                break;  // Can't afford more toys
            }
        }
        
        result.push_back(count);
    }
    
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    while (T--) {
        int N;
        cin >> N;
        
        vector<int> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }
        
        int Q;
        cin >> Q;
        
        vector<vector<int>> Query(Q);
        
        // Read queries
        for (int i = 0; i < Q; i++) {
            int C, K;
            cin >> C >> K;
            
            vector<int> query;
            query.push_back(C);
            query.push_back(K);
            
            for (int j = 0; j < K; j++) {
                int broken_idx;
                cin >> broken_idx;
                query.push_back(broken_idx);
            }
            
            Query[i] = query;
        }
        
        // Solve for this test case
        vector<int> result = solve(N, A, Q, Query);
        
        // Output result
        for (size_t j = 0; j < result.size(); j++) {
            cout << result[j];
            if (j != result.size() - 1) {
                cout << " ";
            }
        }
        cout << "\n";
    }
    
    return 0;
}