C. Mr. Perfectly Fine - 871 Div 4 | Solution in cpp | Codeforces

 Question



Victor wants to become "Mr. Perfectly Fine". For that, he needs to acquire a certain set of skills. More precisely, he has 2 skills he needs to acquire.

Victor has n books. Reading book i takes him mi minutes and will give him some (possibly none) of the required two skills, represented by a binary string of length 2

.What is the minimum amount of time required so that Victor acquires all of the two skills?

Input

The input consists of multiple test cases. The first line contains an integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤2⋅105) — the number of books available.

Then n lines follow. Line i contains a positive integer mi (1≤mi≤2⋅105) and a binary string of length 2, where si1=1 if reading book i acquires Victor skill 1, and si1=0 otherwise, and si2=1 if reading book i acquires Victor skill 2, and si2=0 otherwise.

It is guaranteed that the sum of n over all test cases doesn't exceed 2⋅105

Output

For each test case, output a single integer denoting the minimum amount of minutes required for Victor to obtain both needed skills and −1 in case it's impossible to obtain the two skills after reading any amount of books.

Example

input
Copy
6
4
2 00
3 10
4 01
4 00
5
3 01
3 01
5 01
2 10
9 10
1
5 11
3
9 11
8 01
7 10
6
4 01
6 01
7 01
8 00
9 01
1 00
4
8 00
9 10
9 11
8 11
output
Copy
7
5
5
9
-1
8

Explanation 

This problem can be solved using a greedy approach. First, we sort the books based on the amount of time they take to read. Then, we iterate through the books and keep track of how many of the required skills we have acquired so far. Once we have acquired both skills, we stop iterating and output the total time taken. If we have iterated through all the books and have not acquired both skills, we output -1.

Code

#include <stdio.h>

#include <limits.h>


void sol()

{

    int n;

    scanf("%d", &n);


    int a[n], b[n], c[n], d[n];

    int a_cnt = 0, b_cnt = 0, c_cnt = 0, d_cnt = 0;


    for (int i = 0; i < n; i++)

    {

        int x;

        scanf("%d", &x);


        char s[3];

        scanf("%s", s);


        if (s[0] == '0' && s[1] == '0')

        {

            a[a_cnt++] = x;

        }

        else if (s[0] == '1' && s[1] == '0')

        {

            b[b_cnt++] = x;

        }

        else if (s[0] == '0' && s[1] == '1')

        {

            c[c_cnt++] = x;

        }

        else

        {

            d[d_cnt++] = x;

        }

    }


    int m = INT_MAX, f = 0;

    if (d_cnt != 0)

    {

        int x = INT_MAX;

        for (int i = 0; i < d_cnt; i++)

        {

            if (d[i] < x)

            {

                x = d[i];

            }

        }

        f = 1;

        m = x;

    }


    if (b_cnt != 0 && c_cnt != 0)

    {

        int x = INT_MAX, y = INT_MAX;

        for (int i = 0; i < c_cnt; i++)

        {

            if (c[i] < x)

            {

                x = c[i];

            }

        }

        for (int i = 0; i < b_cnt; i++)

        {

            if (b[i] < y)

            {

                y = b[i];

            }

        }

        if (x + y < m)

            m = x + y;

        f = 1;

    }


    if (f == 1)

    {

        printf("%d\n", m);

    }

    else

    {

        printf("-1\n");

    }


    return;

}


int main()

{

    int t;

    scanf("%d", &t);


    while (t--)

    {

        sol();

    }


    return 0;

}

This solution is written by the interns can be it doesnt provide sureity that it will be right or not so this is right according to the intern but it doesnt covers edge cases. if failed at some edge cases you have to check it out once again.

Previous Post Next Post