Bit Party

PKJ

 Google Competition 

 Code Jam 

 Bit Party 

 Problem Statement 

These days, robots can drive cars, but can they throw a good party? We just deployed R robot shoppers to our local supermarket to buy party supplies. The first-order model of a Canadian party was very simple: they just bought B "bits" (a bit being a small donut-like treat found in the area). We will work on improving their AI later, but for now, we want to help them purchase all of those bits as quickly as possible.

The supermarket has C cashiers who can scan customers' purchases. The i-th cashier will:

  • accept a maximum of Máµ¢ items per customer
  • take Sáµ¢ seconds to scan each item
  • spend a further Páµ¢ seconds handling payment and packaging up the bits.
That is, a customer who brings N bits to the i-th cashier (where N must be less than or equal to Máµ¢) will spend a total of Sáµ¢ x N + Páµ¢ seconds interacting with that cashier.

Before the robots interact with any cashiers, you will distribute the bits among the robots however you want. (Bits must remain intact; you cannot break them up into fractional pieces!) Any robot that gets no bits will not get to interact with a cashier, and will go away disappointed.

Then, for each robot with at least one bit, you will choose a different single cashier. (Two robots cannot use the same cashier, and a robot cannot use more than one cashier.) The robots all start interacting with its cashier, it cannot be given more bits and cannot interact with other cashier.

If you help the robot make optimal choices, what is the earliest time at which all of the robots can finish interacting with their cashiers?

 Input 

The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with three integers R, B, and C: the numbers of robot shoppers, bits, and cashiers. Then, there are C more lines. The i-th of these represents the i-th cashier, and it has three integers Máµ¢, Sáµ¢, and Páµ¢: the maximum number of bits, scan time per bit (in seconds), and payment/packaging time (in seconds) for that cashier, as described above.

 Output 

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the earliest time (in seconds) at which all robots can finish interacting with their cashiers.

 Limits 

1 ≤ T ≤ 100.
1 ≤ Máµ¢ ≤ 10⁹, for all i.
1 ≤ Sáµ¢ ≤ 10⁹,for all i.
1 ≤ Páµ¢ ≤ 10⁹, for all i.
The sum of the R largest values of Máµ¢ ≥ B. (It is possible for at least one subset of R cashiers to handle all of the bits.)
Time limit: 15 seconds per test set.
Memory limit: 1 GB.

 Test Set 1 (Visible) 

1 ≤ R ≤ C ≤ 5.
1 ≤ B ≤ 20.

 Test Set 2 (Hidden) 

1 ≤ R ≤ C ≤ 1000.
1 ≤ B ≤ 10.

 Sample 


                Input                        Output


                3
                2 2 2
                1 2 3
                1 1 2
                2 2 2
                  1 2 3                        Case #1:   5
                2 1 2                        Case #2:   4
                3 4 5                        Case #3:   7
                2 3 3
                2 1 5
                2 4 2
                2 2 4
                2 5 1

In Sample Case #1, there are two robots, two bits, and two cashiers, and each cashiers can only handle one item. So, you must give one bit to each robot. Cashier 1 takes 5 seconds, and Cashier 2 takes 3 seconds, so the time required is 5 seconds.

Sample Case #2 is similar to the previous case, except that now Cashier 2 can handle up to 2 items. So, it is best to give all the bits to one robot and have that robot use Cashier 2. This takes 1 seconds per item plus 2 seconds = 4 seconds.

In Sample Case #3, the optimal strategy is to send one robot with 2 bits to cashier 2, and two robots with 1 bit each to any of the other cashiers.

 Analysis 

 Test Set 1 

We might consider enumerating all the ways of assigning bits to cashiers, but with 20 bits and 5 cashiers, there could be as many as 5²⁰ ways ― too many to check! We need to take advantage of the fact that the bits are interchangeable, and instead find all the ways to partition B bits among R of the C cashiers (since we will only be able to use as many cashiers as we have robots). Then, we can compute how much time each of those ways takes, and pick the minimum of those values.

We can calculate the number of ways to partition 20 bits among 5 robots using this method. It turns out there are only (24 choose 4) = 10,626 ways to check. If we have fewer robots than cashiers, then we need to introduce another multiplicative factor of (C choose R), but this cannot be larger than 10 in test set 1. Each check takes O(R) time, which is very small given that R is at most 5. So, test set 1 should be solvable well within the 15 second time limit, regardless of your language choice.

 Test Set 2 

