Mixing Solutions
Source: aizu

Mixing Solutions

Let’s prepare for an experiment with the chemical Yokohama Yellow, or YY in short. You have several containers of aqueous solution of YY. While YY is evenly dissolved in each solution, the concentration may differ among containers. You will take arbitrary amounts of solution from some of the containers and mix them to prepare a new solution with the predetermined total amount.

Ideally, the mixed solution should contain the target amount of YY, but there is a problem. While the exact amount of solution in each container is known, the amount of YY in each solution is guaranteed only to fall within a certain range. Due to this uncertainty, it is difficult to match the amount of YY in the mixed solution exactly to the target amount. Still, you can ensure that the error, the difference from the target amount, will never exceed a certain limit.

To be more precise, let the target and actual amounts of YY in the mixed solution be $y_t$ mg (milligrams) and $y_a$ mg, respectively. Given the amounts of solution taken from the containers, $y_a$ is guaranteed to fall within a certain range. The maximum error is defined as the maximum of $|y_a - y_t|$ when $y_a$ varies within this range.

Find the minimum achievable value of the maximum error, given that you can take any portion of the solution in each container as long as their total is equal to the predetermined amount.

Input

The input consists of a single test case of the following format.

$n$ $s$ $c$
$a_1$ $l_1$ $r_1$
$\vdots$
$a_n$ $l_n$ $r_n$


The first line contains three integers, $n$, $s$, and $c$, satisfying $1 \leq n \leq 1000$, $1 \leq s \leq 10^5$, and $0 \leq c \leq M$, where $M = 10^4$ here and in what follows. Here, $n$ denotes the number of containers of YY solution. The predetermined total amount of the mixed solution is $s$ mg, and the target amount of YY is $\frac{c}{M}s$ mg. The $i$-th of the following $n$ lines contains three integers, $a_i$, $l_i$, and $r_i$, satisfying $1 \leq a_i \leq 10^5$ and $0 \leq l_i \leq r_i \leq M$. These integers indicate that the $i$-th container has $a_i$ mg of solution and that the amount of YY in it is guaranteed to be between $\frac{l_i}{M}a_i$ mg and $\frac{r_i}{M}a_i$ mg, inclusive. They satisfy $\sum^n_{i=1} a_i \geq s$.

Output

The minimum achievable value of the maximum error can be proven to be a rational number. Express the value as an irreducible fraction $p/q$ with $q > 0$, and output $p$ and $q$ separated by a space on a single line.

Sample Input 1
3 10 5000
10 2000 3000
10 4000 6000
10 7000 8000

Sample Output 1
 1 2

Sample Input 2
2 10 5000
7 4500 5500
12 3500 6000

Sample Output 2
4 5

Sample Input 3
3 1 4159
1 1 1
1 100 100
1 10000 10000

Sample Output 3
0 1

Sample Input 4
6 12345 6789
2718 2818 2845
9045 2353 6028
7471 3526 6249
7757 2470 9369
9959 5749 6696
7627 7240 7663

Sample Output 4
23901191037 67820000


C++ solution:
// O(n log n log M): yosupo さんの解法
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int M = 10000;
constexpr ll P = 1000000007;

int main() {
  ll n, s, c;
  cin >> n >> s >> c;
  vector<array<ll, 3>> alr(n);
  for (auto &[a, l, r] : alr) cin >> a >> l >> r;

  // ベクトル (P-k, k) との内積を最小化する多角形上の点の計算 (0 <= k <= P)
  auto get_vertex = [&](ll k) {
    auto coef = [&](ll l, ll r) { return k * r - (P - k) * l; };
    sort(alr.begin(), alr.end(), [&](auto &a, auto &b) { return coef(a[1], a[2]) < coef(b[1], b[2]); });
    
    ll x = c * s;
    ll y = -c * s;
    ll rem = s;
    for (auto [a, l, r] : alr) {
      ll z = min(a, rem);
      x -= l * z;
      y += r * z;
      rem -= z;
    }
    return array<ll, 2>{x, y};
  };

  array<ll, 2> ans;
  auto [x0, y0] = get_vertex(1);
  auto [x1, y1] = get_vertex(P - 1);
  if (x0 >= y0) {
    ans = {x0, 1};
  } else if (x1 <= y1) {
    ans = {y1, 1};
  } else {
    // x0 < y0 and x1 > y1
    int kl = 1;
    int kr = P - 1;
    while (kr - kl > 1) {
      int k = (kl + kr) / 2;
      auto [x, y] = get_vertex(k);
      if (x < y)
        kl = k;
      else
        kr = k;
    }
    auto [xl, yl] = get_vertex(kl);
    auto [xr, yr] = get_vertex(kr);
    ll p = xr * yl - xl * yr;
    ll q = (xr - yr) - (xl - yl);
    ans = {p, q};
  }

  ans[1] *= M;
  ll g = gcd(ans[0], ans[1]);
  cout << ans[0] / g << ' ' << ans[1] / g << '\n';
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math/big"
	"os"
	"sort"
	"strconv"
	"strings"
)

