use std::num::Saturating; use proconio::input; fn main() { input! { n: u128, a: u128, b: u128, c: u128, d: u128, e: u128, f: u128, } let p = calc(n, a, b, c); let q = calc(n, d, e, f); if p < q { println!("KCPC"); } else if p > q { println!("KUPC"); } else { println!("Same"); } } fn calc(n: u128, x: u128, y: u128, z: u128) -> u128 { let mut ng = 0u128; let mut ok = n; while ok.abs_diff(ng) > 1 { let mid = ok.midpoint(ng); if calc2(x, y, z, mid) >= n { ok = mid; } else { ng = mid; } } ok } fn calc2(x: u128, y: u128, z: u128, m: u128) -> u128 { let x = Saturating(x); let y = Saturating(y); let z = Saturating(z); let m = Saturating(m); let offset = x * m; let (q, r) = (m / y, m % y); let add = q * (q - Saturating(1)) / Saturating(2) * z; let add2 = r * q * z; (offset + add + add2).0 } #[cfg(test)] mod tests { use rand::RngExt; use super::*; fn testcase(rng: &mut impl rand::Rng) -> (u128, u128, u128, u128) { let n: u128 = rng.random_range(1..10); let a: u128 = rng.random_range(1..10); let b: u128 = rng.random_range(1..10); let c: u128 = rng.random_range(1..10); (n, a, b, c) } fn naive(n: u128, a: u128, b: u128, c: u128) -> u128 { let mut ans = 0; for i in 0.. { ans += a + i / b * c; if ans >= n { return i + 1; } } unreachable!() } #[test] fn stress() { const T: usize = 100; let failed = vec![(7, 1, 1, 1)]; for (n, a, b, c) in failed { let expected = naive(n, a, b, c); let actual = calc(n, a, b, c); assert_eq!(expected, actual, "{n} {a} {b} {c}"); } let mut rng = rand::rng(); for _ in 0..T { let (n, a, b, c) = testcase(&mut rng); let expected = naive(n, a, b, c); let actual = calc(n, a, b, c); assert_eq!(expected, actual, "{n} {a} {b} {c}"); } } }