Skip to content

11017: 【原1017】二哥养兔子

题目

题目描述

author: 吴杰 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1017

Description

二哥培养出了一种繁殖能力很强的兔子。

这种兔子在出生后的第一个月,能够生出a对兔子;第二个月,能够生出b对兔子;第三个月以及以后的每个月,都可以生出c对兔子。

二哥对此很感兴趣,若他有一对刚出生的兔子,按照最理想的模式繁殖,并假设兔子不死,二哥想知道最少需要几个月这些兔子可以遍布地球的每个角落。

为了回答这个问题,二哥想要知道这种兔子在第N个月时的对数。

Input Format

输入只有一行,四个数,分别为a,b,c,N ( \(0 \leq a \leq b \leq c \leq 100, N \leq 1000\) ),其含义为题目所述。

Output Format

输出只有一个数,为第N个月兔子的对数。

Sample Input

0 1 1 11

Sample Output

144

FineArtz's solution

/* 二哥养兔子 */
#include <iostream>
#include <string>
using namespace std;

class BigInt{
    friend BigInt operator +(const BigInt&, const BigInt&);
    friend BigInt operator *(const BigInt&, const int&);
    friend ostream& operator <<(ostream &, const BigInt&);
public:
//constructor
    BigInt() = default;
    BigInt(string);
    BigInt(const BigInt&);

    int getl() const { return len; }
private:
    int data[20000] = {0};
    int len = 1;
};

BigInt::BigInt(string s){
    len = s.size();
    for (int i = 1; i <= len; ++i)
        data[i] = s[len - i] - '0';
}
BigInt::BigInt(const BigInt &b){
    len = b.len;
    for (int i = 1; i <= len; ++i)
        data[i] = b.data[i];
}

BigInt operator +(const BigInt &a, const BigInt &b){
    BigInt ans;
    int l = (a.getl() > b.getl() ? a.getl() : b.getl());
    for (int i = 1; i <= l; ++i)
        ans.data[i] = a.data[i] + b.data[i];
    int i = 1;
    while (i <= l + 1){
        if (ans.data[i] >= 10){
            ans.data[i++] -= 10;
            ++ans.data[i];
        }
        else ++i;
    }
    ans.len = i;
    while (ans.len > 1 && ans.data[ans.len] == 0) --ans.len;
    return ans;
}
BigInt operator *(const BigInt &a, const int &b){
    BigInt ans;
    for (int i = 1; i <= a.len; ++i)
        ans.data[i] = b * a.data[i];
    ans.len = a.len;
    for (int i = 1; i <= ans.len; ++i){
        if (ans.data[i] / 10 != 0){
            ans.data[i + 1] += ans.data[i] / 10;
            ans.data[i] %= 10;
        }
    }
    while (ans.data[ans.len + 1] > 0){
        ++ans.len;
        if (ans.data[ans.len] >= 10){
            ans.data[ans.len + 1] += ans.data[ans.len] / 10;
            ans.data[ans.len] %= 10;
        }
    }
    return ans;
}
ostream& operator <<(ostream &os, const BigInt &a){
    for (int i = a.len; i >= 1; --i)
        os << a.data[i];
    return os;
}

BigInt one("1"), two, aft, ans("1");
int main(){
    int a, b, c, n;
    cin >> a >> b >> c >> n;
    while (n--){
        BigInt tmp(one * a + two * b + aft * c);
        ans = ans + tmp;
        aft = aft + two;
        two = one;
        one = tmp;
    }
    cout << ans << endl;
   // cout << ans.getl() << endl;
}

ligongzzz's solution

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>

