From ac1f723d39b6d25903237af86a7319209373731b Mon Sep 17 00:00:00 2001
From: mathiasmagnusson <mathiasmagnussons@gmail.com>
Date: Fri, 9 Dec 2022 18:01:29 +0100
Subject: Code jam

---
 .../round1b/controlled-inflation/src/main.rs       | 50 ++++++++++++++++++++++
 1 file changed, 50 insertions(+)
 create mode 100644 code-jam22/round1b/controlled-inflation/src/main.rs

(limited to 'code-jam22/round1b/controlled-inflation/src/main.rs')

diff --git a/code-jam22/round1b/controlled-inflation/src/main.rs b/code-jam22/round1b/controlled-inflation/src/main.rs
new file mode 100644
index 0000000..6204dd1
--- /dev/null
+++ b/code-jam22/round1b/controlled-inflation/src/main.rs
@@ -0,0 +1,50 @@
+use std::{
+    cmp::Reverse,
+    collections::BinaryHeap,
+    io::{stdin, Read},
+    usize,
+};
+
+fn diff(a: usize, b: usize) -> usize {
+    a.max(b) - a.min(b)
+}
+
+fn main() {
+    let mut input = String::new();
+    stdin().lock().read_to_string(&mut input).unwrap();
+    let mut ints = input
+        .split_ascii_whitespace()
+        .map(|i| i.parse::<usize>().unwrap());
+    let mut get = || ints.next().unwrap();
+
+    for case in 1..=get() {
+        let (n, p) = (get(), get());
+        let xs = (0..n)
+            .map(|_| {
+                let (mut min, mut max) = (usize::MAX, 0);
+                for _ in 0..p {
+                    let x = get();
+                    min = min.min(x);
+                    max = max.max(x);
+                }
+                (min, max)
+            })
+            .collect::<Vec<(_, _)>>();
+
+        let mut q = BinaryHeap::new();
+        q.push((Reverse(0), 0, 0));
+        while let Some((Reverse(dist), i, v)) = q.pop() {
+            // eprintln!("dist = {}; i = {}; v = {}", dist, i, v);
+            if i == n {
+                println!("Case #{}: {}", case, dist);
+                break;
+            }
+            let (min, max) = xs[i];
+
+            let dist_a = dist + diff(v, min) + diff(min, max);
+            q.push((Reverse(dist_a), i + 1, max));
+            let dist_b = dist + diff(v, max) + diff(max, min);
+            q.push((Reverse(dist_b), i + 1, min));
+        }
+    }
+}
-- 
cgit v1.2.3