f447: 12918 - Lucky Thief

解題心得

這題滿簡單的，想不到會在第四題。

只要稍微推一下就知道是連續數字的相加，代入公式就好，但沒想到CPE測資比ZJ嚴格。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int t, n, m;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		cout << (m - 1 + m - n) * n / 2 << endl;
	}
	return 0;
}

f446: 1237 - Expert Enough

解題心得

每次有新的query，就掃過所有車種，看有幾個符合，以及記錄符合的index。

如果有零個或不只一個，那就不對。如果只有一個，那就可以用index找到車種名稱了。

程式碼

#include <iostream>
#include <string>
using namespace std;

struct carInfo
{
	string name;
	int low, high;
};
carInfo db[10000];
int main()
{
	int t, d, l, h, q, p;
	string m;
	cin >> t;
	while (t--)
	{
		cin >> d;

		for (int i = 0; i < d; i++)
			cin >> db[i].name >> db[i].low >> db[i].high;
		cin >> q;
		while (q--)
		{
			cin >> p;
			int flag = 0, index = -1;
			for (int i = 0; i < d; i++)
			{
				if (db[i].low <= p && p <= db[i].high)
					flag++, index = i;
			}
			if (flag != 1) cout << "UNDETERMINED" << endl;
			else cout << db[index].name << endl;
		}
		
		if (t != 0) cout << endl;
	}
	return 0;
}

f445: 263 - Number Chains

解題心得

照著題目敘述做就好。

程式碼

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int descending(int n)
{
	int arr[10] = { 0 }, ans = 0;
	while (n)
	{
		arr[n % 10]++;
		n /= 10;
	}
	for (int i = 9; i >= 0; i--)
	{
		while (arr[i] != 0)
		{
			ans = ans * 10 + i;
			arr[i]--;
		}
	}
	return ans;
}
int ascending(int n)
{
	int arr[10] = { 0 }, ans = 0;
	while (n)
	{
		arr[n % 10]++;
		n /= 10;
	}
	for (int i = 0; i < 10; i++)
	{
		while (arr[i] != 0)
		{
			ans = ans * 10 + i;
			arr[i]--;
		}
	}
	return ans;
}
int main()
{
	int n;
	while (cin >> n && n)
	{
		vector<int> v;
		cout << "Original number was " << n << endl;
		while (true)
		{
			int ascend = ascending(n), descend = descending(n), result = descend - ascend;
			cout << descend << " - " << ascend << " = " << result << endl;
			
			if (v.size() != 0 && find(v.begin(), v.end(), result) != v.end())
				break;
			v.push_back(result);
			n = result;
		}
		cout << "Chain length " << v.size() + 1 << endl << endl;
		
	}
	return 0;
}

f444: 10268 - 498-bis

解題心得

CPE 的系統跟 zerojudge 的測資格式不太一樣，後者好像不是用 \n 換行，只好再用別的方法寫。

程式碼

[for CPE]

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main()
{
	long long int x, a;
	while (cin >> x)
	{
		vector<long long int> bits;
		long long int ans = 0;
		while (cin >> a && getchar() != '\n')
			bits.push_back(a);
		for (int i = 0; i < bits.size(); i++)
		{
			bits[i] *= bits.size() - i;
			ans += bits[i] * pow(x, bits.size() - 1 - i);
		}
		cout << ans << endl;
	}
	return 0;
}

[for ZJ]

#include <iostream>
#include <vector>
#include <sstream>
#include <math.h>
#include <string>
using namespace std;

int main()
{
	long long int x, a;
	string s;
	while (cin >> x)
	{
		vector<long long int> bits;
		long long int ans = 0;
		cin.ignore();
		getline(cin, s);
		stringstream ss(s);
		while (ss >> a)
			bits.push_back(a);
		bits.pop_back();
		for (int i = 0; i < bits.size(); i++)
		{
			bits[i] *= bits.size() - i;
			ans += bits[i] * pow(x, bits.size() - 1 - i);
		}
		cout << ans << endl;
	}
	return 0;
}

f439: 10191 - Longest Nap

解題心得

這題不難，只是很多瑣碎的地方要弄。

基本上就是把開始跟結束時間轉換成分鐘，然後用陣列來記錄哪些時候有空或沒空，最後再從頭掃到尾找最長的空檔。因為是10:00開始，把所有轉換後的時間減10*60分鐘。

寫完後覺得寫很醜，如果用開始跟結束時間作為標記，不知道會不會好看一點。

程式碼

#include <iostream>
#include <string>
using namespace std;

int t[480] = { 0 };

int to_int(string s)
{
	int n = 0;
	n = stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2)) - 600;
	return n;
}

