結果

問題 No.381 名声値を稼ごう Extra
ユーザー Keigo Oka
提出日時 2019-04-19 20:03:07
言語 Rust
(1.37.0)
結果
AC  
実行時間 4,854 ms
コード長 28,128 Byte
コンパイル時間 1,624 ms
使用メモリ 2,844 KB
最終ジャッジ日時 2019-11-15 04:53:30

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 2 ms
960 KB
input AC 4,854 ms
2,844 KB
テストケース一括ダウンロード
コンパイルメッセージ
warning: unused doc comment
   --> Main.rs:794:5
    |
794 | /     /// AOJ National Budget
795 | |     // let n = sc.next::<i32>();
796 | |     // for _ in 0..n {
797 | |     //     let a = sc.next::<BigUint>();
...   |
806 | |
807 | |     /// yukicoder 381
    | |_____________________^
808 |       let i = sc.next::<BigUint>();
    |       ----------------------------- rustdoc does not generate documentation for statements
    |
    = note: #[warn(unused_doc_comments)] on by default

ソースコード

diff #
#![allow(non_snake_case, unused_imports)]
//////////////////////////////// LIBRARY START ////////////////////////////////
#[macro_use]
pub mod contest {
    #[macro_use]
    pub mod num {
        pub use self::biguint::*;
        pub use self::num::*;
        #[macro_use]
        pub mod num {
            use std::cmp::PartialEq;
            use std::ops::*;

            pub trait NumOps<Rhs = Self, Output = Self>:
                Add<Rhs, Output = Output>
                + Sub<Rhs, Output = Output>
                + Mul<Rhs, Output = Output>
                + Div<Rhs, Output = Output>
                + Rem<Rhs, Output = Output>
            {
            }

            pub trait RefNum<Base>: NumOps<Base, Base> + for<'r> NumOps<&'r Base, Base> {}

            pub trait Num: Zero + One + RefNum<Self> + PartialEq<Self>
            where
                Self: Sized,
            {
            }

            pub trait Zero {
                fn zero() -> Self;
            }

            pub trait One {
                fn one() -> Self;
            }

            macro_rules! impl_num {
                ( $t: ty, $zero: expr, $one: expr) => {
                    impl Zero for $t {
                        fn zero() -> $t {
                            $zero
                        }
                    }
                    impl One for $t {
                        fn one() -> $t {
                            $one
                        }
                    }
                    impl NumOps<$t, $t> for $t {}
                    impl<'r> NumOps<&'r $t, $t> for $t {}
                    impl RefNum<$t> for $t {}
                    impl Num for $t {}
                };
            }

            impl_num!(i32, 0, 1);
            impl_num!(i64, 0, 1);
            impl_num!(f32, 0.0, 1.0);
            impl_num!(f64, 0.0, 1.0);

            #[cfg(test)]
            mod test {
                macro_rules! assert_op {
        ($left:ident $op:tt $right:ident == $expected:expr) => {
            assert_eq!((&$left) $op (&$right), $expected);
            assert_eq!((&$left) $op $right.clone(), $expected);
            assert_eq!($left.clone() $op (&$right), $expected);
            assert_eq!($left.clone() $op $right.clone(), $expected);
        };
    }

                #[test]
                fn test_it() {
                    let a = 3;
                    let b = 2;
                    assert_op!(a * b == 6);
                    assert_op!(a + b == 5);
                }
            }
        }
        #[macro_use]
        pub mod algorithm {
            pub fn add3(a: u32, b: u32, carry: bool) -> (u32, bool) {
                let (x, c) = a.overflowing_add(b);
                if !carry {
                    return (x, c);
                }
                let (x2, c2) = x.overflowing_add(1);
                (x2, c || c2)
            }
            pub fn sub3(a: u32, b: u32, carry: bool) -> (u32, bool) {
                let (x, c) = a.overflowing_sub(b);
                if !carry {
                    return (x, c);
                }
                let (x2, c2) = x.overflowing_sub(1);
                (x2, c || c2)
            }
        }
        #[macro_use]
        pub mod biguint {
            use std;
            use std::cmp::Ordering;
            use std::ops::*;