To solve this test set, we need to be able to answer the following question: Given a time limit T, is there a possible assignment of bits such that all the robots can finish interacting with their cashiers in no more than T seconds? Let f(T) be the answer to this question.

How can we find f(T)? The maximum number of bits that the i-th cashier can process in not more than T seconds is max(0, min(Máµ¢, floor((T - Páµ¢) / Sáµ¢))). Let us call this value Capacityáµ¢.

Then, we want to know whether a total of B bits can be assigned to R robots, and each of those robot to a cashier, such that the number of bits processed by the i-th cashier is not more than Capacityáµ¢. To do this, we can greedily sort the Capacity values into nonincreasing order, and then assign the R robots to the first R cashiers. f(T) is true if and only if the total number of bits that can be processed by the first R cashiers is at least B. Therefore, we can compute the value of f(T) for any T in O(C log (C)) time (which is the time it takes to sort the Capacity values). (Aside: We can even avoid the sort, and instead partition in O(C) time, by using introselect, for example.)

Since we want to minimize the time taken for all robots to interact with their cashiers, we want to find the minimum possible value of T such that f(T) is true. 
That value of T will also satisfy the following:

  • f(x) is false for all x < T.
  • f(x) is true for all x ≥ T.

Therefore, we can find the value of T using binary search. Since the maximum answer will not be more than O(max(S) x B + max(P)), this solution will run in O(C log(C) log(max(S) x B + max(P))) time.

 Solution 
 Programming Language: C++17 (G++) 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
using namespace std;
#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif
typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair
const int N = 1010;
int n, m;
ll k;
ll a[N][3];
ll b[N];
bool solve(ll T) {
	for (int i = 0; i < n; i++) {
		ll t = (T - a[i][2]);
		t /= a[i][1];
		t = max(t, 0LL);
		t = min(t, a[i][0]);
		b[i] = t;
	}
	sort(b, b + n);
	ll res = 0;
	for (int i = n - m; res < k && i < n; i++) {
		res += b[i];
	}
	return res >= k;
}
void solve() {
	scanf("%d%lld%d", &m, &k, &n);
	for (int i = 0; i < n; i++)
		scanf("%lld%lld%lld", &a[i][0], &a[i][1], &a[i][2]);
	ll L = -1, R = (ll)2e18;
	while(R - L > 1) {
		ll x = (L + R) / 2;
		if (solve(x))
			R = x;
		else
			L = x;
	}
	printf("%lld\n", R);
}
int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		printf("Case #%d: ", i);
		solve();
	}
	return 0;
}

