【UVa】11729 - Commando War

Problem here

Solution

---

N年冇寫
先水一題
xdd

---

按執行時間由大到小排序
找完成所有任務的總時間

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
bool cmp(pair<int, int>a , pair<int, int> ai){
    return a.second > ai.second;
}
int main(){
    int n, b, j;
    int count = 0;
    while(cin >> n){
        vector<pair<int, int> > s;
        if(n == 0)
            break;

        for(int i = 0; i < n; i++){
            cin >> b >> j;
            s.push_back(make_pair(b,j));
        }
        sort(s.begin(), s.end(), cmp);
        int time = 0,tb = 0;
        for(int i = 0; i < s.size(); i++){
            tb += s[i].first;
            time = max(time, tb+s[i].second);
        }
        cout << "Case " << ++count << ": " << time << endl;
    }
    return 0;
}

【CodeChef】Fit Squares in Triangle

Problem here

Solution

water

#include <iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        while(n--){
            int l;
            cin >> l;
            int t = (l/2-1)*((l/2-1)+1) / 2;
            if(t)
                cout << t << endl;
            else 
                cout << 0 << endl;
        }
    }
    return 0;
}

【UVa】Brick Wall Patterns

Problem here

Solution

*記得要開long long int

#include <iostream>
#include <memory.h>
using namespace std;
long long int dp[51];
int main(){
    int n;
    memset(dp, 0, sizeof(dp));
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= 50; i++)
        dp[i] = dp[i-1] + dp[i-2];
    while(cin >> n){
        if(n == 0)
            break;
        cout << dp[n] << endl;
    }
    return 0;
}

【UVa】11015 Rendezvous

Problem here

Solution

輸入是從1開始數的，所以讀入時將u, v 都-1
先刷所有最短路
再找最小總和

#include <iostream>
#include <string>
#include <memory.h>
#include <vector>
#define max_num 9999
using namespace std;
int rat[30][30];
vector<string> names;
int main(){

    int n, m;
    int kase = 1;
    while(cin >> n >> m){
        if(n == 0)
            break;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(i==j)
                    rat[i][j] = rat[j][i] = 0;
                else
                    rat[i][j] = rat[j][i] = max_num;

        for(int i = 0; i < n; i++){
            string input;
            cin >> input;
            names.push_back(input);
        }
        for(int i = 0; i < m; i++){
            int u, v, k;
            cin >> u >> v >> k;
            rat[u-1][v-1] = rat[v-1][u-1] = k;
        }

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                    if(rat[j][k] >  rat[j][i] + rat[i][k])
                        rat[j][k] =  rat[j][i] + rat[i][k]; 

        int min = max_num;
        int rec;
        for(int i = 0; i < n; i++){
            int sum = 0;
            for(int j = 0; j < n; j++){
                sum += rat[i][j];
            }
            if(sum < min){
                min = sum;
                rec = i;
            }
        }
        cout << "Case #" << kase++ << " : " << names[rec] << endl;
        names.clear();
    }

    return 0;
}

【UVa】11463 - Commandos

Problem here

Solution

floyd刷所有點到其他點的最短路
再在上面找開始點到集合點的最大值

#include <iostream>
#include <memory.h>
#define MAX_NUM 1<<29
using namespace std;
int main(){
    int kase;
    cin >> kase;
    int cnt = 1;
    while(kase--){
        int n, r;
        int rat[101][101];
        cin >> n >> r;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(i==j)
                    rat[i][j] = rat[j][i] = 0;
                else
                    rat[i][j] = MAX_NUM;
        int s, e;
        while(r--){
            int x, y;
            cin >> x >> y;
            rat[x][y] = rat[y][x] = 1;
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                    if(rat[j][i] + rat[i][k] < rat[j][k])
                        rat[j][k] = rat[j][i] + rat[i][k];
        cin >> s >> e;

        int ans = 0;
        for(int i = 0; i < n; i++)
            if(ans < rat[s][i] + rat[i][e])
                ans = rat[s][i] + rat[i][e];
        cout << "Case " << cnt++ << ": " << ans << endl;
    }
    return 0;
}

【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;
}