結果

問題 No.1286 Stone Skipping
コンテスト
ユーザー Strorkis
提出日時 2020-11-13 22:26:38
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,501 bytes
コンパイル時間 12,062 ms
コンパイル使用メモリ 404,856 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-23 09:54:05
合計ジャッジ時間 13,119 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{BufRead, BufReader, BufWriter, Write};
use std::{str::FromStr, iter::FromIterator, fmt::Display};

pub struct ProconIo<'a> {
    pub reader: BufReader<std::io::StdinLock<'a>>,
    pub writer: BufWriter<std::io::StdoutLock<'a>>,
}

impl ProconIo<'_> {
    pub fn get_input(&mut self) -> String {
        let mut input = String::new();
        self.reader.read_line(&mut input).ok();
        input
    }

    pub fn read<T: FromStr>(&mut self) -> T {
        self.get_input().trim().parse().ok().unwrap()
    }

    pub fn read_col<T: FromStr, C: FromIterator<T>>(&mut self) -> C {
        self.get_input()
            .split_whitespace()
            .map(|x| x.parse().ok().unwrap())
            .collect()
    }

    pub fn read_chars<C: FromIterator<char>>(&mut self) -> C {
        self.get_input().trim().chars().collect()
    }

    pub fn writeln<T: Display>(&mut self, x: T) {
        writeln!(self.writer, "{}", x).ok();
    }

    pub fn writeln_col<C: IntoIterator>(&mut self, c: C)
    where
        C::Item: Display,
    {
        self.writeln(
            c.into_iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        )
    }
}

#[allow(unused_macros)]
macro_rules! read_tuple {
    ( $io:expr, $( $t:ty ),* ) => {{
        let input = $io.get_input();
        let mut iter = input.split_whitespace();
        ( $( iter.next().unwrap().parse::<$t>().unwrap() ),* )
    }};
}

/*
    1
    2 3
    3 4
    4 6 7
    5 7 8
    6 9 10
    7 10 11
    8 12 14 15
    9 13 15 16
*/


fn solve(io: &mut ProconIo) {
    let d: u64 = io.read();

    let f = |mut x: u64, i: u64| {
        let mut sum = 0;
        for _ in 0..=i {
            sum += x;
            x >>= 1;
        }
        sum
    };

    let n = 64 - (d + 1).leading_zeros() as u64;
    for i in (1..=n).rev() {
        let mut left = 1 << (i - 1);
        let mut right = d + 1;
        while left < right {
            let middle = (left + right) / 2;
            if f(middle, i) < d {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        if f(left, i) == d {
            io.writeln(left);
            return;
        }
    }
    io.writeln(d);
}

fn main() {
    let stdin = std::io::stdin();
    let stdout = std::io::stdout();
    let mut io = ProconIo {
        reader: BufReader::new(stdin.lock()),
        writer: BufWriter::new(stdout.lock()),
    };
    solve(&mut io);
}
0