int main()
{
	int testcase, counter = 1;
	while (cin >> testcase)
	{
		cin.ignore();
		for (int i = 0; i < 480; i++) t[i] = 0;
		for (int days = 1; days <= testcase; days++)
		{
			string s, start, end;
			getline(cin, s);
			start = s.substr(0, 5);
			end = s.substr(6, 5);
			for (int i = to_int(start); i <= to_int(end); i++)
				t[i] = 1;

			//cout << to_int(start) << " " << to_int(end) << endl;
		}
		int prev = -1, count = 0, maxCount = 0, curTime = 0, time = 0;
		for (int i = 0; i < 480; i++)
		{
			if (t[i] == 0)
				count++;
			if ((t[i] == 1 && prev == 0) || i == 479)
			{
				if (curTime == 0) count--;
				if (count + 1 > maxCount)
				{
					maxCount = count + 1;
					time = curTime;
				}
				count = 0;
				//cout << "update: " << maxCount << endl;
			}
			if (t[i] == 0 && prev == 1)
				curTime = i - 1;
			prev = t[i];
		}
		cout << "Day #" << counter++ << ": the longest nap starts at " << (time + 600) / 60 << ":";
		if ((time + 600) % 60 < 10) cout << "0" << (time + 600) % 60 ;
		else cout << (time + 600) % 60;
		cout << " and will last for ";
		if (maxCount < 60) cout << maxCount << " minutes.\n";
		else cout << maxCount / 60 << " hours and " << maxCount % 60 << " minutes.\n";

	}
	return 0;
}
// 18*60 - 10*60 = 8*60 = 480

f438: 855 - Lunch in Grid City

解題心得

最後好像也沒用到s跟a的值。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
	int t, s, a, f;
	cin >> t;
	while (t--)
	{
		int arrS[50001], arrA[50001];
		cin >> s >> a >> f;
		for (int i = 0; i < f; i++)
			cin >> arrS[i] >> arrA[i];
		sort(arrS, arrS + f);
		sort(arrA, arrA + f);

		if (f % 2 == 1) cout << "(Street: " << arrS[f / 2] << ", Avenue: " << arrA[f / 2] << ")" << endl;
		else cout << "(Street: " << arrS[f / 2 - 1] << ", Avenue: " << arrA[f / 2 - 1] << ")" << endl;
	}
	return 0;
}

a941: 10041 - Vito's large family

解題心得

vito family的進化版(?)，如果直接重跑過一遍s[]把距離加起來會tle。

但最後還是用了黑魔法的那兩行才過的。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;

int s[2000000] = { 0 },record[30001] = { 0 };

int main()
{
	cin.sync_with_stdio(false), cin.tie(0);
	int t, r;
	cin >> t;
	while (t--)
	{
		cin >> r;
		for (int i = 0; i < 30001; i++)
			record[i] = 0;
		for (int i = 0; i < r; i++)
		{
			cin >> s[i];
			record[s[i]]++;
		}
		sort(s, s + r);
		int mid = 0;
		long long int d = 0;
		if (r % 2 == 1) mid = s[r / 2];
		else mid = s[r / 2 - 1];
		for (int i = 0; i <= 30000; i++)
		{
			d += abs(i - mid) * record[i];
		}
		cout << d << " " << mid << endl;
	}
	return 0;
}

d501: 第二題：數列最小值

解題心得

很像高中數學曾經學過的題目，印象中解法是：

1. 當 n 為奇數，則答案為中位數

2. 當 n 為偶數，則答案為區間內的所有整數

程式碼

#include <iostream>
#include <algorithm>
using namespace std;

int n, arr[1000000] = { 0 };

int main()
{
	while (cin >> n)
	{
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		sort(arr, arr + n);
		if (n % 2 == 1)
			cout << "A=" << arr[n / 2] << endl;
		else
		{
			cout << "A=";
			for (int i = arr[n / 2 - 1]; i <= arr[n / 2]; i++)
			{
				if (i != arr[n / 2])
					cout << i << "、";
				else
					cout << i << endl;
			}
		}
		
	}
	return 0;
}

f437: 1368 - DNA Consensus String

解題心得

要找到第 i 個會是哪個字母，就去統計所有的字串的第 i 個都是哪些字母，找出現最多的那個。如果出現次數相同，則按照字典序順序，所以判斷式的等於才會那樣寫。

要計算 hamming 距離，就是統計不符合的字元次數。

程式碼

#include <iostream>
using namespace std;

int main()
{
	int t, m, n;
	string s[50];
	cin >> t;
	while (t--)
	{
		cin >> m >> n;
		for (int i = 0; i < m; i++)
			cin >> s[i];
		string ans = "";
		int d = 0;
		for (int i = 0; i < n; i++)
		{
			int countA = 0, countT = 0, countC = 0, countG = 0;
			for (int j = 0; j < m; j++)
			{
				if (s[j][i] == 'A') countA++;
				else if (s[j][i] == 'T') countT++;
				else if (s[j][i] == 'C') countC++;
				else if (s[j][i] == 'G') countG++;
			}
			if (countA >= countC && countA >= countG && countA >= countT)
				ans += "A", d += countC + countG + countT;
			else if (countC > countA && countC >= countG && countC >= countT)
				ans += "C", d += countA + countG + countT;
			else if (countG > countA && countG > countC && countG >= countT)
				ans += "G", d += countC + countA + countT;
			else
				ans += "T", d += countC + countG + countA;
		}
		cout << ans << endl << d << endl;
	}
	return 0;
}

11498: Division of Nlogonia

解題心得

沒有心得。

程式碼

#include <iostream>
using namespace std;

int main()
{
	int t, n, m, x, y;
	while (cin >> t && t)
	{
		cin >> n >> m;
		while (t--)
		{
			cin >> x >> y;
			if (x > n && y > m)
				cout << "NE" << endl;
			else if (x < n && y > m)
				cout << "NO" << endl;
			else if (x > n && y < m)
				cout << "SE" << endl;
			else if (x < n && y < m)
				cout << "SO" << endl;
			else
				cout << "divisa" << endl;
		}
	}
	return 0;
}