#![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: Add + Sub + Mul + Div + Rem { } pub trait RefNum: NumOps + for<'r> NumOps<&'r Base, Base> {} pub trait Num: Zero + One + RefNum + PartialEq 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, } 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 { 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 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 { 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 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 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(pub Vec); /// Creates `MyVec` #[macro_export] macro_rules! v { ( $( $x:expr ),* ) => { MyVec(vec![ $( $x, )* ]) }; ( $x:expr ; $n:expr ) => { { MyVec(vec![$x; $n as usize]) } }; } impl fmt::Display for MyVec { 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 Deref for MyVec { type Target = Vec; #[inline] fn deref(&self) -> &Vec { &self.0 } } impl DerefMut for MyVec { #[inline] fn deref_mut(&mut self) -> &mut Vec { &mut self.0 } } impl FromIterator for MyVec { #[inline] fn from_iter>(iter: I) -> Self { MyVec(Vec::from_iter(iter)) } } impl Index for MyVec { type Output = T; #[inline] fn index(&self, i: I) -> &T { &self.0[i.to_usize()] } } impl IndexMut for MyVec { #[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::()); /// 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 { br: io::BufReader, // Read tokens are stored in reversed order per line. buf: Vec, } pub fn new(r: R) -> Scanner { Scanner::new(r) } impl Scanner { #[inline] pub fn new(r: R) -> Scanner { Scanner { br: io::BufReader::new(r), buf: vec![], } } #[inline] pub fn next(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { self.next_string() .map(|s| s.parse::().expect("Parse failed: ")) .expect("Unexpected EOF") } #[inline] pub fn nexts(&mut self, n: i32) -> MyVec 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 { 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::(); // for _ in 0..n { // let a = sc.next::(); // let b = sc.next::(); // let res = format!("{}", a + b); // if res.len() > 80 { // println!("overflow"); // } else { // println!("{}", res); // } // } /// yukicoder 381 let i = sc.next::(); println!("{}", i.count_ones()); }