【UVa】Expanding Fractions

Problem here

Solution

#include <iostream>
#include <memory.h>
#include <string>
using namespace std;

int main(){
    int n, m;
    int len[1001];
    while(cin >> n >> m){
        if(n == 0 && m == 0)
            break;
        memset(len, -1, sizeof(len));
        len[n] = 0;
        string output = ".";
        while(n){
            n *= 10;
            output += (n/m) + '0';
            n %= m;
            if(len[n%m] != -1)
                break;
            len[n] = output.length()-1;
        }
        for(int i = 0; i < output.length(); i++){
            if(i > 0 && (i%50)==0 )
                cout << endl;
            cout << output[i];
        }
        cout << endl;
        if(n != 0)
            cout << "The last " << output.length() - len[n%m] - 1 << " digits repeat forever." << endl;
        else
            cout << "This expansion terminates." << endl;

        //UVa 要再output一空行
        //cout << endl
    }
    return 0;
}

【UVa】Frogger

Problem here

Solution

自己的石子為點0，目標石子為1
生成MST直到點0點1連通

#include <iostream>
#include <vector>
#include <memory.h>
#include <utility>
#include <string>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
vector<pair<float, pair<int, int> > > edges;
string spp;
float cal(int x1, int x2, int y1, int y2){
    return (float)sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

bool cmp(pair<float, pair<int, int> > a, pair<float, pair<int, int> > b){
    return a.first < b.first;
}

int pre[1000];

int find(int x){
    int r = x;
    while(pre[r] != r){
        r = pre[r];
    }
    int j = x, y;
    while(j != r){
        y = pre[j];
        pre[j] = r;
        j = y;
    }
    return r;
}

void join(int a, int b){
    int fa = find(a);
    int fb = find(b);
    if(fa != fb){
        pre[fa] = fb;
    }
}
int main(){
    int n;
    int count = 1;
    while(cin >> n){
        if(n==0)
            break;
        vector<pair<int , int > > point;
        for(int i = 0; i < n; i++){
            int x, y;
            cin >> x >> y;
            point.push_back(make_pair(x,y));
            for(int j = 0; j < i; j++){
                edges.push_back(make_pair(cal(point[i].first, point[j].first, point[i].second, point[j].second), make_pair(i, j)) );
            }
        }
        cout << "Scenario #" << count++ << endl;

        sort(edges.begin(), edges.end(), cmp);
        for(int i = 0; i < n; i++)
            pre[i] = i;
        for(int i = 0; i < edges.size(); i++){
            if(find(edges[i].second.first)==find(edges[i].second.second))
                continue;

            join(edges[i].second.first, edges[i].second.second);
            if(find(1) == find(0)){
                printf("Frog Distance = %.3lf\n", edges[i].first);
                break;
            }

        }

        edges.clear();
        cout << endl;
        getline(cin, spp);
    }
    return 0;
}

【Zerojudge】d908

Problem here

Solution

DFS

#include <iostream>
#include <memory.h>
using namespace std;
int rat[30][30];
bool visit[30];
int sum;
void solve(int here, int cost){
    sum = max(sum, cost);
    visit[here] = true;
    for(int i = 0; i < 26; i++){
        if(visit[i] == false && rat[here][i] != 0){
            solve(i, cost+rat[here][i]);
            visit[i] = false;
        }
    }
}

int main(){
    char start;
    while(cin >> start){
        int n;cin >> n;
        sum = 0;
        memset(rat, 0, sizeof(rat));
        memset(visit, false, sizeof(visit));
        while(n--){
            char a, b;int w;
            cin >> a >> b >> w;
            rat[a-'A'][b-'A'] = max(rat[a-'A'][b-'A'], w);
        }
        solve(start-'A', sum);
        cout << sum << endl;

    }

    return 0;
}

【UVa】12149 - Feynman

Problem here

Solution

N增加1, 總正方形數會增加N*N

1. #include <iostream>
2. #include <memory.h>
3. using namespace std;
4. int mark[101];
5. int main(){
6. int n;
7. memset(mark, 0, sizeof(mark));
8. while(cin >> n){
9. if(n == 0)
10. break;
12. for(int i = 1 ; i <= n; i++)
13. if(mark[i] == 0)
14. mark[i] = mark[i-1] + (i*i);
16. cout << mark[n] << endl;
18. }
19. return 0;
20. }

【SPOJ】AIBOHP - Aibohphobia

Problem here

Solution

答案＝原字串長度-原字串與其反轉後字串的lcm

一開始用top down寫，TLE orz…. 
之後改成 bottom up 才AC

#include <iostream>
#include <string>
using namespace std;
string input, res;
int lcs[6101][6101];

int main(){

    int kase;
    cin >> kase;
    while(kase--){
        cin >> input;
        res.resize(input.size());
        for(int i = 0; i < input.length(); i++)
            res[i] = input[input.length()-1-i];

        for(int m = 0; m <= input.length(); m++){
            for(int n = 0; n <= res.length(); n++){
                if(m == 0 || n == 0)
                    lcs[m][n] = 0;
                else if(input[m-1] == res[n-1])
                    lcs[m][n] = 1 + lcs[m-1][n-1];
                else
                    lcs[m][n] = max(lcs[m][n-1], lcs[m-1][n]);
            }
        }

        cout << input.length() - lcs[input.length()][res.length()] << endl;
    }

    return 0;
}