Cod sursa(job #3137462)

Utilizator TincaMateiTinca Matei TincaMatei Data 13 iunie 2023 03:43:50
Problema Fractal Scor 100
Compilator rs Status done
Runda Arhiva de probleme Marime 5.33 kb
#![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"));
}