This is an editorial for the NTUPC 2021 (臺大盃 2021 全国中学生程式设计竞赛).

Try out the contest here! (You will need a Codeforces account to access the contest)

Table of Contents

Candies and Wrappers (30 marks)

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

int main() {
  int m, n, p, q;
  cin >> m >> n >> p >> q;
  int candies = m * n;
  int wrappers = 0;
  int ate = 0;
  while (candies > 0) {
    // Eat all the candies
    ate += candies;
    // Add the wrappers
    wrappers += candies;
    // Exchange wrappers for candies
    candies = (wrappers / p) * q;
    // Excess wrappers
    wrappers %= p;
  }
  cout << ate << endl;
}

Age of Tree (30 marks)

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

map<string, double> growth_factor = {
    {"American Beech", 6},       {"Basswood", 3},
    {"Common Horsechestnut", 8}, {"Dogwood", 7},
    {"European White Birch", 5}, {"White Fir", 7.5}};

typedef long double ld;
const ld PI = 3.141592;
int main() {
  cout << fixed << setprecision(1);
  ld m;
  cin >> m;
  if (m - floor(m) != 0 || m <= 0) {
    cout
        << "You must specify a positive integer number for the number of trees!"
        << endl;
    return 0;
  }

  int n = m;
  ld circum;
  string tree;
  for (int i = 0; i < n; i++) {
    cin >> circum;
    getline(cin, tree);  // remove newline
    getline(cin, tree);  // read tree name
    if (circum <= 0) {
      cout << "The circumference for " << tree << " must be greater than 0!"
           << endl;
      continue;
    }
    if (!growth_factor.count(tree)) {
      cout << "Species entered is not available!" << endl;
      continue;
    }
    cout << tree << " : " << circum << " : "
         << circum / PI * growth_factor[tree] << endl;
  }
}

Finding Vocabularies (30 marks)

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

int main(){
  vector<string> v;
  set<string> res;
  string s;
  while(!cin.eof()){
    cin >> s;
    if(s.empty()) break;
    v.push_back(s);
  }
  for(auto now : v){
    s.clear();
    for(auto c : now){
      if(isalpha(c)) s += toupper(c);
      if(c == '\'') s += '\'';
    }
    if(!s.empty()) res.insert(s);
  }
  cout << res.size() << endl;
  for(auto now : res) cout << now << endl;
}

DNA Matching (40 marks)

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

string cp(string s, int n){
	// copy s for n times
	string ans = "";
	for(int i = 0; i < n; i++) ans += s;
	return ans;
}

int main(){
	string s,d,dna[4]; cin >> s >> d >> dna[0] >> dna[1] >> dna[2] >> dna[3];

	for(int i=0;i<4;i++){
		if(dna[i] == d){
			cout << i+1 << endl;
			int longest = 0;
			for(int t=1;;t++){
				string tmp = cp(s,t);
				if(d.find(tmp) != string::npos){
					longest = t;
				} else break;
			}
			cout << longest << endl;
			return 0;
		}
	}
	cout << 0 << endl << 0 << endl;
}

Two-Opt Swaps (40 marks)

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

int main() {
  string s = "abcdefgha";
  int n;
  cin >> n;
  while (n--) {
    char c, d;
    cin >> c >> d;
    int pos1, pos2;
    pos1 = s.find(c);
    pos2 = s.find(d);
    if (pos1 > pos2) swap(pos1, pos2);
    reverse(s.begin() + pos1, s.begin() + pos2 + 1);
  }
  cout << s << endl;
}

Malaysian ID Card Number (40 marks)

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

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
#define _ << ' ' <<
typedef long long ll;
typedef long double ld;

vector<string> split(string s, char n = ';') {
  string cur;
  vector<string> res;
  for (char c : s) {
    if (c == n) {
      res.push_back(cur);
      cur.clear();
    } else
      cur += c;
  }
  res.push_back(cur);
  return res;
}

/* map number to month name */
const string month_name[] = {"January",   "February", "March",    "April",
                             "May",       "June",     "July",     "August",
                             "September", "October",  "November", "December"};

struct person {
  string ic;
  ll day;
  ll month;
  ll year;
  bool male;
  person(string _ic) {
    ic = _ic;
    male = (ic.back() - '0') & 1;
    year = stoll(ic.substr(0, 2));
    if (year >= 30)
      year += 1900;
    else
      year += 2000;
    month = stoll(ic.substr(2, 2));
    day = stoll(ic.substr(4, 2));
  }
  ll birthdate() { return year * 10000 + month * 100 + day; }
  string str() {
    return ic + " " + ic.substr(4, 2) + " " + (month_name[month - 1]) + " " +
           to_string(year) + (male ? " Male" : " Female");
  }
};

/* Birthdate */
bool birthdate(person a, person b) { return a.birthdate() < b.birthdate(); }

/* Birth year */
bool birthyear(person a, person b) { return a.year < b.year; }

/* Birth Month */
bool birthmonth(person a, person b) { return a.month < b.month; }

/* Birth Day */
bool birthday(person a, person b) { return a.day < b.day; }

/* Male */
bool male(person a, person b) { return a.male > b.male; }

/* Female */
bool female(person a, person b) { return a.male < b.male; }

int main() {
  string s;
  cin >> s;
  vector<string> ic = split(s);
  vector<person> pl;
  for (auto k : ic) pl.push_back(person(k));
  // for (auto p : pl) cout << p.str() << endl;
  string c[3];
  getline(cin, c[0]);  // newline
  getline(cin, c[2]);
  getline(cin, c[1]);
  getline(cin, c[0]);
  for (int i = 0; i < 3; i++) {
    if (c[i] == "Birthdate")
      stable_sort(pl.begin(), pl.end(), birthdate);
    else if (c[i] == "Birth Year")
      stable_sort(pl.begin(), pl.end(), birthyear);
    else if (c[i] == "Birth Month")
      stable_sort(pl.begin(), pl.end(), birthmonth);
    else if (c[i] == "Birth Day")
      stable_sort(pl.begin(), pl.end(), birthday);
    else if (c[i] == "Gender with Male first")
      stable_sort(pl.begin(), pl.end(), male);
    else if (c[i] == "Gender with Female first")
      stable_sort(pl.begin(), pl.end(), female);
  }
  for (auto p : pl) cout << p.str() << endl;
}

Minesweeping Field (40 marks)

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

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(){
	int m,n,z;
	cin >> m >> n >> z;
	vector<vector<int>> a(m+2, vector<int>(n+2, 0));
	while(z--){
		int x,y;
		cin >> x >> y;
		x++; y++;
		a[x][y] = -1;
		for(int i=0;i<8;i++){
			if(a[x+dx[i]][y+dy[i]] >= 0)
				a[x+dx[i]][y+dy[i]]++;
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j] == -1)
				cout << '*';
			else
				cout << a[i][j];
		}
		cout << endl;
	}
}

Linear Interpolation (40 marks)

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

int main(){
	cout << fixed << setprecision(2);
	int n; cin >> n;
	vector<double> a(n);
	for(int i=0;i<n;i++){
		string s; cin >> s;
		if(s != "#") a[i] = stod(s);
		else a[i] = -1;
	}

	double fr = a[0];
	int hc = 0;
	for(int i=0;i<n;i++){
		if(a[i] == -1){
			hc++;
		} else {
			if(hc){
				double each = (a[i] - fr) / (hc + 1);
				// print the missing values
				for(int j=0;j<hc;j++){
					cout << fr + each * (j + 1) + (double)(0.0001) << endl;
				}
				hc = 0;
			}
			fr = a[i];
		}
	}
}

Food Preparation Arrangement (50 marks)

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

vector<string> split(string s, char c) {
    vector<string> res;
    stringstream ss(s);
    string x;
    while (getline(ss, x, c)) res.push_back(x);
    return res;
}

string timeToString(int raw_m){
  raw_m *= 5;
  // 10:00 + raw_m minutes
  int m = raw_m % 60;
  int h = raw_m / 60 + 10;
  string res = to_string(h);
  if (m < 10) res += ":0" + to_string(m);
  else res += ":" + to_string(m);
  return res;
}

int main(){
  string s; cin >> s;
  vector<string> ord = split(s,';');
  vector<string> cus;
  vector<vector<int>> num;
  for(auto ss : ord){
    cus.push_back(split(ss,'#')[0]);
    vector<string> orders = split(ss,'%');
    vector<int> res;
    for(auto k : orders){
      res.push_back(stoi(split(k,':')[1]));
    }
    sort(res.begin(),res.end(),greater<int>());
    num.push_back(res);
  }
  int chef[3] = {0,0,0};
  for(int i=0;i<(int)num.size();i++){
    int cur_max = 0;
    for(auto n : num[i]){
      sort(chef,chef+3);
      chef[0] += n;
      cur_max = max(cur_max,chef[0]);
    }
    cout << cus[i] << " can collect food at " << timeToString(cur_max) << endl;
  }
}

Minimum Amount of Bill (50 marks)

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

typedef long double ld;

int main(){
  cout << fixed << setprecision(2);
  ld a[8];
  for(int i=0;i<8;i++) cin >> a[i];
  sort(a,a+8);
  ld total = accumulate(a,a+8,0.0);
  ld ans = total;
  do {
    ld cur = total;
    if(a[0] + a[1] + a[2] >= 80 - 1e-5) cur -= a[3]/2;
    if(a[4] + a[5] + a[6] >= 80 - 1e-5) cur -= a[7]/2;
    ans = min(ans,cur);
  } while(next_permutation(a,a+8));
  cout << ans << endl;
}

Partitions of a Number (60 marks)

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

typedef long long ll;

vector<vector<int>> p(17);

int dfs(int cur_2 /* need to start from cur_2 */, int cur_3 /* max */, ll N){
  int total = 0;
  for(int i=cur_2;i<(int)p.size();i++){
    for(int j=0;j<(int)p[i].size();j++){
      if(p[i][j] >= cur_3) break;
      ll cur = pow(2,i) * pow(3,p[i][j]);
      if(cur == N) total++;
      else if(cur < N)
        total += dfs(i+1,p[i][j],N - pow(2,i)*pow(3,p[i][j]));
    }
  }
  return total;
}

int main(){
  // see how many 2^a 3^b is within 1e5
  for(ll a = 0; a <= 16; a++){
    for(ll b = 0; b <= 20; b++){
      ll n = pow(2, a) * pow(3, b);
      if(n <= 1e5){
        p[a].push_back(b);
      }
    }
  }
  int n; cin >> n;
  cout << dfs(0,1e9,n) << endl;
}

Roots of Polynomials (60 marks)

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

typedef long double ld;

struct polynomial {
  int deg = 0;
  vector<ld> a;
  polynomial() : polynomial(0) {}
  explicit polynomial(int d) {
    if (d >= 0) {
      deg = d;
      a.assign(d + 1, 0);
    }
  }
  void set(int p, ld val) { a[p] = val; }
  ld eval(ld x) {
    ld res = 0;
    for (int i = 0; i <= deg; i++) {
      res += (ld)pow(x, i) * (ld)a[i];
    }
    return res;
  }
  polynomial derivative() {
    if (!deg) return polynomial();
    polynomial res(deg - 1);
    for (int i = 0; i < deg; i++) {
      res.set(i, a[i + 1] * (i + 1));
    }
    return res;
  }
  ld newton_method(ld low, ld high) {
    /* Newton's method, there exists exactly one root between low and high */
    /* Find the root between low and high */
    /* split into 100 parts, 10000 iterations each */
    if(abs(eval(low)) < 1e-10) return low;
    if(abs(eval(high)) < 1e-10) return high;
    polynomial f = derivative();
    for(ld i = low; i <= high; i+=(high-low)/100){
      ld x = i;
      for (int j = 0; j < 1000; j++) {
        ld fx = eval(x);
        ld fpx = f.eval(x);
        x -= fx / fpx;
        if(low < x && x < high && abs(eval(x)) < 1e-10){
          return x;
        }
      }
    }
  }
};

int main() {
  cout << fixed << setprecision(6);
  int n;
  cin >> n;
  polynomial poly(n);
  ld k;
  for (int i = n; i >= 0; i--) {
    cin >> k;
    poly.set(i, k);
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    ld l, h;
    cin >> l >> h;
    cout << poly.newton_method(l, h) << endl;
  }
}