            use super::algorithm;
            use super::{One, Zero};

            #[derive(Clone, Debug, Hash)]
            pub struct BigUint {
                // [3, 2] represents 3 + (2 << 32).
                data: Vec<u32>,
            }

            impl std::fmt::Display for BigUint {
                fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                    if self.data.len() == 0 {
                        return write!(f, "0");
                    }

                    let base = 1_000_000_000u64;
                    // [3, 2] represents 3 + (2 * base).
                    let mut res = vec![];
                    for d in self.data.iter().rev() {
                        let mut carry = *d as u64;
                        for x in res.iter_mut() {
                            let v = (*x << 32) + carry;
                            *x = v % base;
                            carry = v / base;
                        }
                        while carry > 0 {
                            res.push(carry % base);
                            carry /= base;
                        }
                    }
                    debug_assert_ne!(res.last(), Some(&0));
                    let (rest, top) = res.split_at(res.len() - 1);
                    write!(f, "{}", top[0])?;
                    for x in rest.iter().rev() {
                        write!(f, "{:09}", x)?;
                    }
                    Ok(())
                }
            }

            impl PartialEq for BigUint {
                #[inline]
                fn eq(&self, other: &BigUint) -> bool {
                    match self.cmp(other) {
                        Ordering::Equal => true,
                        _ => false,
                    }
                }
            }

            impl Eq for BigUint {}

            impl PartialOrd for BigUint {
                #[inline]
                fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
                    Some(self.cmp(other))
                }
            }

            impl Ord for BigUint {
                #[inline]
                fn cmp(&self, other: &BigUint) -> Ordering {
                    cmp_slice(&self.data[..], &other.data[..])
                }
            }

            fn cmp_slice(a: &[u32], b: &[u32]) -> Ordering {
                debug_assert!(a.last() != Some(&0));
                debug_assert!(b.last() != Some(&0));
                if a.len() < b.len() {
                    return Ordering::Less;
                } else if a.len() > b.len() {
                    return Ordering::Greater;
                }
                for i in (0..a.len()).rev() {
                    let c = a[i].cmp(&b[i]);
                    if c != Ordering::Equal {
                        return c;
                    }
                }
                Ordering::Equal
            }

            impl From<u64> for BigUint {
                fn from(mut x: u64) -> BigUint {
                    let mut data = vec![];
                    while x > 0 {
                        data.push((x & u32::max_value() as u64) as u32);
                        x >>= 32;
                    }
                    BigUint { data: data }
                }
            }

            #[derive(Debug, PartialEq)]
            pub struct ParseBigUintError;

            impl std::str::FromStr for BigUint {
                type Err = ParseBigUintError;
                fn from_str(s: &str) -> Result<BigUint, ParseBigUintError> {
                    let s = s.as_bytes();
                    if s.iter().any(|c| *c < b'0' || b'9' < *c) {
                        return Err(ParseBigUintError);
                    }

                    fn parse_u32(s: &[u8]) -> u32 {
                        s.iter().fold(0u32, |acc, c| acc * 10 + (*c - b'0') as u32)
                    }

                    let mut data = vec![];
                    let base = 1_000_000_000u64;
                    let chunk_size = 9;

                    let (head, tail) = s.split_at(s.len() % chunk_size);
                    if !head.is_empty() {
                        data.push(parse_u32(head));
                    }
                    debug_assert_eq!(tail.len() % chunk_size, 0);
                    for ch in tail.chunks(chunk_size) {
                        // data *= base
                        let mut carry = parse_u32(ch) as u64;
                        for d in data.iter_mut() {
                            let v = *d as u64 * base + carry;
                            *d = v as u32;
                            carry = v >> 32;
                        }
                        if carry > 0 {
                            data.push(carry as u32);
                        }
                    }
                    // For "0" etc.
                    while data.last() == Some(&0) {
                        data.pop();
                    }
                    debug_assert_ne!(data.last(), Some(&0));

                    Ok(BigUint { data: data })
                }
            }

            impl Zero for BigUint {
                fn zero() -> BigUint {
                    BigUint::from(0)
                }
            }
            impl One for BigUint {
                fn one() -> BigUint {
                    BigUint::from(1)
                }
            }

