Решение задачи №87 от UniLecs

count_choices.rs

extern crate num_bigint;
extern crate num_traits;

use num_bigint::BigUint;
use num_traits::{Zero, One};

type Length = u32;

#[deny(overflowing_literals)]
const BORDER: Length = 1_001;

#[derive(Debug, PartialEq)]
enum CountChoicesError {
    OutOfBound,
}

fn count_choices(n: Length) -> Result<BigUint, CountChoicesError> {
    if n >= BORDER {
        Err(CountChoicesError::OutOfBound)
    } else {
        match n {
            0 => Ok(Zero::zero()),
            1 => Ok(One::one()),
            _ => {
                let big_one: BigUint = One::one();
                let mut prev = Zero::zero();
                let mut curr = One::one();
                
                for _ in 1..n {
                    let sum = prev + &curr + &big_one;
                    prev = std::mem::replace(&mut curr, sum);
                }
                
                Ok(curr)
            }
        }
    }
}

#[test]
fn some_variants() {
    let (n, answer) = (1, 1_u32.into());
    assert_eq!(count_choices(n), Ok(answer));
    
    let (n, answer) = (2, 2_u32.into());
    assert_eq!(count_choices(n), Ok(answer));
    
    let (n, answer) = (3, 4_u32.into());
    assert_eq!(count_choices(n), Ok(answer));
    
    let (n, answer) = (10, 143_u32.into());
    assert_eq!(count_choices(n), Ok(answer));
}

#[test]
fn big_answer() {
    let (n, big_answer) = (100, "927372692193078999175".parse().unwrap());
    assert_eq!(count_choices(n), Ok(big_answer));
    
    let (n, big_answer) = (200, "734544867157818093234908902110449296423350".parse().unwrap());
    assert_eq!(count_choices(n), Ok(big_answer));
}

#[test]
fn check_error() {
    assert_eq!(count_choices(BORDER), Err(CountChoicesError::OutOfBound));
}

Playground: https://play.rust-lang.org/?gist=57f5a0b653a7936382a6957f9798e477&version=stable