fn solve(_reader: R, _writer: &mut W) { let mut _scanner = Scanner::new(_reader); #[allow(unused_macros)] macro_rules! scan { ($t:ty) => { _scanner.next::<$t>().unwrap() }; ($($t:ty),+) => { ($(scan!($t)),+) }; ($t:ty; $n:expr $(; $m:expr)*) => {{ let mut vec = Vec::with_capacity($n); for _ in 0..$n { vec.push(scan!($t $(; $m)*)); } vec }}; ($t_0:ty, $t_1:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1; $n) }; ($t_0:ty, $t_1:ty, $t_2:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1, $t_2 = 2; $n) }; ($($t:ty = $i:tt),+; $n:expr) => {{ let mut vecs = ($(Vec::<$t>::with_capacity($n)),+); for _ in 0..$n {$( vecs.$i.push(scan!($t)); )+} vecs }}; } #[allow(unused_macros)] macro_rules! scan_iter { ($t:ty; $n:expr) => { _scanner.take::<$t>($n).map(|x| x.unwrap()) }; } #[allow(unused_macros)] macro_rules! print { ($fmt:expr) => { write!(_writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { write!(_writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! println { () => { writeln!(_writer).unwrap() }; ($fmt:expr) => { writeln!(_writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { writeln!(_writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! eprint { ($fmt:expr) => { #[cfg(debug_assertions)] write!(::std::io::stderr(), $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { #[cfg(debug_assertions)] write!(::std::io::stderr(), $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! eprintln { () => { #[cfg(debug_assertions)] writeln!(::std::io::stderr()).unwrap() }; ($fmt:expr) => { #[cfg(debug_assertions)] writeln!(::std::io::stderr(), $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { #[cfg(debug_assertions)] writeln!(::std::io::stderr(), $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! dump { ($($x:expr),+) => { eprint!("[{}:{}] ", file!(), line!()); eprintln!(concat!($(stringify!($x), "={:?}; "),+), $($x),+); }; } use cmp::{OrdAssign, Reverse}; use data_structures::PairingHeap; let n = scan!(usize); let a = scan!(i32; n); let b = scan!(i32; n); let mut pq = PairingHeap::new(); let mut ans = i32::max_value(); for i in 0..n { let mut cnt_max = 0; pq.extend(a.iter().map(|&a_i| Reverse((a_i, 0)))); for j in 0..n { let k = if i + j >= n { i + j - n } else { i + j }; let Reverse((x, cnt)) = pq.pop().unwrap(); cnt_max.max_assign(cnt + 1); pq.push(Reverse((x + b[k] / 2, cnt + 1))); } ans.min_assign(cnt_max); pq.clear(); } println!("{}", ans); } const STACK_SIZE_MEBIBYTES: Option = None; fn main() { fn run_solver() { let stdin = stdin(); let stdout = stdout(); #[cfg(debug_assertions)] let mut writer = stdout.lock(); #[cfg(not(debug_assertions))] let mut writer = ::std::io::BufWriter::new(stdout.lock()); solve(stdin.lock(), &mut writer); writer.flush().unwrap(); } if let Some(size) = STACK_SIZE_MEBIBYTES { let builder = ::std::thread::Builder::new().stack_size(size * 1024 * 1024); builder.spawn(run_solver).unwrap().join().unwrap(); } else { run_solver(); } } use io::Scanner; use std::io::{stdin, stdout, BufRead, Write}; pub mod cmp { pub use self::ord_assign::*; pub use self::reverse::*; mod ord_assign { use std::cmp::{max, min}; pub trait OrdAssign: Ord where Self: Copy, { fn min_assign(&mut self, other: Self) { *self = min(*self, other); } fn max_assign(&mut self, other: Self) { *self = max(*self, other); } } impl OrdAssign for T {} } mod reverse { use std::cmp::Ordering; #[derive(Clone, Copy, PartialEq, Eq, Default, Debug, Hash)] pub struct Reverse(pub T); impl PartialOrd for Reverse { fn partial_cmp(&self, other: &Self) -> Option { other.0.partial_cmp(&self.0) } } impl Ord for Reverse { fn cmp(&self, other: &Self) -> Ordering { other.0.cmp(&self.0) } } } } pub mod data_structures { pub use self::pairing_heap::PairingHeap; mod pairing_heap { use std::collections::LinkedList; use std::mem::{replace, swap}; #[derive(Clone, Debug)] pub struct PairingHeap { root: Option>, len: usize, } #[derive(Clone, Debug)] struct Node { key: T, children: LinkedList>>, } impl Node { fn new(x: T) -> Self { Node { key: x, children: LinkedList::new() } } } impl PairingHeap { pub fn new() -> Self { PairingHeap { root: None, len: 0 } } pub fn peek(&self) -> Option<&T> { self.root.as_ref().map(|node| &node.key) } pub fn pop(&mut self) -> Option { replace(&mut self.root, None).map(|node| { self.root = Self::merge_list(node.children); self.len -= 1; node.key }) } pub fn push(&mut self, x: T) { self.root = Self::merge(replace(&mut self.root, None), Some(Node::new(x))); self.len += 1; } pub fn len(&self) -> usize { self.len } pub fn is_empty(&self) -> bool { debug_assert_eq!(self.root.is_none(), self.len == 0); self.len == 0 } pub fn clear(&mut self) { self.root = None; self.len = 0; } pub fn append(&mut self, other: &mut Self) { self.root = Self::merge(replace(&mut self.root, None), replace(&mut other.root, None)); self.len += other.len; other.len = 0; debug_assert!(other.is_empty()); } fn merge(l: Option>, r: Option>) -> Option> { match (l, r) { (l, None) => l, (None, r) => r, (Some(mut l), Some(mut r)) => { if l.key < r.key { swap(&mut l, &mut r); } debug_assert!(l.key >= r.key); l.children.push_back(Some(r)); Some(l) } } } fn merge_list(mut xs: LinkedList>>) -> Option> { let mut acc = None; loop { match (xs.pop_back(), xs.pop_back()) { (Some(l), Some(r)) => acc = Self::merge(Self::merge(l, r), acc), (Some(x), None) => acc = Self::merge(x, acc), (None, None) => break, _ => unreachable!(), } } acc } } impl Default for PairingHeap { fn default() -> Self { Self::new() } } impl Extend for PairingHeap { fn extend>(&mut self, iter: I) { for x in iter { self.push(x); } } } impl IntoIterator for PairingHeap { type Item = T; type IntoIter = IntoIter; fn into_iter(self) -> IntoIter { IntoIter(self) } } pub struct IntoIter(PairingHeap); impl Iterator for IntoIter { type Item = T; fn next(&mut self) -> Option { self.0.pop() } } } } pub mod io { pub use self::scanner::*; mod scanner { use std::io::BufRead; use std::marker::PhantomData; use std::str::{from_utf8, FromStr}; pub struct Scanner { reader: R, buffer: Vec, position: usize, } impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buffer: vec![], position: 0 } } pub fn next(&mut self) -> Option { Parse::parse(self.next_bytes().unwrap_or(&[])) } pub fn take(&mut self, n: usize) -> Take { Take { scanner: self, n: n, _marker: PhantomData } } pub fn next_bytes(&mut self) -> Option<&[u8]> { if self.buffer.is_empty() { self.read_line(); } loop { match self.buffer.get(self.position) { Some(&b' ') => self.position += 1, Some(&b'\n') => self.read_line(), Some(_) => break, None => return None, } } let start = self.position; loop { match self.buffer.get(self.position) { Some(&b' ') | Some(&b'\n') | None => break, Some(_) => self.position += 1, } } Some(&self.buffer[start..self.position]) } fn read_line(&mut self) { self.position = 0; self.buffer.clear(); self.reader.read_until(b'\n', &mut self.buffer).unwrap(); } } pub struct Take<'a, R: 'a, T> { scanner: &'a mut Scanner, n: usize, _marker: PhantomData T>, } impl<'a, R: BufRead, T: Parse> Iterator for Take<'a, R, T> { type Item = Option; fn next(&mut self) -> Option { if self.n > 0 { self.n -= 1; Some(self.scanner.next()) } else { None } } fn size_hint(&self) -> (usize, Option) { (self.n, Some(self.n)) } } impl<'a, R: BufRead, T: Parse> ExactSizeIterator for Take<'a, R, T> {} pub trait Parse: Sized { fn parse(bytes: &[u8]) -> Option; } impl Parse for u8 { fn parse(bytes: &[u8]) -> Option { if bytes.len() == 1 { Some(*unsafe { bytes.get_unchecked(0) }) } else { None } } } macro_rules! parse_impl { ($($t:ident)+) => {$( impl Parse for $t { fn parse(bytes: &[u8]) -> Option { from_utf8(bytes).ok().and_then(|s| $t::from_str(s).ok()) } } )+}; } parse_impl! { i32 i64 isize u32 u64 usize String } } }