const M = 10000
const P = 1000000007

type Container struct {
	a, l, r int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	s, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	c, _ := strconv.Atoi(scanner.Text())

	containers := make([]Container, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		a, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		l, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		r, _ := strconv.Atoi(scanner.Text())
		containers[i] = Container{a, l, r}
	}

	valueSlope := func(k int) (val, slope *big.Int) {
		sortedContainers := make([]Container, n)
		copy(sortedContainers, containers)
		sort.Slice(sortedContainers, func(i, j int) bool {
			left := k*sortedContainers[i].r - (P-k)*sortedContainers[i].l
			right := k*sortedContainers[j].r - (P-k)*sortedContainers[j].l
			return left < right
		})

		val = big.NewInt(0)
		slope = big.NewInt(0)
		rem := s

		cs := big.NewInt(int64(c))
		cs.Mul(cs, big.NewInt(int64(s)))
		pMinus2k := big.NewInt(int64(P - 2*k))
		term := big.NewInt(0).Mul(cs, pMinus2k)
		val.Add(val, term)

		slopeTerm := big.NewInt(-2)
		slopeTerm.Mul(slopeTerm, cs)
		slope.Add(slope, slopeTerm)

		for _, container := range sortedContainers {
			a := container.a
			l := container.l
			r := container.r
			z := a
			if rem < z {
				z = rem
			}
			kBig := big.NewInt(int64(k))
			rBig := big.NewInt(int64(r))
			term1 := big.NewInt(0).Mul(kBig, rBig)
			pMinusK := big.NewInt(int64(P - k))
			lBig := big.NewInt(int64(l))
			term2 := big.NewInt(0).Mul(pMinusK, lBig)
			term := big.NewInt(0).Sub(term1, term2)
			zBig := big.NewInt(int64(z))
			term.Mul(term, zBig)
			val.Add(val, term)

			lPlusR := big.NewInt(int64(l + r))
			slopeTerm := big.NewInt(0).Mul(lPlusR, zBig)
			slope.Add(slope, slopeTerm)

			rem -= z
			if rem == 0 {
				break
			}
		}
		return val, slope
	}

	_, slope0 := valueSlope(1)
	_, slope1 := valueSlope(P - 1)

	if slope0.Sign() <= 0 {
		val, _ := valueSlope(0)
		ans := computeFraction(val)
		fmt.Println(ans.Num().String(), ans.Denom().String())
	} else if slope1.Sign() >= 0 {
		val, _ := valueSlope(P)
		ans := computeFraction(val)
		fmt.Println(ans.Num().String(), ans.Denom().String())
	} else {
		kl := 1
		kr := P - 1
		for kr-kl > 1 {
			k := (kl + kr) / 2
			_, slope := valueSlope(k)
			if slope.Sign() > 0 {
				kl = k
			} else {
				kr = k
			}
		}
		fl, gl := valueSlope(kl)
		fr, gr := valueSlope(kr)

		term1 := big.NewInt(0).Mul(gl, gr)
		klMinusKr := big.NewInt(int64(kl - kr))
		term1.Mul(term1, klMinusKr)

		term2 := big.NewInt(0).Mul(gl, fr)

		term3 := big.NewInt(0).Mul(gr, fl)

		numerator := big.NewInt(0).Add(term1, term2)
		numerator.Sub(numerator, term3)

		denominator := big.NewInt(0).Sub(gl, gr)
		denominator.Mul(denominator, big.NewInt(P*M))

		ans := big.NewRat(1, 1)
		ans.SetFrac(numerator, denominator)
		reduceFraction(ans)

		fmt.Println(ans.Num().String(), ans.Denom().String())
	}
}

