#![allow(dead_code)]
use std::io::{Read, BufRead, Stdin, BufReader};
use std::fs::File;
use std::str::FromStr;
use std::fmt::Debug;
pub struct InParser<T: Read> {
reader: BufReader<T>,
buffer: Vec<u8>,
cursor: usize
}
impl InParser<Stdin> {
pub fn from_stdin() -> InParser<Stdin> {
InParser::new(std::io::stdin())
}
}
impl InParser<File> {
pub fn from_filename(name: &str) -> InParser<File> {
InParser::new(File::open(name)
.expect("Failed to open file"))
}
}
impl<T: Read> InParser<T> {
pub fn new(reader: T) -> InParser<T> {
let mut reader = BufReader::new(reader);
let buffer = reader.fill_buf()
.expect("Failed to fill buffer")
.to_vec();
InParser {
reader,
buffer,
cursor: 0,
}
}
pub fn get_current_byte(&mut self) -> Option<u8> {
if self.cursor < self.buffer.len() {
return Some(self.buffer[self.cursor]);
}
return None
}
pub fn advance_cursor(&mut self) {
self.cursor += 1;
if self.cursor >= self.buffer.len() {
self.reader.consume(self.buffer.len());
self.buffer = self.reader.fill_buf()
.expect("Failed to fill buffer")
.to_vec();
self.cursor = 0;
}
}
fn skip_spaces(&mut self) {
while self.get_current_byte() == Some(b' ') ||
self.get_current_byte() == Some(b'\n') {
self.advance_cursor();
}
}
fn get_token(&mut self) -> Option<String> {
let mut token_buf: Vec<u8> = Vec::new();
self.skip_spaces();
while self.get_current_byte() != None &&
self.get_current_byte() != Some(b' ') &&
self.get_current_byte() != Some(b'\n') {
let byte = self.get_current_byte().unwrap();
token_buf.push(byte);
self.advance_cursor();
}
let strval = std::str::from_utf8(&token_buf)
.expect("Failed to convert into valid utf8")
.trim();
if strval.is_empty() {
return None;
} else {
Some(strval.to_string())
}
}
pub fn read<F: FromStr>(&mut self) -> F
where <F as FromStr>::Err: Debug{
let token = self.get_token()
.expect("Tried to read from empty token");
token.parse::<F>()
.unwrap()
}
}
use std::io::{Write, BufWriter, Stdout};
pub struct OutParser<T: Write> {
writer: BufWriter<T>,
}
impl<T: Write> OutParser<T> {
pub fn new(writer: T) -> OutParser<T> {
OutParser {
writer: BufWriter::new(writer)
}
}
pub fn write<F: ToString>(&mut self, val: F) -> &mut Self {
self.writer.write(&val.to_string().as_bytes())
.expect("Failed to write");
self
}
}
impl OutParser<Stdout> {
pub fn from_stdout() -> OutParser<Stdout> {
OutParser::new(std::io::stdout())
}
}
impl OutParser<File> {
pub fn from_filename(name: &str) -> OutParser<File> {
OutParser::new(File::create(name)
.expect("Failed to open file"))
}
}
struct Coord {
x: i32,
y: i32,
}
impl Coord {
fn new(x: i32, y: i32) -> Coord {
Coord { x, y }
}
fn transpose(&self) -> Coord {
Coord { x: self.y, y: self.x }
}
fn translate(&self, (dx, dy): (i32, i32)) -> Coord {
Coord { x: self.x + dx, y: self.y + dy }
}
fn rotate(&self, order: usize) -> Coord {
Coord { x: self.y, y: (1 << order) as i32 + 1 - self.x }
}
}
fn calculate_length(k: usize, coord: Coord) -> usize {
if k == 0 {
return 0;
}
match (coord.x > 1 << (k - 1), coord.y > 1 << (k - 1)) {
(false, false) => {
calculate_length(k - 1, coord.transpose())
}
(false, true) => {
(1 << (2 * k - 2)) + calculate_length(k - 1, coord.translate((0, -(1 << (k - 1)))))
}
(true, false) => {
(1 << (2 * k - 2)) * 3 + calculate_length(k - 1, coord.translate((-(1 << (k - 1)), 0))
.transpose()
.rotate(k - 1)
.rotate(k - 1))
}
(true, true) => {
(1 << (2 * k - 2)) * 2 + calculate_length(k - 1, coord.translate((-(1 << (k - 1)), -(1 << (k - 1)))))
}
}
}
fn solve_test<I: Read, O: Write>(fin: &mut InParser<I>, fout: &mut OutParser<O>) {
let (k, x, y): (usize, i32, i32) = (fin.read(), fin.read(), fin.read());
fout.write(calculate_length(k, Coord::new(x, y)));
}
fn try_sample(input: &[u8], ok: &str) {
use std::io::Cursor;
let mut output = Vec::<u8>::new();
solve_test(&mut InParser::new(BufReader::new(Cursor::new(input))),
&mut OutParser::new(BufWriter::new(&mut output)));
assert_eq!(std::str::from_utf8(&output).unwrap(), ok);
}
fn sample_1() {
try_sample(b"1 1 1", "0");
}
fn sample_2() {
try_sample(b"3 2 3", "13")
}
fn sample_3() {
try_sample(b"2 4 1", "15");
}
fn main() {
//sample_1();
//sample_2();
//sample_3();
solve_test(&mut InParser::from_filename("fractal.in"),
&mut OutParser::from_filename("fractal.out"));
}