#include #include #include #include #include #include #include #include #include #include #include #include namespace utility { templatestruct addable; templatestruct subtractable; templatestruct multipliable; templatestruct dividable; templateconstexpr decltype(auto) operator+(T const& lhs, U const& rhs) { auto x = lhs; x += rhs; return x; } templateconstexpr decltype(auto) operator-(T const& lhs, U const& rhs) { auto x = lhs; x -= rhs; return x; } templateconstexpr decltype(auto) operator*(T const& lhs, U const& rhs) { auto x = lhs; x *= rhs; return x; } templateconstexpr decltype(auto) operator/(T const& lhs, U const& rhs) { auto x = lhs; x /= rhs; return x; } templatestruct equality_comparable { constexpr decltype(auto) operator!=(equality_comparableconst& rhs)const { return !(static_cast(*this) == static_cast(rhs)); } }; templatestruct less_than_comparable { constexpr decltype(auto)operator<(equality_comparableconst& rhs)const { return static_cast(*this) < static_cast(rhs); } constexpr decltype(auto)operator>(T const& rhs)const { return rhs < *this; } constexpr decltype(auto)operator<=(T const& rhs)const { return !(rhs < *this); } constexpr decltype(auto)operator>=(T const& rhs)const { return !(*this < rhs); } }; templatestruct addable { constexpr decltype(auto) operator+=(addableconst& rhs) { return static_cast(*this) += static_cast(rhs); } friend constexpr decltype(auto) operator+(addableconst& lhs, addableconst& rhs); }; templatestruct subtractable { constexpr decltype(auto) operator-=(subtractableconst& rhs) { return static_cast(*this) -= static_cast(rhs); } friend constexpr decltype(auto) operator-(subtractableconst& lhs, subtractableconst& rhs); }; templatestruct multipliable { constexpr decltype(auto) operator*=(multipliableconst& rhs) { return static_cast(*this) *= static_cast(rhs); } friend constexpr decltype(auto) operator*(multipliableconst& lhs, multipliableconst& rhs); }; templatestruct dividable { constexpr decltype(auto) operator/=(dividableconst& rhs) { return static_cast(*this) /= static_cast(rhs); } friend constexpr decltype(auto) operator/(dividableconst& lhs, dividableconst& rhs); }; struct nullopt_t { }; constexpr nullopt_t nullopt{}; templateclass optional:private equality_comparable> { union { T val; nullopt_t null; }; bool flag; public: constexpr optional(nullopt_t n = nullopt) : null(), flag(false) { } constexpr T& operator*() { if (flag) { return val; } throw std::invalid_argument("this optional value has not any value"); } constexpr T const& operator*()const { if (flag) { return val; } throw std::invalid_argument("this optional value has not any value"); } constexpr void reset() { null = nullopt; flag = false; } constexpr operator bool()const { return flag; } templatevoid emplace(Us&&... args) { val = T(std::forward(args)...); flag = true; } constexpr auto& operator=(T const& v) { val = v; flag = true; return *this; } constexpr auto& operator=(T&& v) { val = v; flag = true; return *this; } constexpr auto& operator=(nullopt_t) { null = nullopt; flag = false; return *this; } constexpr optional(T const& v) :optional() { *this = v; } constexpr optional(T&& v) : optional() { *this = std::move(v); } constexpr bool operator==(optional const& rhs)const { return flag&&rhs.flag ? val == rhs.val : flag == rhs.flag; } optional(optional const&) = default; optional(optional&&) = default; optional& operator=(optional const&) = default; optional& operator=(optional&&) = default; ~optional() = default; }; } namespace math { templateconstexpr T pow(T val, std::uint64_t p) { return p == 0 ? T(1) : p == 1 ? val : p == 2 ? val*val : p % 2 == 0 ? pow(pow(val, p / 2), 2) : pow(pow(val, p / 2), 2)*val; } templateconstexpr int ilog(T val, U base) { T v(1); for (int i{};;++i) { if (val <= v) { return i; } v *= base; } } templateclass mod_number: private utility::equality_comparable>, private utility::addable>, private utility::subtractable>, private utility::multipliable>, private utility::dividable> { std::uint64_t value; public: mod_number(std::uint64_t v = 0) :value(v%Mod) { } mod_number(int v) :value(v%Mod) { } mod_number(std::int64_t v) :value(v%Mod) { } mod_number(std::uint32_t v) :value(v%Mod) { } bool operator==(mod_number const& rhs) { return value == rhs.value; } auto& operator+=(mod_number const& rhs) { value += rhs.value; value %= Mod; return *this; } auto& operator-=(mod_number const& rhs) { value += Mod - rhs.value; value %= Mod; return *this; } auto& operator*=(mod_number const& rhs) { value *= rhs.value; value %= Mod; return *this; } auto& operator/=(mod_number const& rhs) { return operator*=(pow(rhs, Mod - 2)); } }; constexpr int bitcount(unsigned int x) { x = (x & 0x55555555) + ((x & 0xAAAAAAAA) >> 1); x = (x & 0x33333333) + ((x & 0xCCCCCCCC) >> 2); x = (x & 0x0F0F0F0F) + ((x & 0xF0F0F0F0) >> 4); x = (x & 0x00FF00FF) + ((x & 0xFF00FF00) >> 8); x = (x & 0x0000FFFF) + ((x & 0xFFFF0000) >> 16); return static_cast(x); } constexpr int bitcount(unsigned long long x) { x = (x & 0b0101010101010101010101010101010101010101010101010101010101010101) + ((x & 0b1010101010101010101010101010101010101010101010101010101010101010) >> 1); x = (x & 0b0011001100110011001100110011001100110011001100110011001100110011) + ((x & 0b1100110011001100110011001100110011001100110011001100110011001100) >> 2); x = (x & 0b0000111100001111000011110000111100001111000011110000111100001111) + ((x & 0b1111000011110000111100001111000011110000111100001111000011110000) >> 4); x = (x & 0b0000000011111111000000001111111100000000111111110000000011111111) + ((x & 0b1111111100000000111111110000000011111111000000001111111100000000) >> 8); x = (x & 0b0000000000000000111111111111111100000000000000001111111111111111) + ((x & 0b1111111111111111000000000000000011111111111111110000000000000000) >> 16); x = (x & 0b0000000000000000000000000000000011111111111111111111111111111111) + ((x & 0b1111111111111111111111111111111100000000000000000000000000000000) >> 32); return static_cast(x); } constexpr int bitcount(int x) { return bitcount(static_cast(x)); } constexpr int bitcount(long long x) { return bitcount(static_cast(x)); } constexpr auto infinity = utility::nullopt; templateclass infable : private utility::addable, private utility::subtractable, private utility::multipliable, private utility::dividable, private utility::equality_comparable, private utility::less_than_comparable { utility::optional val; public: constexpr infable(T v = T()) :val(v) { } constexpr infable(utility::nullopt_t) : val() { } constexpr T const& get()const { return *val; } constexpr bool operator<(infableconst& rhs)const { if (val&&rhs.val) { return *val < rhs.get(); } else if (val && !rhs.val) { return true; } else { return false; } } constexpr bool operator==(infableconst& rhs)const { return val == rhs.val; } constexpr decltype(auto) operator+=(infableconst& rhs) { if (val) { if (rhs.val) { *val += rhs.get(); } else { val = infinity; } } return *this; } constexpr decltype(auto) operator-=(infableconst& rhs) { if (val) { if (rhs.val) { *val -= rhs.get(); } else { val = infinity; } } return *this; } constexpr decltype(auto) operator*=(infableconst& rhs) { if (val) { if (rhs.val) { *val *= rhs.get(); } else { val = infinity; } } return *this; } constexpr decltype(auto) operator/=(infableconst& rhs) { if (val) { if (rhs.val) { *val /= rhs.get(); } else { val = infinity; } } return *this; } }; } namespace container { namespace detail { templatestruct tree_array { std::array ar; constexpr T& operator()(std::size_t index, std::size_t depth) { return ar[(1ull << depth) + index - 1]; } constexpr T const& operator()(std::size_t index, std::size_t depth)const { return ar[(1ull << depth) + index - 1]; } }; } templateclass addtree { std::array data; T get(std::size_t left, std::size_t right, std::size_t i, std::size_t l, std::size_t r) { if (r <= left || right <= l) return T(); if (left <= l&&r <= right) { return data[i]; } else { return get(left, right, 2 * i + 1, l, (l + r) / 2) + get(left, right, 2 * i + 2, (l + r) / 2, r); } } public: addtree() :data{} { } void change(T const& val, std::size_t index) { T from = data[index + Size - 1]; for (std::size_t i = 1, c = math::ilog(Size, 2);i <= Size;(i <<= 1), --c) { data[i + (index >> c) - 1] -= from; data[i + (index >> c) - 1] += val; } } auto begin()const { return std::next(data.begin(), Size - 1); } auto end()const { return data.end(); } T get(std::size_t left, std::size_t right) { return left > right ? T() : get(left, right + 1, 0, 0, Size); } }; templateclass minmaxtree { detail::tree_array, Depth> data; T min(std::size_t left, std::size_t right, std::size_t L, std::size_t R, std::size_t depth)const { if (right <= L || R <= left) { return std::numeric_limits::max(); } else if (left <= L&&R <= right) { return data(L >> (Depth - depth), depth).first; } else { return std::min( min(left, right, L, (L + R) / 2, depth + 1), min(left, right, (L + R) / 2, R, depth + 1)); } } T max(std::size_t left, std::size_t right, std::size_t L, std::size_t R, std::size_t depth)const { if (right <= L || R <= left) { return std::numeric_limits::min(); } else if (left <= L&&R <= right) { return data(L >> (Depth - depth), depth).second; } else { return std::max( max(left, right, L, (L + R) / 2, depth + 1), max(left, right, (L + R) / 2, R, depth + 1)); } } public: void change(T const& val, std::size_t index) { data(index, Depth).first = val; data(index, Depth).second = val; for (int i = 1;i <= Depth;++i) { data(index >> i, Depth - i).first = std::min( data((index >> i) << 1, Depth - i + 1).first, data(((index >> i) << 1) + 1, Depth - i + 1).first); data(index >> i, Depth - i).second = std::max( data((index >> i) << 1, Depth - i + 1).second, data(((index >> i) << 1) + 1, Depth - i + 1).second); } } T min(std::size_t left, std::size_t right)const { return right < left ? std::numeric_limits::max() : min(left, right + 1, 0, 1 << Depth, 0); } T max(std::size_t left, std::size_t right)const { return right < left ? std::numeric_limits::min() : max(left, right + 1, 0, 1 << Depth, 0); } minmaxtree() :data{} { } }; templateusing dijkstra_queue = std::priority_queue, std::greater<>>; } void Main(); int main() { std::ios::sync_with_stdio(false); Main(); } //ここから頑張る void Main() { int N; std::cin >> N; container::dijkstra_queue, int>> queue; std::vector> result(N, math::infinity); queue.emplace(1, 1); while (result.back() == math::infinity && queue.size()) { auto top = queue.top(); queue.pop(); if (top.second<1 || top.second>N) continue; if (top.first < result[top.second - 1]) { result[top.second - 1] = top.first; queue.emplace(top.first + 1, top.second + math::bitcount(top.second)); queue.emplace(top.first + 1, top.second - math::bitcount(top.second)); } } std::cout << (result.back() == math::infinity ? -1 : result.back().get()) << std::endl; }