結果

問題 No.453 製薬会社
ユーザー maguroflymagurofly
提出日時 2021-09-01 10:28:09
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 4,011 bytes
コンパイル時間 12,140 ms
コンパイル使用メモリ 378,848 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 10:13:17
合計ジャッジ時間 13,099 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(non_snake_case)]
fn main() {
let input = getline().trim().split_whitespace().map(|s| s.parse::<f64>().unwrap()).collect::<Vec<_>>();
let (C, D) = (input[0], input[1]);
let c = vec![1000.0, 2000.0];
let mat = vec![
vec![3.0 / 4.0, 2.0 / 7.0, C],
vec![1.0 / 4.0, 5.0 / 7.0, D],
vec![-1.0, 0.0, 0.0],
vec![0.0, -1.0, 0.0],
];
let bounds = vec![
(0.0, 2000.0),
(0.0, 2000.0),
];
let x = seidel_lp(&mut Rng(1), 2, &c, &mat, &bounds).expect("No solution found");
println!("{}", x[0] * 1000.0 + x[1] * 2000.0);
}
fn getline() -> String {
let mut __ret=String::new();
std::io::stdin().read_line(&mut __ret).ok();
return __ret;
}
type T = f64;
struct Rng(u64);
impl Rng {
pub fn next_u32(&mut self) -> u32 {
self.0 = 48271 * self.0 % 2147483647;
self.0 as u32
}
}
/// Seidel's LP Algorithm
/// https://niuez.github.io/cp-cpp-library/math/seidels_lp.html
/// find x = {x[0], x[1], ..., x[d - 1]}
/// maximizes (0 .. d).map(|i| c[i] * x[i]).sum()
fn seidel_lp(rnd: &mut Rng, d: usize, c: &[T], mat: &[Vec<T>], bounds: &[(T, T)]) -> Option<Vec<T>> {
// eprintln!("seidel_lp(rnd, d = {}, c = {:?}, mat = {:?}, bounds = {:?})", d, c, mat, bounds);
assert_eq!(c.len(), d, "c.len() != d");
let m = mat.len();
for i in 0 .. m {
assert_eq!(mat[i].len(), d + 1, "mat[{}].len() != d + 1 ({}); mat = {:?}", i, d + 1, &mat);
}
fn eps_eq(x: T, y: T) -> bool {
(x - y).abs() <= 1e-9
}
if d == 1 {
let (mut low, mut high) = bounds[0];
let mut z = 0.0;
for a in mat.iter() {
if eps_eq(a[0], 0.0) {
if eps_eq(a[1], z) || a[1] < z {
z = a[1];
}
} else if a[0] > 0.0 {
// greater
// high = high.min(a[1] / a[0]);
//
let pa = a[1] / a[0];
if eps_eq(pa, high) || pa < high {
high = pa;
}
} else {
// less
// low = low.max(a[1] / a[0]);
let pa = a[1] / a[0];
if eps_eq(pa, low) || pa > low {
low = pa;
}
}
}
if z.is_sign_negative() || high < low {
None
} else if eps_eq(c[0], 0.0) || c[0] > 0.0 {
Some(vec![high])
} else {
Some(vec![low])
}
} else if m == 0 {
// no constraints
Some((0 .. d).map(|i| {
if eps_eq(c[i], 0.0) || c[i] > 0.0 {
bounds[i].1
} else {
bounds[i].0
}
}).collect())
} else {
let rmi = rnd.next_u32() as usize % m;
let a = &mat[rmi];
let mut next_mat = Vec::with_capacity(m - 1);
for i in 0 .. m {
if i != rmi {
next_mat.push(mat[i].clone());
}
}
// eprintln!("call from {}", line!() + 1);
let mut v = seidel_lp(rnd, d, c, &next_mat, bounds)?;
{
let value = a.iter().zip(&v).fold(0.0, |sum, (&x, &y)| sum + x * y);
if value <= a[d] {
return Some(v);
}
}
let k = (0 .. d).rev().find(|&i| !eps_eq(a[i], 0.0))?;
let mut next_bounds = vec![];
for i in 0 .. d {
if i != k {
next_bounds.push(bounds[i]);
}
}
let mut bar_mat = vec![Vec::with_capacity(d); m + 1];
for mi in 0 .. m - 1 {
let ratio = next_mat[mi][k] / a[k];
for i in 0 ..= d {
if i != k {
bar_mat[mi].push(next_mat[mi][i] - ratio * a[i]);
}
}
}
let mut bar_c = Vec::with_capacity(d - 1);
{
let ratio = c[k] / a[k];
for i in 0 .. d {
if i != k {
bar_c.push(c[i] - ratio * a[i]);
}
}
}
for i in 0 .. d {
if i != k {
let x = -(a[k].recip() * a[i]);
bar_mat[m - 1].push(x);
bar_mat[m].push(x);
}
}
bar_mat[m - 1].push(bounds[k].1);
bar_mat[m].push(bounds[k].0);
// eprintln!("call from {}", line!() + 1);
v = seidel_lp(rnd, d - 1, &bar_c, &bar_mat, &next_bounds)?;
v.insert(k, 0.0);
let s = a.iter().zip(&v).fold(0.0, |sum, (&x, &y)| sum + x * y);
v[k] = (a[d] - s) / a[k];
Some(v)
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0