func computeFraction(val *big.Int) *big.Rat {
	ans := big.NewRat(1, 1)
	denominator := big.NewInt(P * M)
	ans.SetFrac(val, denominator)
	reduceFraction(ans)
	return ans
}

func reduceFraction(frac *big.Rat) {
	gcd := big.NewInt(0).GCD(nil, nil, frac.Num(), frac.Denom())
	if gcd.Cmp(big.NewInt(0)) != 0 {
		frac.Num().Div(frac.Num(), gcd)
		frac.Denom().Div(frac.Denom(), gcd)
	}
	if frac.Denom().Sign() < 0 {
		frac.Num().Neg(frac.Num())
		frac.Denom().Neg(frac.Denom())
	}
}

Java solution:
import java.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main {
    static final BigInteger M = BigInteger.valueOf(10000);
    static final BigInteger P = BigInteger.valueOf(1000000007);
    
    static class Container implements Comparable<Container> {
        BigInteger a, l, r;
        BigInteger sortKey;
        
        Container(BigInteger a, BigInteger l, BigInteger r) {
            this.a = a;
            this.l = l;
            this.r = r;
        }
        
        void setSortKey(BigInteger k) {
            this.sortKey = k.multiply(r).subtract(P.subtract(k).multiply(l));
        }
        
        @Override
        public int compareTo(Container other) {
            return this.sortKey.compareTo(other.sortKey);
        }
    }
    
    static class ValueSlope {
        BigInteger val, slope;
        ValueSlope(BigInteger val, BigInteger slope) {
            this.val = val;
            this.slope = slope;
        }
    }
    
    static ValueSlope valueSlope(List<Container> containers, BigInteger s, BigInteger c, BigInteger k) {
        for (Container cont : containers) {
            cont.setSortKey(k);
        }
        Collections.sort(containers);
        
        BigInteger val = c.multiply(s).multiply(P.subtract(k.multiply(BigInteger.TWO)));
        BigInteger slope = c.multiply(s).multiply(BigInteger.valueOf(-2));
        BigInteger rem = s;
        
        for (Container cont : containers) {
            BigInteger z = cont.a.min(rem);
            val = val.add(k.multiply(cont.r).subtract(P.subtract(k).multiply(cont.l)).multiply(z));
            slope = slope.add(cont.l.add(cont.r).multiply(z));
            rem = rem.subtract(z);
            if (rem.equals(BigInteger.ZERO)) break;
        }
        
        return new ValueSlope(val, slope);
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int s = Integer.parseInt(firstLine[1]);
        int c = Integer.parseInt(firstLine[2]);
        
        List<Container> containers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int l = Integer.parseInt(line[1]);
            int r = Integer.parseInt(line[2]);
            containers.add(new Container(
                BigInteger.valueOf(a),
                BigInteger.valueOf(l),
                BigInteger.valueOf(r)
            ));
        }
        
        ValueSlope vs0 = valueSlope(new ArrayList<>(containers), 
                                  BigInteger.valueOf(s), 
                                  BigInteger.valueOf(c), 
                                  BigInteger.ONE);
        ValueSlope vs1 = valueSlope(new ArrayList<>(containers), 
                                  BigInteger.valueOf(s), 
                                  BigInteger.valueOf(c), 
                                  P.subtract(BigInteger.ONE));
        
        BigInteger numerator, denominator;
        
        if (vs0.slope.compareTo(BigInteger.ZERO) <= 0) {
            ValueSlope vs = valueSlope(new ArrayList<>(containers), 
                                     BigInteger.valueOf(s), 
                                     BigInteger.valueOf(c), 
                                     BigInteger.ZERO);
            numerator = vs.val;
            denominator = P.multiply(M);
        } else if (vs1.slope.compareTo(BigInteger.ZERO) >= 0) {
            ValueSlope vs = valueSlope(new ArrayList<>(containers), 
                                     BigInteger.valueOf(s), 
                                     BigInteger.valueOf(c), 
                                     P);
            numerator = vs.val;
            denominator = P.multiply(M);
        } else {
            BigInteger kl = BigInteger.ONE;
            BigInteger kr = P.subtract(BigInteger.ONE);
            
            while (kr.subtract(kl).compareTo(BigInteger.ONE) > 0) {
                BigInteger k = kl.add(kr).divide(BigInteger.TWO);
                ValueSlope vs = valueSlope(new ArrayList<>(containers), 
                                         BigInteger.valueOf(s), 
                                         BigInteger.valueOf(c), 
                                         k);
                if (vs.slope.compareTo(BigInteger.ZERO) > 0) {
                    kl = k;
                } else {
                    kr = k;
                }
            }
            
            ValueSlope vsl = valueSlope(new ArrayList<>(containers), 
                                      BigInteger.valueOf(s), 
                                      BigInteger.valueOf(c), 
                                      kl);
            ValueSlope vsr = valueSlope(new ArrayList<>(containers), 
                                      BigInteger.valueOf(s), 
                                      BigInteger.valueOf(c), 
                                      kr);
            
            BigInteger term1 = vsl.slope.multiply(vsr.slope).multiply(kl.subtract(kr));
            BigInteger term2 = vsl.slope.multiply(vsr.val);
            BigInteger term3 = vsr.slope.multiply(vsl.val);
            numerator = term1.add(term2).subtract(term3);
            denominator = vsl.slope.subtract(vsr.slope).multiply(P).multiply(M);
        }
        
        BigInteger gcd = numerator.gcd(denominator);
        numerator = numerator.divide(gcd);
        denominator = denominator.divide(gcd);
        
        if (denominator.compareTo(BigInteger.ZERO) < 0) {
            numerator = numerator.negate();
            denominator = denominator.negate();
        }
        
        System.out.println(numerator + " " + denominator);
    }
}