            impl<'a, 'b> Add<&'b BigUint> for &'a BigUint {
                type Output = BigUint;
                fn add(self, other: &'b BigUint) -> BigUint {
                    let n = std::cmp::max(self.data.len(), other.data.len());
                    let mut data = vec![];
                    let mut carry = false;
                    for i in 0..n {
                        let a = self.data.get(i).map_or(0, |x| *x);
                        let b = other.data.get(i).map_or(0, |x| *x);
                        let (x, c) = algorithm::add3(a, b, carry);
                        carry = c;
                        data.push(x);
                    }
                    if carry {
                        data.push(1);
                    }
                    debug_assert_ne!(data.last(), Some(&0));
                    BigUint { data: data }
                }
            }
            impl<'a, 'b> Sub<&'b BigUint> for &'a BigUint {
                type Output = BigUint;
                fn sub(self, other: &'b BigUint) -> BigUint {
                    debug_assert!(self >= other);
                    let n = std::cmp::max(self.data.len(), other.data.len());
                    let mut data = vec![];
                    let mut carry = false;
                    for i in 0..n {
                        let a = self.data.get(i).map_or(0, |x| *x);
                        let b = other.data.get(i).map_or(0, |x| *x);
                        let (x, c) = algorithm::sub3(a, b, carry);
                        carry = c;
                        data.push(x);
                    }
                    debug_assert!(!carry);
                    while data.last() == Some(&0) {
                        data.pop();
                    }
                    debug_assert_ne!(data.last(), Some(&0));
                    BigUint { data: data }
                }
            }
            impl<'a, 'b> Mul<&'b BigUint> for &'a BigUint {
                type Output = BigUint;
                fn mul(self, other: &'b BigUint) -> BigUint {
                    if self == &BigUint::zero() || other == &BigUint::zero() {
                        return BigUint::zero();
                    }
                    let n = self.data.len() + other.data.len() - 1;
                    let mut data = vec![];
                    let mut carry = 0u64;
                    let u32max = u32::max_value() as u64;
                    for i in 0..n {
                        //        2   1   0 - self (j)
                        //            1   0 - other(k)
                        //  ----------------
                        //       2,0 1,0 0,0
                        //   2,1 1,1 0,1
                        //    |   |   |   |
                        //    3   2   1   0 - i
                        let mut digit = carry & u32max;
                        carry >>= 32;

                        let from = if i + 1 >= other.data.len() {
                            i + 1 - other.data.len()
                        } else {
                            0
                        };
                        for j in from..std::cmp::min(i + 1, self.data.len()) {
                            let k = i - j;
                            let x = self.data[j] as u64;
                            let y = other.data[k] as u64;
                            let val = digit + x * y;

                            digit = val & u32max;
                            carry += val >> 32;
                        }
                        debug_assert!(digit <= u32max);
                        data.push(digit as u32);
                    }
                    if carry > 0 {
                        debug_assert!(carry <= u32max);
                        data.push(carry as u32);
                    }
                    debug_assert_ne!(data.last(), Some(&0));

                    BigUint { data: data }
                }
            }
            macro_rules! impl_others {
                ($tr:tt $func: ident) => {
                    impl<'a> $tr<BigUint> for &'a BigUint {
                        type Output = BigUint;
                        fn $func(self, x: BigUint) -> BigUint {
                            self.$func(&x)
                        }
                    }
                    impl<'b> $tr<&'b BigUint> for BigUint {
                        type Output = BigUint;
                        fn $func(self, x: &'b BigUint) -> BigUint {
                            (&self).$func(x)
                        }
                    }
                    impl $tr<BigUint> for BigUint {
                        type Output = BigUint;
                        fn $func(self, x: BigUint) -> BigUint {
                            (&self).$func(&x)
                        }
                    }
                };
            }
            impl_others!(Add add);
            impl_others!(Sub sub);
            impl_others!(Mul mul);

            impl BigUint {
                pub fn count_ones(&self) -> u32 {
                    self.data.iter().fold(0, |acc, x| acc + x.count_ones())
                }
            }

