Submission #2555045

---

Source Code Expand

use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn naive(seq: &mut Vec<i64>, cnt: usize) -> usize {
    let n = seq.len();
    for i in 0..cnt {
        seq.sort();
        seq.reverse();
        if seq[0] < n as i64 {
            return i;
        }
        seq[0] -= n as i64;
        for j in 1..n {
            seq[j] += 1;
        }
    }
    cnt
}

fn main() {
    let n = read::<usize>();
    let mut seq = vec![0i64; n];
    for i in 0..n {
        seq[i] = read::<i64>();
    }
    let mut ans = 0;
    ans += naive(&mut seq, 100);
    if seq[n - 1] >= n as i64 {
        for i in 0..n {
            let cnt = std::cmp::max(seq[i] / (n as i64 + 1) - 1, 0);
            ans += (n + 1) * cnt as usize;
            seq[i] -= cnt * (n as i64 + 1);
            assert!(seq[i] >= n as i64);
        }
    }
    ans += naive(&mut seq, 10000);
    // println!("{:?}", seq);
    println!("{}", ans);
}

Submission Info

Judge Result