//Published By PKJCODERS

 Programming Language: Java 11 (Open JDK) 

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;
public class Solution {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        BitParty solver = new BitParty();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++) {
            solver.solve(i, in, out);
        }
        out.close();
    }
    static class BitParty {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int r = in.readInt();
            int b = in.readInt();
            int c = in.readInt();
            int[] m = new int[c];
            int[] s = new int[c];
            int[] p = new int[c];
            in.readIntArrays(m, s, p);
            long[] qty = new long[c];
            long left = 0;
            long right = 2_000_000_000_000_000_000L;
            while (left < right) {
                long middle = (left + right) >> 1;
                for (int i = 0; i < c; i++) {
                    if (p[i] > middle) {
                        qty[i] = 0;
                    } else {
                        qty[i] = Math.min(m[i], (middle - p[i]) / s[i]);
                    }
                }
                Arrays.sort(qty);
                ArrayUtils.reverse(qty);
                long current = 0;
                for (int i = 0; i < r; i++) {
                    current += qty[i];
                }
                if (current >= b) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            out.printLine("Case #" + testNumber + ":", left);
        }
    }
    static interface LongStream extends Iterable<Long>, Comparable<LongStream> {
        public LongIterator longIterator();
        default public Iterator<Long> iterator() {
            return new Iterator<Long>() {
                private LongIterator it = longIterator();
                public boolean hasNext() {
                    return it.isValid();
                }
                public Long next() {
                    long result = it.value();
                    it.advance();
                    return result;
                }
            };
        }
        default public int compareTo(LongStream c) {
            LongIterator it = longIterator();
            LongIterator jt = c.longIterator();
            while (it.isValid() && jt.isValid()) {
                long i = it.value();
                long j = jt.value();
                if (i < j) {
                    return -1;
                } else if (i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if (it.isValid()) {
                return 1;
            }
            if (jt.isValid()) {
                return -1;
            }
            return 0;
        }
    }
    static interface LongIterator {
        public long value() throws NoSuchElementException;
        public boolean advance();
        public boolean isValid();
    }
    static interface LongCollection extends LongStream {
        public int size();

    }
    static class ArrayUtils {
        public static void reverse(long[] array) {
            new LongArray(array).inPlaceReverse();
        }
    }
    static interface LongList extends LongReversableCollection {
        public abstract long get(int index);
        public abstract void set(int index, long value);
        public abstract void removeAt(int index);
        default public void swap(int first, int second) {
            if (first == second) {
                return;
            }
            long temp = get(first);
            set(first, get(second));
            set(second, temp);
        }
        default public LongIterator longIterator() {
            return new LongIterator() {
                private int at;
                private boolean removed;
                public long value() {
                    if (removed) {
                        throw new IllegalStateException();
                    }
                    return get(at);
                }
                public boolean advance() {
                    at++;
                    removed = false;
                    return isValid();
                }
                public boolean isValid() {
                    return !removed && at < size();
                }
                public void remove() {
                    removeAt(at);
                    at--;
                    removed = true;
                }
            };
        }
        default public void inPlaceReverse() {
            for (int i = 0, j = size() - 1; i < j; i++, j--) {
                swap(i, j);
            }
        }
    }
    static abstract class LongAbstractStream implements LongStream {
        public String toString() {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for (LongIterator it = longIterator(); it.isValid(); it.advance()) {
                if (first) {
                    first = false;
                } else {
                    builder.append(' ');
                }
                builder.append(it.value());
            }
            return builder.toString();
        }
        public boolean equals(Object o) {
            if (!(o instanceof LongStream)) {
                return false;
            }
            LongStream c = (LongStream) o;
            LongIterator it = longIterator();
            LongIterator jt = c.longIterator();
            while (it.isValid() && jt.isValid()) {
                if (it.value() != jt.value()) {
                    return false;
                }
                it.advance();
                jt.advance();
            }
            return !it.isValid() && !jt.isValid();
        }
        public int hashCode() {
            int result = 0;
            for (LongIterator it = longIterator(); it.isValid(); it.advance()) {
                result *= 31;
                result += it.value();
            }
            return result;
        }
    }
    static class LongArray extends LongAbstractStream implements LongList {
        private long[] data;
        public LongArray(long[] arr) {
            data = arr;
        }
        public int size() {
            return data.length;
        }
        public long get(int at) {
            return data[at];
        }
        public void removeAt(int index) {
            throw new UnsupportedOperationException();
        }
        public void set(int index, long value) {
            data[index] = value;
        }

    }
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
        public void readIntArrays(int[]... arrays) {
            for (int i = 0; i < arrays[0].length; i++) {
                for (int j = 0; j < arrays.length; j++) {
                    arrays[j][i] = readInt();
                }
            }
        }
        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        public String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }
        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        public String next() {
            return readString();
        }
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    static class OutputWriter {
        private final PrintWriter writer;
        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }
        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }
        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }
        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }
        public void close() {
            writer.close();
        }
    }
    static interface LongReversableCollection extends LongCollection {
    }
}

//Published By PKJCODERS

 Programming Language: Python 3.7 

