UVa - 495 - Fibonacci Freeze

Problem Link: 495 - Fibonacci Freeze
#include <bits/stdc++.h>
#define S 5003
using namespace std;

vector <int> Fib[S], addition;

void Fib_Number(){
    Fib[0].push_back(0);
    Fib[1].push_back(1);
    for(int i = 2; i < S; i++){
        int sz1 = Fib[i-2].size()-1;
        int sz2 = Fib[i-1].size()-1;
        int tmp, ad, c = 0;
        while(sz1 >= 0 && sz2 >= 0){
            ad = c+Fib[i-2][sz1]+Fib[i-1][sz2];
            if(ad > 9){
                c = ad/10;
                ad %= 10;
            }
            else c = 0;
            addition.push_back(ad);
            sz1--, sz2--;
        }
        if(sz1 >= 0){
            while(sz1 >= 0){
                ad = c+Fib[i-2][sz1];
                if(ad > 9){
                    c = ad/10;
                    ad %= 10;
                }
                else c = 0;
                addition.push_back(ad);
                sz1--;
            }
        }
        if(sz2 >= 0){
            while(sz2 >= 0){
                ad = c+Fib[i-1][sz2];
                if(ad > 9){
                    c = ad/10;
                    ad %= 10;
                }
                else c = 0;
                addition.push_back(ad);
                sz2--;
            }
        }
        if(c)addition.push_back(c);
        int sz = addition.size();
        for(int z = sz-1; z >= 0; z--)Fib[i].push_back(addition[z]);
        addition.clear();
    }
}

int main(){
    Fib_Number();
    int n;
    while(cin >> n){
        int sz = Fib[n].size();
        cout << "The Fibonacci number for " << n << " is ";
        for(int i = 0; i < sz; i++)cout << Fib[n][i];
        puts("");
    }
    return 0;
}

UVa - 11060 - Beverages

Problem Link: 11060 - Beverages

#include <bits/stdc++.h>


#define S 103


using namespace std;


 


vector <int> Order[S];


queue <int> ans;


map <string, int> Bev;


map <int, string> Ans;


int cn, indegree[S];


 


int main(){


    string Beverages, x, y;


    int n, m, cs = 0;


    while(cin >> n){


        for(int i = 1; i <= n; i++){


            cin >> Beverages;


            Bev[Beverages] = i;


            Ans[i] = Beverages;


        }


        memset(indegree, 0, sizeof(indegree));


        cin >> m;


        for(int i = 0; i < m; i++){


            cin >> x >> y;


            Order[Bev[x]].push_back(Bev[y]);


            indegree[Bev[y]]++;


        }


        bool f = true;


        while(f){


            int cn = 0;


            for(int i = 1; i <= n; i++){


                if(!indegree[i]){


                    indegree[i] = -1;


                    ans.push(i);


                    int sz = Order[i].size();


                    for(int z = 0; z < sz; z++)indegree[Order[i][z]]--;


                    break;


                }


                cn++;


            }


            if(cn == n)break;


        }


        cout << "Case #" << ++cs << ": Dilbert should drink beverages in this order:";


        while(!ans.empty()){


            cout << " " << Ans[ans.front()];


            ans.pop();


        }


        puts(".");


        puts("");


        Ans.clear(), Bev.clear();


        for(int i = 0; i <= n; i++)Order[i].clear();


    }


    return 0;


}

UVa - 10004 - Bicoloring

#include <bits/stdc++.h>
using namespace std;

int dirX[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dirY[] = {0, 1, 0, -1, 1, -1, -1, 1};

int row, col, cnt, vis[103][103];
string grid[103];

int dfs(int i, int j){
    if(i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 'L' || vis[i][j])return 0;
    vis[i][j] = 1;
    cnt++;
    for(int z = 0; z < 8; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
    return cnt;
}

int main(){
    int t, cs = 0;
    bool sp = false;
    string s;
    cin >> t;
    getchar();
    getchar();
    while(t--){
        int x, y;
        row = 0;
        if(sp)puts("");
        sp = true;
        while(getline(cin, s) && s.size()){
            if(s[0] == 'L' || s[0] == 'W'){
                grid[row] = s;
                col = grid[row++].size();
            }
            else{
                cnt = 0;
                istringstream cinn(s);
                cinn >> x;
                cinn >> y;
                memset(vis, 0, sizeof(vis));
                cout << dfs(x-1, y-1) << endl;
            }
        }
    }
    return 0;

}