2016 ACM-ICPC Taiwan Online Practice Contests 2: NCTU Problemset

Iðunn.cpp

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int ncase;
    scanf("%d", &ncase);

    while(ncase--) {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);

	int apple[n];
	for(int i = 0; i < n; i++)
	    scanf("%d", &apple[i]);

	int degree[n];
	memset(degree, 0, sizeof(degree));
	for(int i = 0; i < m; i++) {
	    int u, v;
	    scanf("%d %d", &u, &v);
	    u--;
	    v--;
	    degree[u]++;
	    degree[v]++;
	}

	double prob[n];
	for(int i = 0; i < n; i++) {
	    prob[i] = (double) apple[i] * degree[i] * k / (double) (2 * m);
	}

	double ans = 0;
	for(int i = 0; i < n; i++)
	    ans += prob[i];
	printf("%.15f\n", ans);
    }

    return 0;
}

Kaprekar's constant.cpp

#include <bits/stdc++.h>

using namespace std;

int main()
{

    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
	int n;
	scanf("%d", &n);
	map<int, int> cycle;
	map<int, int> cycleNumber;

	int counter = 1;
	while (true) {
	    int cnt[10];
	    memset(cnt, 0, sizeof(cnt));

	    int idx = 0;
	    while (n > 0) {
		idx++;
		cnt[n % 10]++;
		n /= 10;
	    }
	    cnt[0] += 5 - idx;

	    // get max num
	    int mx = 0;
	    for (int i = 9; i >= 0; i--) {
		if (cnt[i] != 0) {
		    for (int j = 0; j < cnt[i]; j++) {
			mx *= 10;
			mx += i;
		    }
		}
	    }

	    // get min num
	    int mn = 0;
	    for (int i = 0; i < 10; i++) {
		if (cnt[i] != 0) {
		    for (int j = 0; j < cnt[i]; j++) {
			mn *= 10;
			mn += i;
		    }
		}
	    }

	    // out.println(mn + " " + mx);
	    n = mx - mn;
	    //out.println("n = " + n);
	    if (cycle.find(n) != cycle.end()) {
		int first = cycle[n];
		int cycleLength = counter - first;

		/*
		   out.println("first= " + first);
		   out.println("cycle Length = " + cycleLength);
		 */

		int ans = (999999 - (first - 1)) % cycleLength;
		ans = ans == 0 ? cycleLength : ans;
		ans += first - 1;
		//out.println("ans  = " + ans + " " + cycleNumber.get(ans));
		printf("%05d\n", cycleNumber[ans]);
		break;
	    }

	    //out.println("counter = " + counter + ", " + n);
	    cycle[n] = counter;
	    cycleNumber[counter++]=  n;
	}
    }
    return 0;
}

Odin.cpp

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

typedef long long ll;
const int MAX_N = 10;
const int MAX_M = 300;
const ll INF = 1e18;

int N, M, E;
int R[MAX_M];
ll f[MAX_M][MAX_M];
ll dp[MAX_N][MAX_M];
vector<int> places[MAX_N];

void floyd_warshall() {
    for (int k = 0; k < M; k++) {
        for (int u = 0; u < M; u++) {
            for (int v = 0; v < M; v++) {
                f[u][v] = min(f[u][v], f[u][k] + f[k][v]);
            }
        }
    }
}

int solve() {
    floyd_warshall();

    for (int r0 : places[0]) {
        dp[0][r0] = 0;
    }
    for (int i = 0; i < N - 1; i++) {
        for (int u : places[i]) {
            for (int v : places[i + 1]) {
                // cout << i << ", " << u << ", " << v << endl;
                dp[i + 1][v] = min(dp[i + 1][v], dp[i][u] + f[u][v]);
            }
        }
    }

    ll ans = INF;
    for (int u : places[N - 1]) {
        ans = min(ans, dp[N - 1][u]);
    }

    if (ans >= INF)
        return -1;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int TC;
    cin >> TC;
    while (TC--) {
        cin >> N >> M >> E;

        for (int u = 0; u < M; u++) {
            fill(f[u], f[u] + M, INF);
            f[u][u] = 0;
        }
        for (int i = 0; i < N; i++) {
            fill(dp[i], dp[i] + M, INF);
            places[i].clear();
        }

        for (int u = 0; u < M; u++) {
            cin >> R[u];
            places[R[u]].push_back(u);
        }

        for (int i = 0; i < E; i++) {
            int u, v; ll w;
            cin >> u >> v >> w;
            f[u][v] = min(f[u][v], w);
        }

        cout << solve() << endl;
    }

    return 0;
}

Thor's Successor.java

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));

        // Start writing your solution here.
        
        int ncase = sc.nextInt();
        while(ncase-- > 0) {
        	int n = sc.nextInt();
        	int[] inp = new int[n];
        	for(int i = 0; i < n; i++)
        		inp[i] = sc.nextInt();
        	
        	Arrays.sort(inp);
        	
        	int ans = 0;
        	for(int i = inp.length - 1; i > inp.length - 4; i--) {
        		ans += inp[i];
        	}
        	out.println(ans);
        }
      
        // Stop writing your solution here.
        out.close();
    }

    // PrintWriter for faster output
    public static PrintWriter out;

    // MyScanner class for faster input
    public static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        boolean hasNext()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    return false;
                }
            }
            return true;
        }

        String next()
        {
            if (hasNext())
                return st.nextToken();
            return null;
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Triangles.cpp

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

typedef long long ll;

ll C(ll a) {
	return (a * (a - 1) * (a - 2)) / 6;
}

int N, M;

ll get_internal(int r1, int c1, int r2, int c2) {
	if (r1 == r2)
		return 0;
	if (c1 == c2)
		return 0;

	return __gcd(abs(r2 - r1), abs(c2 - c1)) - 1;
}

void solve() {
    ll ans = C(N * M) - C(N) * M - C(M) * N;

	ll m = 0;
    for (int r1 = 0; r1 < N; r1++) {
		for (int c1 = 0; c1 < M; c1++) {
			for (int r2 = 0; r2 < N; r2++) {
				for (int c2 = 0; c2 < M; c2++) {
					ll cnt = get_internal(r1, c1, r2, c2);
					m += cnt;

					// printf("(%d, %d, %d, %d) : %lld\n", r1, c1, r2, c2, cnt);
				}
			}
		}
	}

	printf("%lld\n", ans - m / 2);
}

int main() {
    int TC;
    scanf("%d", &TC);
    while (TC--) {
        scanf("%d %d", &N, &M);
        solve();
    }

    return 0;
}