吳邦一程設練習 #1

ccu_practice_1.md

吳邦一程設練習 #1 (Week 1 to Week 4)

w1a.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


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

    while (M--) {
        int A[3];
        int i,j,d;
        scanf("%d %d %d %d",&A[0],&A[1],&A[2],&d);
        int B[31] = {0};
        B[0] = A[0];
        B[1] = A[1];
        B[2] = A[2];

        int B_deg = 2;

        int t = d-1;
        while(t--)
        {
            int C[31] = {0};

            for(i=0;i<=2;i++) {
                for(j=0; j<=B_deg; j++) {
                    C[i+j] += A[i] * B[j];
                }
            }

            memcpy(B, C, sizeof(C));
            B_deg = 2 + B_deg;
        }

        for (i = 0; i <= 2*d; i++) {
            if (i != 0)
                printf(" ");
            printf("%d", B[i]);
        }
        printf("\n");
    }

    return 0;
}

w1b.c

#include <stdio.h>

int gcd(int a, int b) {
	while (b) {
		// a, b = b, a mod b
		int temp = a;
		a = b;
		b = temp % b;
	}

	return a;
}

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

	while (T--) {
		int Q1, R1, Q2, R2;
		scanf("%d %d %d %d", &Q1, &R1, &Q2, &R2);

		int g = gcd(Q1 - R1, Q2 - R2);
		int i;
		for (i=1; i <= g; i++) {
			if (g % i == 0) {
				if (i != 1)
					printf(" ");
				printf("%d", i);
			}
		}
		printf("\n");
	}

	return 0;
}

w1c.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int pos[100000+1];

int main() {
    int a, b;

    while (scanf("%d %d", &a, &b)) {
        if (b == 0) break;

        if (a == b) {
            printf("1\n");
            continue;
        }

        memset(pos, -1, sizeof(pos));

        int r = a;

        pos[r] = 0;

        int idx;
        for (idx = 1; ; idx++) {
            a = 10 * r;
            r = a % b;

            if (pos[r] != -1) {
                printf("%d\n", idx - pos[r]);
                break;
            }
            else
                pos[r] = idx;
        }

    }

    return 0;
}

w2a.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;

struct Point {
	int x, y;
};

Point data[60];

int main() {
	int T;
	cin >> T;

	while (T--) {
		int N;
		cin >> N;

		for (int i=0; i<N; i++) {
			cin >> data[i].x >> data[i].y;
		}

		int max_area = -1;
		for (int i=0; i<N-1; i++) {
			for (int j=i+1; j<N; j++) {
				int delta_x = data[i].x - data[j].x;
				int delta_y = data[i].y - data[j].y;
				int area = abs(delta_x) * abs(delta_y);
				if (area > max_area)
					max_area = area;
			}
		}

		cout << max_area << "\n";
	}

	return 0;
}

w2b.cpp

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
	string N, M;

	while (cin >> N >> M) {zz
		int cnt = 0;
		int idx = M.find(N);
		while (idx != -1) {
			cnt++;
			idx = M.find(N, idx+1);
		}

		cout << cnt << "\n";
	}

	return 0;
}

w2c.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int record[10000+10];
vector<long long> data;

int main() {
	int T;
	cin >> T;

	while (T--) {
		long long a, b;
		int c;
		cin >> a >> b >> c;

		memset(record, -1, sizeof(record));
		data.clear();

		int cycle_len = 0;
		int start_level = -1;

		int value = 1;
		record[value] = 0;
		data.push_back(value);

		for (int level=1; level <= b; level++) {
			value = (value * a) % c;

			if (record[value] != -1) {
				cycle_len = level -  record[value];
				start_level = level - cycle_len; // record[value]
				break;
			}
			else {
				record[value] = level;
				data.push_back(value);
			}
		}

		//cout << ": " << cycle_len << ", " << start_level << endl;

		if (cycle_len == 0) {
			cout << data.back() << "\n";
		}
		else {
			int idx = (b - start_level) % cycle_len + start_level;
			cout << data[idx] << "\n";
		}
	}

	return 0;
}

w3a.cpp

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long mystoll(string inp) {
    int value = 0;
    for (size_t i = 0; i < inp.length(); i++)
        value = value * 2 + (inp[i] - '0');
    return value;
}

int main() {
    ios::sync_with_stdio(false);

    int N;
    while (cin >> N) {
        if (N == 0) break;

        long long sum = 0;

        for (int i = 0; i < N; i++) {
            string inp;
            cin >> inp;
            sum += mystoll(inp);
        }

        cout << sum << "\n";
    }

    return 0;
}

