Skip to content

Instantly share code, notes, and snippets.

@robert-king

robert-king/challenge-nine.rs

Created March 23, 2022 05:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save robert-king/b2cf1e1273a241689944293a2b8736d0 to your computer and use it in GitHub Desktop.
Save robert-king/b2cf1e1273a241689944293a2b8736d0 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
challenge-nine.rs
fn main() {
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
let t: usize = sc.read();
for case_num in 1..=t {
let mut v: Vec<usize> = sc.chars().into_iter().map(|c| {
((c as u8) - b'0') as usize
}).collect();
let s = v.iter().sum::<usize>() % 9;
let x = if s == 0 {
0
} else {
9 - s
};
let mut ok = false;
for i in 0..v.len() {
if x == 0 && i == 0 {
continue;
}
if v[i] > x {
v.insert(i, x);
ok = true;
break;
}
}
if !ok {
v.push(x);
}
let mut out = vec![];
for i in 0..v.len() {
out.push(v[i].to_string());
}
let ans = out.join("");
sc.write(
format!("Case #{}: {}", case_num, ans)
);
sc.write("\n");
}
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> IO<R, W> {
IO(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
use std::io::Write;
self.1.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn usize0(&mut self) -> usize {
self.read::<usize>() - 1
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
pub fn binary_vec(&mut self) -> Vec<u8> {
self.read::<String>()
.bytes()
.map(|b| b - b'0')
.collect()
}
}
Raw
interesting-integers.rs
// https://codingcompetitions.withgoogle.com/kickstart/round/00000000008cb33e/00000000009e73ea
use std::collections::HashMap;
fn f(dig: &Vec<usize>, i: usize, eq: bool, prod: usize, sum: usize, cache: &mut HashMap<(usize, bool, usize, usize), usize>) -> usize {
if i == dig.len() {
if sum > 0 && prod % sum == 0 {
return 1;
}
return 0;
}
let h = (i, eq, prod, sum);
if cache.contains_key(&h) {
return cache[&h];
}
let mut ans = 0;
for d in 0..=9 {
if d > dig[i] && eq {
break;
}
let prod2 = if sum + d > 0 {
prod*d
} else {
1
};
ans += f(dig, i+1, eq && d == dig[i], prod2, sum+d, cache);
}
cache.insert(h, ans);
ans
}
fn digits(mut x: usize) -> Vec<usize> {
let mut v = vec![];
while x > 0 {
v.push(x % 10);
x /= 10;
}
v.reverse();
v
}
fn solve_one(x: usize) -> usize {
let mut cache = HashMap::new();
let dig = digits(x);
f(&dig, 0, true, 1, 0, &mut cache)
}
fn solve_both(a: usize, b: usize) -> usize {
solve_one(b) - solve_one(a-1)
}
fn main() {
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
let t: usize = sc.read();
for case_num in 1..=t {
let (a, b): (usize, usize) = (sc.read(), sc.read());
sc.write(
format!("Case #{}: {}", case_num, solve_both(a, b))
);
sc.write("\n");
}
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> IO<R, W> {
IO(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
use std::io::Write;
self.1.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn usize0(&mut self) -> usize {
self.read::<usize>() - 1
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
pub fn binary_vec(&mut self) -> Vec<u8> {
self.read::<String>()
.bytes()
.map(|b| b - b'0')
.collect()
}
}
Raw
palindrome-free-strings.rs
fn bad(v: &Vec<u8>, k: usize) -> bool {
if k < 4 {
return false;
}
let mut ok = false;
let mut i = k - 4;
let mut j = k;
while i < j {
if v[i] != v[j] {
ok = true;
break;
}
i += 1;
j -= 1;
}
if !ok {
return true;
}
if k == 4 {
return false;
}
let mut i = k - 5;
let mut j = k;
while i < j {
if v[i] != v[j] {
return false;
}
i += 1;
j -= 1;
}
true
}
fn f(v: &mut Vec<u8>, i: usize) -> bool {
if i == v.len() {
return true;
}
if v[i] != 2 {
return !bad(v, i) && f(v, i + 1);
}
v[i] = 1;
if !bad(v, i) && f(v, i+1) {
return true;
}
v[i] = 0;
if !bad(v, i) && f(v, i+1) {
return true;
}
v[i] = 2;
false
}
fn main() {
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
let t: usize = sc.read();
for case_num in 1..=t {
let _n: usize = sc.read();
let mut v: Vec<u8> = sc.chars().into_iter().map(|c| {
match c {
'0' => 0,
'1' => 1,
_ => 2,
}
}).collect();
let ok = f(&mut v, 0);
let ans = if ok {
"POSSIBLE"
} else {
"IMPOSSIBLE"
};
sc.write(
format!("Case #{}: {}", case_num, ans)
);
sc.write("\n");
}
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> IO<R, W> {
IO(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
use std::io::Write;
self.1.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn usize0(&mut self) -> usize {
self.read::<usize>() - 1
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
pub fn binary_vec(&mut self) -> Vec<u8> {
self.read::<String>()
.bytes()
.map(|b| b - b'0')
.collect()
}
}
Raw
speed-typing.rs
fn main() {
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
let t: usize = sc.read();
for case_num in 1..=t {
let v1 = sc.chars();
let v2 = sc.chars();
let mut i = 0;
let mut count = 0;
for j in 0..v2.len() {
if i != v1.len() && v2[j] == v1[i] {
i += 1;
} else {
count += 1;
}
}
if i == v1.len() {
sc.write(
format!("Case #{}: {}", case_num, count)
);
} else {
sc.write(
format!("Case #{}: {}", case_num, "IMPOSSIBLE")
);
}
sc.write("\n");
}
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> IO<R, W> {
IO(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
use std::io::Write;
self.1.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn usize0(&mut self) -> usize {
self.read::<usize>() - 1
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
pub fn binary_vec(&mut self) -> Vec<u8> {
self.read::<String>()
.bytes()
.map(|b| b - b'0')
.collect()
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment