pub use __cargo_equip::prelude::*; use proconio::input; const N: usize = 45; const X: usize = 50; const TARGET: u64 = 5 * 100_000_000_000_000_000; fn main() { input! { n: usize, cards: [(u64, u64); n], }; assert_eq!(n, N); let mut ans = Vec::new(); let cards = cards .into_iter() .map(|(a, b)| Card::new(a, b)) .collect::>(); let mut state = State::new(cards, 0); let x = 10; for _ in 0..(X - x) { let (i, j) = choose(&state); state.advance((i, j)); ans.push((i, j)); } // ??? for _ in 0..x { let j = (1..N) .min_by_key(|&j| { let mut state = state.clone(); state.advance((0, j)); state.cards[0].abs_diff() }) .unwrap(); state.advance((0, j)); ans.push((0, j)); } println!("{}", ans.len()); for (i, j) in ans { println!("{} {}", i + 1, j + 1); } } #[derive(Debug, Clone, Copy)] struct Card { a: u64, b: u64, } impl Card { fn new(a: u64, b: u64) -> Self { Self { a, b } } fn abs_diff(&self) -> u64 { self.a.abs_diff(TARGET).max(self.b.abs_diff(TARGET)) } } #[derive(Debug, Clone)] struct State { cards: Vec, t: usize, } impl State { fn new(cards: Vec, t: usize) -> Self { Self { cards, t } } fn advance(&mut self, (i, j): (usize, usize)) { let new_a = (self.cards[i].a + self.cards[j].a) / 2; let new_b = (self.cards[i].b + self.cards[j].b) / 2; let new_card = Card::new(new_a, new_b); self.cards[i] = new_card; self.cards[j] = new_card; self.t += 1; } fn score(&self) -> u64 { self.cards.iter().map(|c| c.abs_diff()).min().unwrap() } } fn choose(state: &State) -> (usize, usize) { let mut scores = vec![0.0; N * N]; let mut counts = vec![0; N * N]; for _ in 0..(100000 / (state.t / 2 + 1)) { let mut next_state = state.clone(); let (i, j) = rand_index(); next_state.advance((i, j)); scores[i * N + j] += f64::log10(playout(next_state) as f64); // log縺ィ繧峨↑縺・→繧ェ繝シ繝舌・繝輔Ο繝シ縺吶k counts[i * N + j] += 1; } let mut ave = Vec::new(); for i in 0..N { for j in (i + 1)..N { if counts[i * N + j] == 0 { continue; } ave.push((scores[i * N + j] / counts[i * N + j] as f64, (i, j))); } } let (_ave, (i, j)) = ave .into_iter() .min_by(|(s1, _), (s2, _)| s1.total_cmp(&s2)) .unwrap(); (i, j) } fn playout(state: State) -> u64 { assert!(state.t < X); if state.t + 1 == X { return state.score(); } let mut state = state; let (i, j) = rand_index(); state.advance((i, j)); playout(state) } fn rand_index() -> (usize, usize) { let i = xorshift() % N; let j = loop { let j = xorshift() % N; if i != j { break j; } }; (i.min(j), i.max(j)) } // https://en.wikipedia.org/wiki/Xorshift#xorshift* fn xorshift() -> usize { static mut X: usize = 1; unsafe { X ^= X >> 12; X ^= X << 25; X ^= X >> 27; X } } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `proconio 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio` /// /// # License and Copyright Notices /// /// - `proconio 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)` /// /// ```text /// The MIT License /// Copyright 2019 (C) statiolake /// /// Permission is hereby granted, free of charge, to any person obtaining a copy of /// this software and associated documentation files (the "Software"), to deal in /// the Software without restriction, including without limitation the rights to /// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of /// the Software, and to permit persons to whom the Software is furnished to do so, /// subject to the following conditions: /// /// The above copyright notice and this permission notice shall be included in all /// copies or substantial portions of the Software. /// /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR /// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS /// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR /// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER /// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN /// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. /// /// Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019. The /// original macro is licensed under BSD 3-clause license. /// /// Redistribution and use in source and binary forms, with or without /// modification, are permitted provided that the following conditions are met: /// /// 1. Redistributions of source code must retain the above copyright notice, this /// list of conditions and the following disclaimer. /// /// 2. Redistributions in binary form must reproduce the above copyright notice, /// this list of conditions and the following disclaimer in the documentation /// and/or other materials provided with the distribution. /// /// 3. Neither the name of the copyright holder nor the names of its contributors /// may be used to endorse or promote products derived from this software /// without specific prior written permission. /// /// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND /// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED /// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE /// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE /// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL /// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR /// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER /// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, /// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE /// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. /// ``` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]pub use crate::__cargo_equip::macros::proconio::*;pub mod marker{use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for Chars{type Output=Vec;fn read>(source:&mut S)->Vec{source.next_token_unwrap().chars().collect()}}pub enum Bytes{}impl Readable for Bytes{type Output=Vec;fn read>(source:&mut S)->Vec{source.next_token_unwrap().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use super::Source;use crate::__cargo_equip::crates::proconio::source::tokens::Tokens;use std::io::BufRead;pub struct LineSource{tokens:Tokens,reader:R,}implLineSource{pub fn new(reader:R)->LineSource{LineSource{tokens:"".to_owned().into(),reader,}}fn prepare(&mut self){while self.tokens.is_empty(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.tokens=line.into();}}}implSourcefor LineSource{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next_token()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.is_empty()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource>{fn from(s:&'a str)->LineSource>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use super::Source;use crate::__cargo_equip::crates::proconio::source::tokens::Tokens;use std::io::BufRead;use std::marker::PhantomData;pub struct OnceSource{tokens:Tokens,_read:PhantomData,}implOnceSource{pub fn new(mut source:R)->OnceSource{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");OnceSource{tokens:context.into(),_read:PhantomData,}}}implSourcefor OnceSource{fn next_token(&mut self)->Option<&str>{self.tokens.next_token()}fn is_empty(&mut self)->bool{self.tokens.is_empty()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource>{fn from(s:&'a str)->OnceSource>{OnceSource::new(BufReader::new(s.as_bytes()))}}}mod tokens{use std::{iter::Peekable,ptr::NonNull,str::SplitWhitespace};pub(super)struct Tokens{tokens:Peekable>,_current_context:CurrentContext,}impl Tokens{pub(super)fn next_token(&mut self)->Option<&str>{self.tokens.next()}pub(super)fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}impl Fromfor Tokens{fn from(current_context:String)->Self{let current_context=CurrentContext::from(current_context);unsafe{let tokens=current_context.0.as_ref().split_whitespace().peekable();Self{tokens,_current_context:current_context,}}}}unsafe impl Send for Tokens{}unsafe impl Sync for Tokens{}struct CurrentContext(NonNull);impl Fromfor CurrentContext{fn from(s:String)->Self{let s=s.into_boxed_str();Self(NonNull::new(Box::leak(s)).unwrap())}}impl Drop for CurrentContext{fn drop(&mut self){unsafe{Box::from_raw(self.0.as_mut())};}}}pub mod auto{#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source{fn next_token(&mut self)->Option<&str>;#[allow(clippy::wrong_self_convention)]fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl>Sourcefor&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read>(source:&mut S)->Self::Output;}implReadable for T where T::Err:Debug,{type Output=T;fn read>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::(),err=e,),}}}}use crate::__cargo_equip::crates::proconio::source::{auto::AutoSource,line::LineSource};use std::io::{BufReader,Stdin};use std::sync::OnceLock;use std::{io::{self,BufRead},sync::Mutex,};pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;pub enum StdinSource{Normal(AutoSource),Interactive(LineSource),Unknown(LineSource),}implsource::Sourcefor StdinSource{fn next_token(&mut self)->Option<&str>{match self{StdinSource::Normal(source)=>source.next_token(),StdinSource::Interactive(source)=>source.next_token(),StdinSource::Unknown(source)=>source.next_token(),}}fn is_empty(&mut self)->bool{match self{StdinSource::Normal(source)=>source.is_empty(),StdinSource::Interactive(source)=>source.is_empty(),StdinSource::Unknown(source)=>source.is_empty(),}}}pub static STDIN_SOURCE:OnceLock>>> =OnceLock::new();#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.get_or_init(||{std::sync::Mutex::new($crate::__cargo_equip::crates::proconio::StdinSource::Normal($crate::__cargo_equip::crates::proconio::source::auto::AutoSource::new(std::io::BufReader::new(std::io::stdin())),))}).lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input_interactive{($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.get_or_init(||{std::sync::Mutex::new($crate::__cargo_equip::crates::proconio::StdinSource::Interactive($crate::__cargo_equip::crates::proconio::source::line::LineSource::new(std::io::BufReader::new(std::io::stdin())),))}).lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","."));$crate::__cargo_equip::crates::proconio::input!{from&mut*locked_stdin,$($rest)*}drop(locked_stdin);};}macro_rules!input_interactive{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input_interactive!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input. ","This is a bug in `proconio`. ","Please report this issue from ","."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use source::Source;let mut lock=STDIN_SOURCE.get_or_init(||{Mutex::new(StdinSource::Unknown(LineSource::new(BufReader::new(io::stdin(),))))}).lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","."));lock.is_empty()}} } pub(crate) mod macros { pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_input_interactive as input_interactive,__cargo_equip_macro_def_proconio_read_value as read_value};} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod proconio {} } }