            #[cfg(test)]
            mod test {
                use super::*;
                macro_rules! assert_op {
        ($left:ident $op:tt $right:ident == $expected:expr) => {
            assert_eq!((&$left) $op (&$right), $expected);
            assert_eq!((&$left) $op $right.clone(), $expected);
            assert_eq!($left.clone() $op (&$right), $expected);
            assert_eq!($left.clone() $op $right.clone(), $expected);
        };
    }
                #[test]
                fn test_add() {
                    let a = BigUint::from(3);
                    let b = BigUint::from(2);
                    let c = BigUint::from(5);
                    assert_op!(a + b == c);
                }
                #[test]
                fn test_add_zero() {
                    let a = BigUint::zero();
                    let b = BigUint::one();
                    assert_op!(a + a == a);
                    assert_op!(a + b == b);
                    assert_op!(b + a == b);
                }
                #[test]
                fn test_add_big() {
                    let a = BigUint::from(3_000_000_000_000);
                    let b = BigUint::from(2_000_000_000_000);
                    let c = BigUint::from(5_000_000_000_000);
                    assert_op!(a + b == c);
                }
                #[test]
                fn test_add_with_carry() {
                    use std;
                    let a = BigUint::from(std::u32::MAX as u64);
                    let b = BigUint::from(1);
                    let c = BigUint::from(std::u32::MAX as u64 + 1);
                    assert_op!(a + b == c);
                }
                #[test]
                fn test_sub() {
                    let a = BigUint::from(3);
                    let b = BigUint::from(2);
                    let c = BigUint::from(5);
                    assert_op!(c - b == a);
                }
                #[test]
                fn test_sub_zero() {
                    let a = BigUint::zero();
                    let b = BigUint::one();
                    assert_op!(b - a == b);
                    assert_op!(a - a == a);
                }
                #[test]
                fn test_sub_big() {
                    let a = BigUint::from(3_000_000_000_000);
                    let b = BigUint::from(2_000_000_000_000);
                    let c = BigUint::from(5_000_000_000_000);
                    assert_op!(c - b == a);
                }
                #[test]
                fn test_sub_with_carry() {
                    use std;
                    let a = BigUint::from(std::u32::MAX as u64);
                    let b = BigUint::from(1);
                    let c = BigUint::from(std::u32::MAX as u64 + 1);
                    assert_op!(c - b == a);
                }
                #[test]
                fn test_mul() {
                    let a = BigUint::from(3);
                    let b = BigUint::from(2);
                    let c = BigUint::from(6);
                    assert_op!(a * b == c);
                }
                #[test]
                fn test_mul_zero() {
                    let a = BigUint::zero();
                    let b = BigUint::one();
                    assert_op!(a * b == a);
                    assert_op!(a * a == a);
                }
                #[test]
                fn test_mul_big() {
                    let a = BigUint::from(3_000_000_000_000);
                    let b = BigUint::from(2_000_000_000_000);
                    let c = BigUint::from(6_000_000_000_000);
                    let d = BigUint::from(1_000_000_000_000);
                    let e = &d * &c;
                    assert_op!(a * b == e);
                }
                #[test]
                fn test_mul_with_carry() {
                    let a = BigUint::from(2);
                    let b = BigUint::from(1u64 << 31);
                    let c = BigUint::from(1u64 << 32);
                    assert_op!(a * b == c);
                }
                #[test]
                fn test_cmp() {
                    let a = BigUint::from(3);
                    let b = BigUint::from(2);
                    let c = BigUint::zero();
                    assert!(a > b);
                    assert!(b < a);
                    assert!(a == a);

                    assert!(c == c);
                    assert!(a > c);
                    assert!(c < a);
                }
                #[test]
                fn test_big_cmp() {
                    let a = BigUint::from(3_000_000_000_000u64);
                    let b = BigUint::from(2_000_000_000_000u64);
                    let c = BigUint::from(2_000_000_000_001u64);

                    assert!(a == a);
                    assert!(a > b);
                    assert!(b < a);
                    assert!(c > b);
                    assert!(b < c);
                }
                macro_rules! assert_from_str {
                    ($a: expr, $b: expr) => {{
                        let a = BigUint::from_str($a).unwrap();
                        let b = BigUint::from($b);
                        assert_eq!(a, b);
                    }};
                }
                #[test]
                fn test_from_str() {
                    use std::str::FromStr;
                    assert_from_str!("0", 0);
                    assert_from_str!("123", 123);
                    assert_from_str!("1000000000", 1000000000);
                    assert_from_str!("10000000000", 10000000000);
                    assert_from_str!("12345678901", 12345678901);
                }
                #[test]
                fn test_from_str_big() {
                    use std::str::FromStr;

                    let base = BigUint::from(1000000000);
                    let a = &base * &base * &base;
                    assert_eq!(BigUint::from_str("1000000000000000000000000000"), Ok(a));
                }