#!/usr/bin/python3
def solve(r, b, c, m, s, p):
    lt, rt = 0, 10 ** 20
    while lt < rt - 1:
        mid = (lt + rt) // 2
        can = [0] * c
        for i in range(c):
            can[i] = max(0, min(m[i], (mid - p[i]) // s[i]))
        can.sort(reverse=True)
        if sum(can[:r]) >= b:
            rt = mid
        else:
            lt = mid
    return rt
t = int(input())
for testcase in range(1, t + 1):
    r, b, c = map(int, input().split())
    m = []
    s = []
    p = []
    for i in range(c):
        cm, cs, cp = map(int, input().split())
        m.append(cm)
        s.append(cs)
        p.append(cp)
    print("Case #{}: {}".format(testcase, solve(r, b, c, m, s, p)))

#Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.) 

Comments

Post a Comment

Popular Posts

Property Inheritance in Family

PKJ
 Coding Problem Keys   Property Inheritance in Family   Problem Statement  The hierarchy of a family is given as the input. The first N lines contain the family hierarchy with each line containing the parent and the child names separated by a space. Each person in the family inherits the property only from his parents. (The value of the property of a parent is divided equally among his children). After the family hierarchy information, the names of two family members X and Y are also passed as the input. The value of property V inherited by the family member X is also given as the input. The program must find and print the value of property inherited by the family member Y. Note: If the value of the property of a parent cannot be divided by the number of children without leaving a remainder, then consider the floor value as the amount inherited by a single child. (As an example if the property worth is 10000 and number of children is 3, then the amount inh...
Click to Continue...

Reversed Sum of Pairs

PKJ
 Coding Problem Keys   Reversed Sum of Pairs    Problem Statement  An array of N integers is passed as input. The program must print the sum of every two consecutive elements in the array from last.  Boundary Condition(s)  1 <= N <= 1000  Input Format  The first line contains N . The second line contains N integers separated by space(s).  Output Format  The first line contains the sum of pairs separated by a space.  Example Input/Output 1   Input  4 10 50 30 60  Output  90 60  Example Input/Output 2   Input  5 25 50 100 250 300  Output  550 150 25  Note: Max Execution Time Limit: 5000 millisecs   Solution   Programming Language: C Language  #include <stdio.h> #include <stdlib.h> int main () { int n,i; scanf( "%d" ,&n); int arr[n]; for ( int i= 0 ;i<n;i++){ scanf( "%d" ,&arr[...
Click to Continue...

Sort Rows by Prime, Even and Odd Count

PKJ
 Coding Problem Keys   Sort Rows by Prime, Even and Odd Count   Problem Statement  An integer matrix of size R*C is given as input. The program must sort the rows based on the number of prime numbers in descending order. If two rows contain the same number of prime numbers then sort the rows based on the number of even numbers(also non-prime). If two rows contain the same number of prime numbers and the same number of even numbers then sort the rows based on the number of odd numbers (also non-prime). If two rows contain the same number of prime numbers, even numbers and odd numbers then sort the rows based on the sum of elements of each row in descending order.  Boundary Condition(s)  1 <= R, C <= 100  Input Format  The first line contains the value of R and C separated by space(s). Next R lines contains C integers each separated by space(s).  Output Format  R lines containing C integers with the rows sorted based on giv...
Click to Continue...

String Comparision

PKJ
  String Comparision   Problem Statement:  The program must accept two string values S1 and S2 as the input. The program must print yes if the both the string values are equal. Else the program must no as the output. Note: S1 and S2 contain only lowercase alphabets.  Boundary Condition(S):  1 <= Length of S1, S2 <=100  Input Format:  The first line contains the string S1. The second line contains the string S2.  Output Format:  The first line contains either yes or no.  Example Input/Output 1:   Input:  eagle eagle  Output:  yes  Explanation:  Both the string values (S1 and S2) are equal. So yes is printed as the output.  Example Input/Output 2:   Input:  tortoise rabbit  Output:  no  Note: Max Execution Time Limit: 4000 millisecs   Solution:   Programming Language: C Language  #include <stdio.h> #include <stdlib.h> in...
Click to Continue...

Integer - Alphabet Pairs to Matrix

PKJ
 Coding Problem Keys   Integer - Alphabet Pairs to Matrix   Problem Statement  The program must accept a list of integer-alphabet pairs and two integers R, C as the input. The sum of the integers present in all the integer-alphabet pairs is always equal to the product of R and C. The program must form a matrix of size R*C based on the following conditions.     - The program must expand each integer-alphabet pair by repeating the specified alphabet X times, where X represents the integer value present in the pair.     - Then the program must fill the matrix with the expanded alphabets from the 1st row to the Rth row, where left to right in each row. Finally, the program must print the R*C matrix as the output.  Boundary Condition(S)  2 <= R, C <= 50  Input Format  The first line contains a list of integer-alphabet pairs separated by a space. The second line contains R and C separated by a space.  Output For...
Click to Continue...

Missing Integers

PKJ
 Coding Problem Keys   Missing Integers   Problem Statement  The program must accept an integer  N  in a continuous series and print the missing integer values. The first and last terms in the series will always be present.  Boundary Condition(s)  2 <= N <= 100 1 <= Each integer value <= 1000  Input Format  The first line contains the value of N. The second line contains N integers separated by a space.  Output Format  The first line contains the missing integer values separated by a space.  Example Input/Output 1   Input  5 10 12 15 16 20  Output  11 13 14 17 18 19  Example Input/Output 2   Input  8 1 5 6 7 8 9 11 12  Output  2 3 4 10  Note:  Max Execution Time Limit: 500 millisecs   Solution   Programming Language: Python 3 Language  n= int ( input ()) l= list ( map ( int , input ().split())) for i in rang...
Click to Continue...