w3b.cpp

#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
const int MAX_N = 10000+1;
int data[MAX_N];
int record[MAX_N][2];

void solve(int idx, int dir) {
    memset(record, -1, sizeof(record));

    if (dir == -1)
        dir = 0;

    int level = 0;
    while (true) {
        //cout << idx << ", " << dir << endl;

        if (idx < 0) {
            cout << "Backward\n";
            return;
        }
        if (idx >= N) {
            cout << "Forward\n";
            return;
        }

        if (record[idx][dir] != -1) {
            cout << "Cycle " << level - record[idx][dir] << "\n";
            return;
        }

        record[idx][dir] = level;

        if (data[idx] < 0)
            dir = 1 - dir;

        idx = idx + ((dir == 0) ? -1 : +1) * abs(data[idx]);

        level++;
    }
}

int main() {
    //ios::sync_with_stdio(false);

    while (cin >> N >> M) {
        if (N == 0 && M == 0) break;

        for (int i = 0; i < N; i++)
            cin >> data[i];

        while (M--) {
            int si, sd;
            cin >> si >> sd;
            solve(si, sd);
        }
    }

    return 0;
}

w3c.cpp

#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    while (cin >> N) {
        if (N == 0) break;

        int enemy[N];
        int us[N];
        for (int i = 0; i < N; i++)
            cin >> enemy[i];
        for (int i = 0; i < N; i++)
            cin >> us[i];

        sort(enemy, enemy + N);
        sort(us, us + N);

        int win_cnt = 0;
        int enemy_idx = N - 1;
        for (int us_idx = N - 1; us_idx >= 0; us_idx--) {
            while (enemy_idx >= 0 && enemy[enemy_idx] >= us[us_idx])
                enemy_idx--;

            if (enemy_idx == -1)
                break;

            //cout << enemy[enemy_idx] << ", " << us[us_idx] << endl;
            win_cnt++;
            enemy_idx--;
        }

        cout << win_cnt << endl;
    }

    return 0;
}

w4a.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;

double d(double px, double py) {
	// (px, 0) (0, py)
	return sqrt(px * px + py * py);
}

int main() {
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	string temp;
	getline(cin, temp);

	while (T--) {
		string inpx, inpy;
		getline(cin, inpx);
		getline(cin, inpy);

		vector<int> x;
		vector<int> y;

		istringstream issx(inpx);
		int data;
		while (issx >> data)
			x.push_back(abs(data));
		istringstream issy(inpy);
		while (issy >> data)
			y.push_back(abs(data));

		sort(x.begin(), x.end());
		sort(y.begin(), y.end());

		double sum = 0;
		const int N = x.size();
		for (int i = 0; i < N; i++) {
			//cout << d(x[i], y[N - i -1]) << endl;
			sum += d(x[i], y[N - i - 1]);
		}

		cout << (int)sum << "\n";
	}
	return 0;
}

w4b.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);

	int T;
	cin >> T;

	while (T--) {
		int N, M;
		cin >> N >> M;

		ll object[N];
		ll student[M];
		for (int i = 0; i < N; i++)
			cin >> object[i];
		for (int i = 0; i < M; i++)
			cin >> student[i];

		sort(object, object + N);
		sort(student, student + M);

		int idx = 0;
		ll reward = 0;
		for (int i = 0; i < N; i++) {
			while (idx < M && student[idx] < object[i])
				idx++;

			if (idx >= M) {
				reward = -1;
				break;
			}

			reward = reward + student[idx];
			idx++;
		}

		cout << reward << "\n";
	}

	return 0;
}

w4c.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
	ios::sync_with_stdio(false);

	int T;
	cin >> T;

	string temp;
	getline(cin, temp);

	while (T--) {
		string inp;
		getline(cin, inp);

		int cnt[26];
		memset(cnt, 0, sizeof(cnt));

		int len = inp.length();
		for (int i = 0; i < len; i++) {
			if ('A' <= inp[i] && inp[i] <= 'Z')
				cnt[inp[i] - 'A']++;
			else if ('a' <= inp[i] && inp[i] <= 'z')
				cnt[inp[i] - 'a']++;
		}

		int maximum = -1;
		for (int i = 0; i < 26; i++)
			maximum = max(maximum, cnt[i]);

		if (maximum == -1) {
			cout << "\n";
			continue;
		}

		for (int i = 0; i < 26; i++) {
			if (cnt[i] == maximum) {
				cout << (char)('A' + i);
			}
		}
		cout << "\n";


	}

	return 0;
}