Solution: Save the Nature | Additional Practice for USACO Silver

Explanation

Binary search on the answer for the minimum number of tickets, $t$ , to sell to make the total ecological contribution to at least $k$ .

Let's try to determine the maximum contribution attainable with $t$ tickets.

The problem indicates that only $x\%$ of the $a$ -th ticket and $y\%$ of the $b$ -th ticket could contribute to the total ecological contribution. We can precompute these multipliers $pct$ (either $0$ , $x$ , $y$ , or $x+y$ depending on the ticket) over $t$ tickets, then greedily match the largest multiplier with the highest value ticket. This can be done by sorting the multipliers $pct$ and tickets $p$ in decreasing order; then the maximum total ecological contribution would be $\sum\limits_{i=1}^{t} p_i \cdot pct_i$ .

Implementation

Time Complexity: $\mathcal{O}(N\log^2 N)$

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
vector<ll> p;

ll x, a, y, b, k;

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public final class SaveNature {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int queryNum = Integer.parseInt(read.readLine());

Python

from math import gcd

for _ in range(int(input())):
	ticket_num = int(input())
	tickets = sorted([int(i) for i in input().split()], reverse=True)
	prog1 = [int(i) for i in input().split()]
	prog2 = [int(i) for i in input().split()]
	min_revenue = int(input())
	# the frequency of both programs including a single ticket
	combo_freq = prog1[1] * prog2[1] // gcd(prog1[1], prog2[1])

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum

Table of Contents

Table of Contents

Explanation

Implementation

Join the USACO Forum!