JavaScript solution:
const fs = require('fs');

const M = 1e4;
const P = 1e9 + 7;

class Fraction {
    constructor(numerator, denominator = 1) {
        this.numerator = BigInt(numerator);
        this.denominator = BigInt(denominator);
        this.simplify();
    }

    simplify() {
        const gcd = this.gcd(this.numerator, this.denominator);
        this.numerator /= gcd;
        this.denominator /= gcd;
        if (this.denominator < 0n) {
            this.numerator = -this.numerator;
            this.denominator = -this.denominator;
        }
    }

    gcd(a, b) {
        a = a < 0n ? -a : a;
        b = b < 0n ? -b : b;
        while (b !== 0n) {
            const temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    add(other) {
        const newNumerator = this.numerator * other.denominator + other.numerator * this.denominator;
        const newDenominator = this.denominator * other.denominator;
        return new Fraction(newNumerator, newDenominator);
    }

    sub(other) {
        const newNumerator = this.numerator * other.denominator - other.numerator * this.denominator;
        const newDenominator = this.denominator * other.denominator;
        return new Fraction(newNumerator, newDenominator);
    }

    mul(other) {
        const newNumerator = this.numerator * other.numerator;
        const newDenominator = this.denominator * other.denominator;
        return new Fraction(newNumerator, newDenominator);
    }

    div(other) {
        const newNumerator = this.numerator * other.denominator;
        const newDenominator = this.denominator * other.numerator;
        return new Fraction(newNumerator, newDenominator);
    }

    toString() {
        return `${this.numerator}/${this.denominator}`;
    }
}

function main() {
    const input = fs.readFileSync(0, 'utf-8').trim().split(/\s+/).map(Number);
    let ptr = 0;
    const n = input[ptr++];
    const s = input[ptr++];
    const c = input[ptr++];
    const alr = [];
    for (let i = 0; i < n; i++) {
        const a = input[ptr++];
        const l = input[ptr++];
        const r = input[ptr++];
        alr.push({ a, l, r });
    }

    function valueSlope(k) {
        const sorted = [...alr].sort((x, y) => {
            const xVal = k * x.r - (P - k) * x.l;
            const yVal = k * y.r - (P - k) * y.l;
            return xVal - yVal;
        });
        let val = BigInt(c) * BigInt(s) * BigInt(P - 2 * k);
        let slope = BigInt(-2 * c * s);
        let rem = s;
        for (const { a, l, r } of sorted) {
            const z = Math.min(a, rem);
            val += BigInt(k * r - (P - k) * l) * BigInt(z);
            slope += BigInt(l + r) * BigInt(z);
            rem -= z;
            if (rem === 0) break;
        }
        return { val, slope };
    }

    const vs1 = valueSlope(1);
    const f0 = vs1.val;
    const g0 = vs1.slope;

    const vsP1 = valueSlope(P - 1);
    const f1 = vsP1.val;
    const g1 = vsP1.slope;

    let ans;
    if (g0 <= 0n) {
        const vs0 = valueSlope(0);
        ans = new Fraction(vs0.val.toString());
    } else if (g1 >= 0n) {
        const vsP = valueSlope(P);
        ans = new Fraction(vsP.val.toString());
    } else {
        let kl = 1;
        let kr = P - 1;
        while (kr - kl > 1) {
            const k = Math.floor((kl + kr) / 2);
            const { slope } = valueSlope(k);
            if (slope > 0n) {
                kl = k;
            } else {
                kr = k;
            }
        }
        const vsKl = valueSlope(kl);
        const fl = vsKl.val;
        const gl = vsKl.slope;
        const vsKr = valueSlope(kr);
        const fr = vsKr.val;
        const gr = vsKr.slope;
        const numerator = gl * gr * BigInt(kl - kr) + gl * fr - gr * fl;
        const denominator = gl - gr;
        ans = new Fraction(numerator.toString()).div(new Fraction(denominator.toString()));
    }

    ans = ans.div(new Fraction(P * M));
    console.log(ans.numerator.toString(), ans.denominator.toString());
}

main();

Python solution:
from fractions import Fraction

M = 10**4
P = 10**9 + 7

n, s, c = map(int, input().split())
alr = [tuple(map(int, input().split())) for _ in range(n)]


def value_slope(k):
    alr.sort(key=lambda x: k * x[2] - (P - k) * x[1])
    val = c * s * (P - 2 * k)
    slope = -2 * c * s
    rem = s
    for a, l, r in alr:
        z = min(a, rem)
        val += (k * r - (P - k) * l) * z
        slope += (l + r) * z
        rem -= z
    return val, slope


f0, g0 = value_slope(1)
f1, g1 = value_slope(P - 1)
if g0 <= 0:
    ans = Fraction(value_slope(0)[0])
elif g1 >= 0:
    ans = Fraction(value_slope(P)[0])
else:
    kl = 1
    kr = P - 1
    while kr - kl > 1:
        k = (kl + kr) // 2
        if value_slope(k)[1] > 0:
            kl = k
        else:
            kr = k
    fl, gl = value_slope(kl)
    fr, gr = value_slope(kr)
    ans = Fraction(gl * gr * (kl - kr) + gl * fr - gr * fl, gl - gr)

ans /= P * M
print(ans.numerator, ans.denominator)

Ruby solution:
M = 10**4
P = 10**9 + 7

def solve
  input = gets.split
  n = input[0].to_i
  s = input[1].to_i
  c = input[2].to_i

  alr = []
  n.times do
    line = gets.split
    a = line[0].to_i
    l = line[1].to_i
    r = line[2].to_i
    alr << [a, l, r]
  end

  def value_slope(k, alr, s, c)
    alr_sorted = alr.sort_by { |a, l, r| k * r - (P - k) * l }
    val = c * s * (P - 2 * k)
    slope = -2 * c * s
    rem = s
    alr_sorted.each do |a, l, r|
      z = [a, rem].min
      val += (k * r - (P - k) * l) * z
      slope += (l + r) * z
      rem -= z
      break if rem == 0
    end
    [val, slope]
  end

  f0, g0 = value_slope(1, alr, s, c)
  f1, g1 = value_slope(P - 1, alr, s, c)

  if g0 <= 0
    val, _ = value_slope(0, alr, s, c)
    ans = Rational(val, 1)
  elsif g1 >= 0
    val, _ = value_slope(P, alr, s, c)
    ans = Rational(val, 1)
  else
    kl = 1
    kr = P - 1
    while kr - kl > 1
      k = (kl + kr) / 2
      _, slope = value_slope(k, alr, s, c)
      if slope > 0
        kl = k
      else
        kr = k
      end
    end
    fl, gl = value_slope(kl, alr, s, c)
    fr, gr = value_slope(kr, alr, s, c)
    numerator = gl * gr * (kl - kr) + gl * fr - gr * fl
    denominator = gl - gr
    ans = Rational(numerator, denominator)
  end

  ans /= P * M
  ans = ans.abs if ans < 0  # Ensure the fraction is positive (error is absolute)
  reduced_num = ans.numerator
  reduced_den = ans.denominator

  # Simplify the fraction by dividing by GCD
  gcd = reduced_num.gcd(reduced_den)
  reduced_num /= gcd
  reduced_den /= gcd

  puts "#{reduced_num} #{reduced_den}"
end

solve