From ac1f723d39b6d25903237af86a7319209373731b Mon Sep 17 00:00:00 2001 From: mathiasmagnusson Date: Fri, 9 Dec 2022 18:01:29 +0100 Subject: Code jam --- code-jam22/round1b/a-se-dat-ab/Cargo.lock | 7 ++ code-jam22/round1b/a-se-dat-ab/Cargo.toml | 8 ++ .../round1b/a-se-dat-ab/src/local_testing_tool.py | 131 +++++++++++++++++++++ code-jam22/round1b/a-se-dat-ab/src/main.rs | 37 ++++++ code-jam22/round1b/controlled-inflation/Cargo.lock | 7 ++ code-jam22/round1b/controlled-inflation/Cargo.toml | 8 ++ .../round1b/controlled-inflation/src/main.rs | 50 ++++++++ code-jam22/round1b/pancake-deque/Cargo.lock | 7 ++ code-jam22/round1b/pancake-deque/Cargo.toml | 8 ++ code-jam22/round1b/pancake-deque/src/main.rs | 35 ++++++ 10 files changed, 298 insertions(+) create mode 100644 code-jam22/round1b/a-se-dat-ab/Cargo.lock create mode 100644 code-jam22/round1b/a-se-dat-ab/Cargo.toml create mode 100644 code-jam22/round1b/a-se-dat-ab/src/local_testing_tool.py create mode 100644 code-jam22/round1b/a-se-dat-ab/src/main.rs create mode 100644 code-jam22/round1b/controlled-inflation/Cargo.lock create mode 100644 code-jam22/round1b/controlled-inflation/Cargo.toml create mode 100644 code-jam22/round1b/controlled-inflation/src/main.rs create mode 100644 code-jam22/round1b/pancake-deque/Cargo.lock create mode 100644 code-jam22/round1b/pancake-deque/Cargo.toml create mode 100644 code-jam22/round1b/pancake-deque/src/main.rs (limited to 'code-jam22/round1b') diff --git a/code-jam22/round1b/a-se-dat-ab/Cargo.lock b/code-jam22/round1b/a-se-dat-ab/Cargo.lock new file mode 100644 index 0000000..dfb0ec3 --- /dev/null +++ b/code-jam22/round1b/a-se-dat-ab/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "a-se-dat-ab" +version = "0.1.0" diff --git a/code-jam22/round1b/a-se-dat-ab/Cargo.toml b/code-jam22/round1b/a-se-dat-ab/Cargo.toml new file mode 100644 index 0000000..c2064ae --- /dev/null +++ b/code-jam22/round1b/a-se-dat-ab/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "a-se-dat-ab" +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/a-se-dat-ab/src/local_testing_tool.py b/code-jam22/round1b/a-se-dat-ab/src/local_testing_tool.py new file mode 100644 index 0000000..63015fb --- /dev/null +++ b/code-jam22/round1b/a-se-dat-ab/src/local_testing_tool.py @@ -0,0 +1,131 @@ +"""judge.py for asedatab.""" + +# Usage: `judge.py test_number`, where the argument test_number is 0 (visible) +# This can also be run as `python3 testing_tool.py test_number`. + +from __future__ import print_function +import sys +import random + +# Use raw_input in Python2. +try: + input = raw_input +except NameError: + pass + +T = 100 +S = 8 +MAX_TURNS = 300 + +INVALID_OUTPUT = -1 +RUN_OUT_OF_TURNS = -1 + +class Error(Exception): + pass + +INVALID_LINE_ERROR = "Couldn't read a valid line." +RUN_OUT_OF_TURNS_ERROR = "Run out of turns" +UNEXPECTED_LENGTH = "Expect line with length {}, but actually get {}".format +UNEPECTED_CHAR = "Input contains unexpected character {}".format +EXCEPTION_AFTER_END_ERROR = "Exception raised while reading input after all cases finish." +ADDITIONAL_INPUT_ERROR = "Additional input after all cases finish: {}".format + +CASE_FAILED_ERROR = "Case #{} failed: {}".format + +def ReadValue(line): + line = line.strip() + if len(line) != S: + raise Error(UNEXPECTED_LENGTH(S, len(line))) + for c in line: + if c not in {'1', '0'}: + raise Error(UNEPECTED_CHAR(c)) + return line + +def GetNewRecord(old_record, newp): + new_record = "" + for i in range(S): + new_record += '1' if old_record[i] != newp[i] else '0' + return new_record + +def GetNumberOfOne(record): + number_of_one = 0 + for i in range(S): + number_of_one += 1 if record[i] == '1' else 0 + return number_of_one + +def RunCase(): + def Output(line): + print(line) + sys.stdout.flush() + + # choose a random record that is not all 0 + record = "0"*S + while record == "0"*S: + record = "" + for i in range(S): + record += chr(random.randrange(2) + ord('0')) + + for i in range(MAX_TURNS): + try: + line = input() + p = ReadValue(line) + r = random.randrange(S) + # right rotate r is same as left rotate (S - r) + r = S - r + newp = p[r:] + p[:r] + record = GetNewRecord(record, newp) + number_of_one = GetNumberOfOne(record) + if number_of_one == 0: + # output 0 if the record is set to 0 and mark the test as completed. + Output(0) + return True + elif i < MAX_TURNS - 1: + # output the number of 1s in the record if it isn't the last turn + Output(number_of_one) + else: + # output -1 (Run out of turns) if it is the last turn and the record + # is not yet set to 0. Also mark the test as failed + Output(RUN_OUT_OF_TURNS) + return False + except Error as err: + Output(INVALID_OUTPUT) + raise Error(err) + except: + Output(INVALID_OUTPUT) + raise Error(INVALID_LINE_ERROR) + +def RunCases(t): + for i in range(1, t + 1): + # The implementation of randomness here is not guaranteed to match the + # implementation of randomness in the real judge. + random.seed(2 + i) + try: + res = RunCase() + if not res: + raise Error(RUN_OUT_OF_TURNS_ERROR) + except Error as err: + raise Error(CASE_FAILED_ERROR(i, err)) + + try: + extra_input = input() + except Exception: + return + raise Error(ADDITIONAL_INPUT_ERROR(extra_input[:100])) + +def main(): + try: + print(T) + sys.stdout.flush() + try: + RunCases(T) + except Error as err: + print(str(err)[:1000], file=sys.stderr) + sys.exit(1) + except Exception as exception: + print(INVALID_OUTPUT) + sys.stdout.flush() + print(('JUDGE_ERROR! Internal judge exception: {}'.format(exception)) + [:1000], file=sys.stderr) + +if __name__ == "__main__": + main() diff --git a/code-jam22/round1b/a-se-dat-ab/src/main.rs b/code-jam22/round1b/a-se-dat-ab/src/main.rs new file mode 100644 index 0000000..a0cbb6b --- /dev/null +++ b/code-jam22/round1b/a-se-dat-ab/src/main.rs @@ -0,0 +1,37 @@ +use std::io::{stdin, stdout, BufRead, Write}; + +fn main() { + let stdin = stdin(); + let mut lines = stdin.lock().lines().map(|l| l.unwrap()); + let mut line = || lines.next().unwrap(); + let stdout = stdout(); + let mut stdout = stdout.lock(); + + let mut state = 8473859; + let mut r = || { + state = state * 252533 % 33554393; + state + }; + + for _ in 1u8..=line().parse().unwrap() { + stdout.write_all(b"00000000\n").unwrap(); + loop { + let n = line().parse::().unwrap(); + if n == -1 { + return; // Wrong answer + } + if n == 0 { + break; + } + let mut out = *b"00000000\n"; + for _ in 0..n { + let mut v = r() % 8; + while out[v] != b'0' { + v = r() % 8; + } + out[v] = b'1'; + } + stdout.write_all(&out).unwrap(); + } + } +} 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::().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::>(); + + 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)); + } + } +} diff --git a/code-jam22/round1b/pancake-deque/Cargo.lock b/code-jam22/round1b/pancake-deque/Cargo.lock new file mode 100644 index 0000000..d8d3902 --- /dev/null +++ b/code-jam22/round1b/pancake-deque/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "pancake-deque" +version = "0.1.0" diff --git a/code-jam22/round1b/pancake-deque/Cargo.toml b/code-jam22/round1b/pancake-deque/Cargo.toml new file mode 100644 index 0000000..24aa3a3 --- /dev/null +++ b/code-jam22/round1b/pancake-deque/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "pancake-deque" +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/pancake-deque/src/main.rs b/code-jam22/round1b/pancake-deque/src/main.rs new file mode 100644 index 0000000..9b0685b --- /dev/null +++ b/code-jam22/round1b/pancake-deque/src/main.rs @@ -0,0 +1,35 @@ +use std::{ + collections::VecDeque, + io::{stdin, Read}, +}; + +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::().unwrap()); + let mut get = || ints.next().unwrap(); + + for case in 0..get() { + let n = get(); + let mut ds: VecDeque<_> = (0..n).map(|_| get()).collect(); + let mut ans = 0; + let mut max = 0; + while !ds.is_empty() { + let f = ds.front().unwrap(); + let b = ds.back().unwrap(); + let d = if f < b { + ds.pop_front().unwrap() + } else { + ds.pop_back().unwrap() + }; + if d >= max { + ans += 1; + max = d; + } + } + + println!("Case #{}: {}", case + 1, ans); + } +} -- cgit v1.2.3