pub struct Writer { writer: BufWriter, } impl Writer { pub fn new(write: W) -> Self { Self { writer: BufWriter::new(write), } } pub fn ln(&mut self, s: S) { writeln!(self.writer, "{}", s).expect("Failed to write.") } pub fn out(&mut self, s: S) { write!(self.writer, "{}", s).expect("Failed to write.") } pub fn join(&mut self, v: &[S], separator: &str) { v.iter().fold("", |sep, arg| { write!(self.writer, "{}{}", sep, arg).expect("Failed to write."); separator }); writeln!(self.writer).expect("Failed to write."); } pub fn bits(&mut self, i: i64, len: usize) { (0..len).for_each(|b| write!(self.writer, "{}", i >> b & 1).expect("Failed to write.")); writeln!(self.writer).expect("Failed to write.") } pub fn flush(&mut self) { let _ = self.writer.flush(); } } pub struct Reader { init: F, buf: VecDeque, } impl R> Iterator for Reader { type Item = String; fn next(&mut self) -> Option { if self.buf.is_empty() { let mut reader = (self.init)(); let mut l = String::new(); reader.read_line(&mut l).unwrap(); self.buf .append(&mut l.split_whitespace().map(ToString::to_string).collect()); } self.buf.pop_front() } } impl R> Reader { pub fn new(init: F) -> Self { let buf = VecDeque::new(); Reader { init, buf } } pub fn v(&mut self) -> T { let s = self.next().expect("Insufficient input."); s.parse().ok().expect("Failed to parse.") } pub fn v2(&mut self) -> (T1, T2) { (self.v(), self.v()) } pub fn v3(&mut self) -> (T1, T2, T3) { (self.v(), self.v(), self.v()) } pub fn v4(&mut self) -> (T1, T2, T3, T4) { (self.v(), self.v(), self.v(), self.v()) } pub fn v5(&mut self) -> (T1, T2, T3, T4, T5) { (self.v(), self.v(), self.v(), self.v(), self.v()) } pub fn vec(&mut self, length: usize) -> Vec { (0..length).map(|_| self.v()).collect() } pub fn vec2(&mut self, length: usize) -> Vec<(T1, T2)> { (0..length).map(|_| self.v2()).collect() } pub fn vec3(&mut self, length: usize) -> Vec<(T1, T2, T3)> { (0..length).map(|_| self.v3()).collect() } pub fn vec4(&mut self, length: usize) -> Vec<(T1, T2, T3, T4)> { (0..length).map(|_| self.v4()).collect() } pub fn chars(&mut self) -> Vec { self.v::().chars().collect() } fn split(&mut self, zero: u8) -> Vec { self.v::() .chars() .map(|c| (c as u8 - zero) as usize) .collect() } pub fn digits(&mut self) -> Vec { self.split(b'0') } pub fn lowercase(&mut self) -> Vec { self.split(b'a') } pub fn uppercase(&mut self) -> Vec { self.split(b'A') } pub fn char_map(&mut self, h: usize) -> Vec> { (0..h).map(|_| self.chars()).collect() } pub fn bool_map(&mut self, h: usize, ng: char) -> Vec> { self.char_map(h) .iter() .map(|v| v.iter().map(|&c| c != ng).collect()) .collect() } pub fn matrix(&mut self, h: usize, w: usize) -> Vec> { (0..h).map(|_| self.vec(w)).collect() } } pub fn to_lr>(range: &R, length: T) -> (T, T) where T: Copy + One + Zero + Add + PartialOrd, { use Bound::{Excluded, Included, Unbounded}; let l = match range.start_bound() { Unbounded => T::zero(), Included(&s) => s, Excluded(&s) => s + T::one(), }; let r = match range.end_bound() { Unbounded => length, Included(&e) => e + T::one(), Excluded(&e) => e, }; assert!(l <= r && r <= length); (l, r) } pub use std::{ cmp::{max, min, Ordering, Reverse}, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}, convert::Infallible, convert::{TryFrom, TryInto}, fmt::{Debug, Display, Formatter}, io::{stdin, stdout, BufRead, BufWriter, Read, Write}, iter::{repeat, Product, Sum}, marker::PhantomData, mem::swap, ops::{ Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Bound, Deref, DerefMut, Div, DivAssign, Index, IndexMut, Mul, MulAssign, Neg, Not, Range, RangeBounds, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign, }, str::{from_utf8, FromStr as FS}, }; #[allow(unused_macros)] macro_rules ! chmin {($ base : expr , $ ($ cmps : expr ) ,+ $ (, ) * ) => {{let cmp_min = min ! ($ ($ cmps ) ,+ ) ; if $ base > cmp_min {$ base = cmp_min ; true } else {false } } } ; } #[allow(unused_macros)] macro_rules ! min {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{if $ a > $ b {$ b } else {$ a } } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{let b = min ! ($ ($ rest ) ,+ ) ; if $ a > b {b } else {$ a } } } ; } #[allow(unused_macros)] macro_rules ! chmax {($ base : expr , $ ($ cmps : expr ) ,+ $ (, ) * ) => {{let cmp_max = max ! ($ ($ cmps ) ,+ ) ; if $ base < cmp_max {$ base = cmp_max ; true } else {false } } } ; } #[allow(unused_macros)] macro_rules ! max {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{if $ a > $ b {$ a } else {$ b } } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{let b = max ! ($ ($ rest ) ,+ ) ; if $ a > b {$ a } else {b } } } ; } pub trait Magma { type M: Clone + PartialEq + Debug; fn op(x: &Self::M, y: &Self::M) -> Self::M; } pub trait Associative {} pub trait Unital: Magma { fn unit() -> Self::M; } pub trait Commutative: Magma {} pub trait Invertible: Magma { fn inv(x: &Self::M) -> Self::M; } pub trait Idempotent: Magma {} pub trait SemiGroup: Magma + Associative {} pub trait Monoid: Magma + Associative + Unital { fn pow(&self, x: Self::M, mut n: usize) -> Self::M { let mut res = Self::unit(); let mut base = x; while n > 0 { if n & 1 == 1 { res = Self::op(&res, &base); } base = Self::op(&base, &base); n >>= 1; } res } } impl Monoid for M {} pub trait CommutativeMonoid: Magma + Associative + Unital + Commutative {} impl CommutativeMonoid for M {} pub trait Group: Magma + Associative + Unital + Invertible {} impl Group for M {} pub trait AbelianGroup: Magma + Associative + Unital + Commutative + Invertible {} impl AbelianGroup for M {} pub trait Band: Magma + Associative + Idempotent {} impl Band for M {} pub trait MapMonoid { type Mono: Monoid; type Func: Monoid; fn op( &self, x: &::M, y: &::M, ) -> ::M { Self::Mono::op(x, y) } fn unit() -> ::M { Self::Mono::unit() } fn apply( &self, f: &::M, value: &::M, ) -> ::M; fn identity_map() -> ::M { Self::Func::unit() } fn compose( &self, f: &::M, g: &::M, ) -> ::M { Self::Func::op(f, g) } } pub trait Zero { fn zero() -> Self; } pub trait One { fn one() -> Self; } pub trait BoundedBelow { fn min_value() -> Self; } pub trait BoundedAbove { fn max_value() -> Self; } # [rustfmt :: skip ] pub trait Integral : 'static + Send + Sync + Copy + Ord + Display + Debug + Add < Output = Self > + Sub < Output = Self > + Mul < Output = Self > + Div < Output = Self > + Rem < Output = Self > + AddAssign + SubAssign + MulAssign + DivAssign + RemAssign + Sum + Product + BitOr < Output = Self > + BitAnd < Output = Self > + BitXor < Output = Self > + Not < Output = Self > + Shl < Output = Self > + Shr < Output = Self > + BitOrAssign + BitAndAssign + BitXorAssign + ShlAssign + ShrAssign + Zero + One + BoundedBelow + BoundedAbove {} macro_rules ! impl_integral {($ ($ ty : ty ) ,* ) => {$ (impl Zero for $ ty {fn zero () -> Self {0 } } impl One for $ ty {fn one () -> Self {1 } } impl BoundedBelow for $ ty {fn min_value () -> Self {Self :: min_value () } } impl BoundedAbove for $ ty {fn max_value () -> Self {Self :: max_value () } } impl Integral for $ ty {} ) * } ; } impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize); pub fn main() { let stdin = stdin(); let stdout = stdout(); solve(Reader::new(|| stdin.lock()), Writer::new(stdout.lock())); } pub fn solve R>(mut reader: Reader, mut writer: Writer) { let n: usize = reader.v(); let mut dp = vec![1 << 60; n + 1]; dp[1] = 1usize; let mut q = VecDeque::new(); q.push_back(1usize); while let Some(v) = q.pop_front() { let c = v.count_ones() as usize; if v + c <= n && chmin!(dp[v + c], dp[v] + 1) { q.push_back(v + c); } if chmin!(dp[v - c], dp[v] + 1) { q.push_back(v - c); } } if dp[n] == 1 << 60 { return writer.ln(-1); } writer.ln(dp[n]); }