Code jam

3 files changed, 65 insertions, 0 deletions

diff --git a/code-jam22/round1b/controlled-inflation/Cargo.lock b/code-jam22/round1b/controlled-inflation/Cargo.lock
new file mode 100644
index 0000000..2683c5a
--- /dev/null
+++ b/code-jam22/round1b/controlled-inflation/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "controlled-inflation"
+version = "0.1.0"
diff --git a/code-jam22/round1b/controlled-inflation/Cargo.toml b/code-jam22/round1b/controlled-inflation/Cargo.toml
new file mode 100644
index 0000000..a28fdcd
--- /dev/null
+++ b/code-jam22/round1b/controlled-inflation/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "controlled-inflation"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
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));
+        }
+    }
+}