using namespace std;
struct bigint { // only positive number;
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;
    //value
    bigint(long long num = 0) { *this = num; }
    bigint operator = (long long num) {
        s.clear();
        do {
            s.push_back(num%BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }
    bigint operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) {
            int end = str.length() - i * WIDTH;
            int start = max(0, end - WIDTH);
            sscanf_s(str.substr(start, end - start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return *this;
    }
    //input&output
    friend ostream& operator << (ostream &out, const bigint& x) {
        out << x.s.back();
        for (int i = x.s.size() - 2; i >= 0; i--) {
            char buf[20];
            sprintf_s(buf, "%08d", x.s[i]);
            for (int j = 0; j < strlen(buf); j++) out << buf[j];
        }
        return out;
    }
    friend istream& operator >>(istream &in, bigint& x) {
        string s;
        if (!(in >> s)) return in;
        x = s;
        return in;
    }
    //compare
    bool operator < (const bigint& b) const {
        if (s.size() != b.s.size()) return s.size() < b.s.size();
        for (int i = s.size() - 1; i >= 0; i++) if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;//equal
    }
    bool operator > (const bigint& b) const { return b < *this; }
    bool operator <= (const bigint& b) const { return !(b < *this); }
    bool operator >= (const bigint& b) const { return !(*this < b); }
    bool operator != (const bigint& b) const { return b < *this || *this < b; }
    bool operator == (const bigint& b) const { return !(b < *this) && !(*this < b); }
    //calculate
    bigint operator +(const bigint& b) const {
        bigint c;
        c.s.clear();
        for (int i = 0, g = 0;; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x%BASE);
            g = x / BASE;
        }
        return c;
    }
    bigint operator +=(const bigint& b) {
        *this = *this + b;
        return *this;
    }
    bigint operator -(const bigint& b) const {
        bigint c;
        c.s.clear();
        for (int i = 0, g = 0;; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x -= b.s[i];
            x += BASE;
            c.s.push_back(x%BASE);
            g = x / BASE - 1;
        }
        return c;
    }
    bigint operator * (const bigint& b) const {
        bigint c;
        c.s.clear();
        bigint g = 0;
        for (int i = 0;; i++) {
            if (g.s.size() == 0 && i >= s.size() + b.s.size() - 1) break;
            bigint x;
            x.s.clear();
            for (int j = 0; j < g.s.size(); j++) x.s.push_back(g.s[j]);
            if (i < s.size() + b.s.size() - 1) {
                for (int j = max(0, i - (int)s.size() + 1); j <= min(i, (int)b.s.size() - 1); j++) {
                    bigint t = (long long)b.s[j] * s[i - j];
                    x += t;
                }
            }
            c.s.push_back(x.s[0]);
            g.s.clear();
            if (x.s.size() > 1) for (int j = 1; j < x.s.size(); j++) g.s.push_back(x.s[j]);
        }
        return c;
    }
};

int main() {
    bigint a, b, c;
    int n;
    bigint num;
    bigint num1 = 1, num2 = 0, num3 = 0;

    //输入
    cin >> a >> b >> c >> n;

    //计算
    for (int i = 0; i < n; i++) {
        bigint temp = num1 * a + num2 * b + num3 * c;
        num3 += num2;
        num2 = num1;
        num1 = temp;
    }

    cout << num1 + num2 + num3 << endl;

    return 0;
}

yyong119's solution

#include <iostream>
int num[1005][2501];
int a,b,c,n,i,j;
int main(){
    using namespace std;
    cin>>a>>b>>c>>n;
    num[4][0]=1; num[4][1]=1;
    for (i=5; i<=n+4; i++){
        for (j=1; j<=num[i-1][0]; j++) num[i][j]+=num[i-1][j];
        for (j=1; j<=num[i-3][0]; j++) num[i][j]+=c*num[i-3][j];
        for (j=1; j<=num[i-2][0]; j++) num[i][j]+=b*(num[i-2][j]-num[i-3][j]);
        for (j=1; j<=num[i-1][0]; j++) num[i][j]+=a*(num[i-1][j]-num[i-2][j]);
        for (j=1; j<=2500; j++){
            num[i][j+1]+=num[i][j]/10;
            num[i][j]=num[i][j]%10;
        }
        for (j=2500; j>=1; j--) if (num[i][j]){num[i][0]=j; break;}
    }
    for (i=num[n+4][0]; i>=1; i--) cout<<num[n+4][i];
    return 0;
}