上海市计算机学会2020年9月月赛（丙组）

 #include <iostream>

    
 #include <algorithm>
    
 #include <cmath>
    
 using namespace std;
    
 int ct, ct1, sum = 0;
    
 int main() {
    
 	int num, ct = 1, mx = -1;
    
 	cin >> num;
    
 	for (int i = num/2; i >= 1; --i) {
    
 		if (num%i == 0) {
    
 			ct1 = i;
    
 			ct = sqrt(i);
    
 			if ( pow(ct, 2) == ct1) {
    
 				sum = ct1;
    
 				mx = max(mx, sum);
    
 			}
    
 		}
    
 	}
    
 	printf("%d", mx);
    
 	return 0;
    
 }
    
    
    
    

 #include <iostream>

    
 #include <algorithm>
    
 using namespace std;
    
 string s;
    
 char b[10];
    
 int main() {
    
 	cin >> s;
    
 	b[1] = '1';
    
 	b[8] = '8';
    
 	b[0] = '0';
    
 	b[6] = '9';
    
 	b[9] = '6';
    
 	int len = s.size();
    
 	for (int i = 0; i < len; i++) {
    
 		if (s[i]=='2' || s[i]=='3' || s[i]=='4' || s[i]=='5' || s[i]=='7') {
    
 			printf("Not a strobogrammatic number");
    
 			return 0;
    
 		} else if (!(s[i]==b[s[len-i-1]-'0'])) {
    
 			printf("Not a strobogrammatic number");
    
 			return 0;
    
 		}
    
 	}
    
 	printf("Strobogrammatic number");
    
 	return 0;
    
 }
    
    
    
    

 #include <bits/stdc++.h>

    
 using namespace std;
    
 const int N = 1007;
    
 string s;
    
 int clct, stct;
    
 struct cour {
    
 	string name;
    
 	int capacity;
    
 } cour[N];
    
 int main() {
    
 	int m, n;
    
 	scanf("%d%d", &m, &n);
    
 	for (int i = 1; i <= m; i++)
    
 		cin >> cour[i].name >> cour[i].capacity;
    
 	map<string, int> ct;
    
 	for (int i = 1; i <= n; i++) {
    
 		cin >> s;
    
 		ct[s]++;
    
 	}
    
 	for (int i = 1; i <= m; i++) {
    
 		if (ct[cour[i].name]*2 < cour[i].capacity) {
    
 			clct++;
    
 			stct += ct[cour[i].name];
    
 		} else if (ct[cour[i].name] > cour[i].capacity)
    
 			stct += ct[cour[i].name] - cour[i].capacity;
    
 	}
    
 	cout << clct << endl << stct;
    
 	return 0;
    
 }
    
    
    
    

 #include <iostream>

    
 #include <algorithm>
    
 using namespace std;
    
 string s;
    
 int main() {
    
 	cin >> s;
    
 	int len = s.size();
    
 	for (int i = 0; i < len-1; i++) {
    
 		if (s[i]==s[i+1] || s[i]==s[i+2]) {
    
 			cout << "Not a random string";
    
 			return 0;
    
 		}
    
 	}
    
 	cout << "Random string";
    
 	return 0;
    
 }
    
    
    
    

 #include <iostream>

    
 #include <algorithm>
    
 using namespace std;
    
 const int mod = 1e9 + 9, N = 1e6 + 7;
    
 int dp[N];
    
 int main() {
    
 	int n;
    
 	scanf("%d", &n);
    
 	dp[0] = 1;
    
 	dp[1] = 2;
    
 	for (int i = 2; i <= n; i++)
    
 		dp[i] = (dp[i-1] + dp[i-2]) % mod;
    
 	printf("%d\n", dp[n]);
    
 	return 0;
    
 }