                #[test]
                fn test_fmt() {
                    use std::str::FromStr;
                    assert_eq!("0".to_string(), format!("{}", BigUint::from(0)));
                    assert_eq!("1".to_string(), format!("{}", BigUint::from(1)));
                    assert_eq!(
                        "123456789".to_string(),
                        format!("{}", BigUint::from(123456789))
                    );
                    assert_eq!(
                        "1000000001".to_string(),
                        format!("{}", BigUint::from(1000000001))
                    );
                    assert_eq!(
                        "12345678901".to_string(),
                        format!("{}", BigUint::from(12345678901))
                    );
                    assert_eq!(
                        "123456789012345678901234567890".to_string(),
                        format!(
                            "{}",
                            BigUint::from_str("123456789012345678901234567890").unwrap()
                        )
                    );
                }
            }
        }
    }
    #[macro_use]
    pub mod prelude {
        pub use self::myvec::*;
        #[macro_use]
        pub mod primitive {
            pub trait ToUsize: Sized {
                fn to_usize(self) -> usize;
            }

            impl ToUsize for i32 {
                #[inline]
                fn to_usize(self) -> usize {
                    self as usize
                }
            }

            impl ToUsize for i64 {
                #[inline]
                fn to_usize(self) -> usize {
                    self as usize
                }
            }

            impl ToUsize for usize {
                #[inline]
                fn to_usize(self) -> usize {
                    self
                }
            }
        }
        #[macro_use]
        pub mod myvec {
            use std::fmt;
            use std::iter::FromIterator;
            use std::ops::*;

            pub use super::primitive::ToUsize;

            /// `Vec` indexable with `i32`, `i64` or `usize`.
            #[derive(Clone, Debug, PartialEq, PartialOrd)]
            pub struct MyVec<T>(pub Vec<T>);

            /// Creates `MyVec`
            #[macro_export]
            macro_rules! v {
    ( $( $x:expr ),* ) => {
        MyVec(vec![ $( $x, )* ])
    };
    ( $x:expr ; $n:expr ) => {
        {
            MyVec(vec![$x; $n as usize])
        }
    };
}

            impl<T: fmt::Display> fmt::Display for MyVec<T> {
                fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
                    let n = self.len();
                    for i in 0..n {
                        let r = if i < n - 1 {
                            writeln!(f, "{}", self.0[i])
                        } else {
                            write!(f, "{}", self.0[i])
                        };
                        if r.is_err() {
                            return r;
                        }
                    }
                    Ok(())
                }
            }

            impl<T> Deref for MyVec<T> {
                type Target = Vec<T>;

                #[inline]
                fn deref(&self) -> &Vec<T> {
                    &self.0
                }
            }

            impl<T> DerefMut for MyVec<T> {
                #[inline]
                fn deref_mut(&mut self) -> &mut Vec<T> {
                    &mut self.0
                }
            }

            impl<T> FromIterator<T> for MyVec<T> {
                #[inline]
                fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
                    MyVec(Vec::from_iter(iter))
                }
            }

            impl<T, I: ToUsize> Index<I> for MyVec<T> {
                type Output = T;

                #[inline]
                fn index(&self, i: I) -> &T {
                    &self.0[i.to_usize()]
                }
            }

            impl<T, I: ToUsize> IndexMut<I> for MyVec<T> {
                #[inline]
                fn index_mut(&mut self, i: I) -> &mut T {
                    &mut self.0[i.to_usize()]
                }
            }

            #[test]
            fn test_myvec() {
                let mut x = v![3, 2, 1];
                x.sort();
                assert_eq!(vec![1, 2, 3], *x);
                let i = 1i32;
                assert_eq!(2, x[i]);
                x[i] = 3;
                assert_eq!(3, x[i]);
                let u = 1usize;
                assert_eq!(3, x[u]);
                x[u] = 2;
                assert_eq!(2, x[u]);
                assert_eq!(2, x[1]);

                assert_eq!("MyVec([1, 2, 3])", format!("{:?}", x));
                assert_eq!(v![1, 2, 3], x);

                assert_eq!("1\n2\n3", format!("{}", x));

                let mut y = v![v![1, 2]; 3];
                y[0][0] = 2;
                assert_eq!(vec![2, 2], *y[0]);
                assert_eq!(vec![1, 2], *y[1]);
            }
        }
    }
    #[macro_use]
    pub mod io {
        /// Scanner
        ///
        /// # Example
        /// ```
        /// use contest::io::Scanner;
        /// let mut sc = Scanner::new("1 2 \n\n \r\t \n 3".as_bytes());
        /// assert_eq!("1".to_string(), sc.next::<String>());
        /// let v = sc.nexts(2);
        /// assert_eq!(2i32, v[0]);
        /// assert_eq!(3i32, v[1]);
        ///
        /// // To create a scanner from stdin:
        /// Scanner::new(std::io::stdin());
        /// ```
        use std;
        use std::io;
        use std::io::BufRead;

        use super::prelude::MyVec;

        pub struct Scanner<R: io::Read> {
            br: io::BufReader<R>,
            // Read tokens are stored in reversed order per line.
            buf: Vec<String>,
        }

        pub fn new<R: io::Read>(r: R) -> Scanner<R> {
            Scanner::new(r)
        }

        impl<R: io::Read> Scanner<R> {
            #[inline]
            pub fn new(r: R) -> Scanner<R> {
                Scanner {
                    br: io::BufReader::new(r),
                    buf: vec![],
                }
            }
            #[inline]
            pub fn next<T>(&mut self) -> T
            where
                T: std::str::FromStr,
                T::Err: std::fmt::Debug,
            {
                self.next_string()
                    .map(|s| s.parse::<T>().expect("Parse failed: "))
                    .expect("Unexpected EOF")
            }
            #[inline]
            pub fn nexts<T>(&mut self, n: i32) -> MyVec<T>
            where
                T: std::str::FromStr,
                T::Err: std::fmt::Debug,
            {
                let mut res = v![];
                for _ in 0..n {
                    res.push(self.next());
                }
                res
            }
            fn next_string(&mut self) -> Option<String> {
                self.buf.pop().or_else(|| match self.update() {
                    true => self.next_string(),
                    false => None,
                })
            }
            #[inline]
            fn update(&mut self) -> bool {
                let mut s = String::new();
                let res = self.br.read_line(&mut s);
                match res.expect("I/O error.") {
                    0 => false,
                    _ => {
                        self.buf = s.split_whitespace().map(|x| x.to_string()).rev().collect();
                        true
                    }
                }
            }
        }

        #[test]
        fn test_next() {
            let mut sc = new("hoge".as_bytes());
            let s: String = sc.next();
            assert_eq!("hoge", s);
        }
    }
}
//////////////////////////////// LIBRARY END ////////////////////////////////

use contest::io::Scanner;
use contest::num::BigUint;
use contest::prelude::MyVec;

fn main() {
    let mut sc = Scanner::new(std::io::stdin());
    /// AOJ National Budget
    // let n = sc.next::<i32>();
    // for _ in 0..n {
    //     let a = sc.next::<BigUint>();
    //     let b = sc.next::<BigUint>();
    //     let res = format!("{}", a + b);
    //     if res.len() > 80 {
    //         println!("overflow");
    //     } else {
    //         println!("{}", res);
    //     }
    // }

    /// yukicoder 381
    let i = sc.next::<BigUint>();
    println!("{}", i.count_ones());
}
0