d:\Documents\C++\ClassMax.cpp
unknown
c_cpp
2 years ago
23 kB
12
Indexable
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define faster() ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
class INT{
public:
void CPP0101();
void CPP0103();
void CPP0104();
void CPP0105();
void CPP0106();
void CPP0109();
void CPP0111();
void CPP0112();
void CPP0113();
void CPP0115();
void CPP0117();
void CPP0121();
void CPP0122();
void CPP0123();
void CPP0124();
void CPP0125();
void CPP0126();
void CPP0127();
void CPP0130();
void CPP0132();
void CPP0133();
void CPP0134();
void CPP0143();
void CPP0152();
void CPP0153();
void CPP0154();
void CPP0108();
void CPP0118();
void CPP0120();
void CPP0173();
void CPP0119();
};
void INT::CPP0101(){
int t; cin >> t;
while(t--){
int n; cin >> n;
cout << 1ll * n * (n + 1) / 2 << endl;
}
}
void INT::CPP0103(){
int n; cin >> n;
double s = 0;
for(int i = 1; i <= n; i++){
s += (float)1/i;
}
cout << fixed << setprecision(4) << s << endl;
}
ll gt(int x){
ll gt = 1ll;
while(x > 1){
gt *= x;
x--;
}
return gt;
}
void INT::CPP0104(){
int n; cin >> n;
long long s = 0;
for(int i = 1; i <= n; i++){
s += gt(i);
}
cout << s << endl;
}
bool locphat(int n){
while(n > 0){
int a = n % 10;
if(a != 8 && a != 0 && a != 6) return false;
n /= 10;
}
return true;
}
void INT::CPP0105(){
int t; cin >> t;
while(t--){
int n; cin >> n;
if(locphat(n)) cout << "YES\n";
else cout << "NO\n";
}
}
bool tn(string s){
int l = 0, r = s.length() - 1;
while(l <= r){
if(s[l] != s[r]) return false;
l++; r--;
}
return true;
}
void INT::CPP0106(){
int t; cin >> t;
while(t--){
string s; cin >> s;
if(tn(s)) cout << "YES\n";
else cout << "NO\n";
}
}
bool socb(int x){
int cntc = 0, cntl = 0;
while(x > 0){
int a = x%10;
if(a % 2 == 1) cntl++;
else cntc++;
x/=10;
}
if(cntc == cntl) return true;
return false;
}
void INT::CPP0109(){
int n; cin >> n;
int cnt = 0;
int l = pow(10,n-1), r = pow(10,n);
for(int i = l; i < r; i++){
if(socb(i)){
cout << i << " ";
cnt++;
}
if(cnt == 10){
cout << endl;
cnt = 0;
}
}
}
bool solk(string s){
for(int i = 1; i < s.length(); i++){
if(abs((s[i] - '0') - (s[i - 1] - '0')) != 1) return false;
}
return true;
}
void INT::CPP0111(){
int t; cin >> t;
cin.ignore();
while(t--){
string s;
cin >> s;
if(solk(s)) cout << "YES\n";
else cout << "NO\n";
}
}
void INT::CPP0112(){
int t; cin >> t;
cin.ignore();
while(t--){
double xA, yA, xB, yB;
cin >> xA >> yA >> xB >> yB;
double d = sqrt(pow(xA - xB,2) + pow(yA-yB,2));
cout << fixed << setprecision(4) << d << endl;
}
}
void INT::CPP0113(){
int t; cin >> t;
while(t--){
int x; cin >> x;
if(x % 100 == 86) cout << "1\n";
else cout << "0\n";
}
}
void solve(int n){
for(int i = 2; i <= sqrt(n); i++){
int cnt = 0;
if(n % i == 0){
cout << i << " ";
while(n % i == 0){
cnt++;
n /= i;
}
cout << cnt << " ";
}
}
if(n != 1) cout << n << " 1";
}
void INT::CPP0115(){
int t; cin >> t;
while(t--){
int n; cin >> n;
solve(n);
cout << endl;
}
}
int tongcs(int n){
int sum = 0;
while(n > 0){
sum += n%10;
n/=10;
}
return sum;
}
void INT::CPP0117(){
int t; cin >> t;
while(t--){
int n; cin >> n;
while(n >= 10){
n = tongcs(n);
}
cout << n << endl;
}
}
ll gcd(ll a, ll b){
if(b == 0) return a;
return gcd(b, a%b);
}
ll lcm(ll a, ll b){
return a / gcd(a, b) * b;
}
void INT::CPP0121(){
int t; cin >> t;
while(t--){
ll a, b;
cin >> a >> b;
cout << lcm(a, b) << " " << gcd(a, b) << endl;
}
}
void INT::CPP0122(){
int t; cin >> t;
while(t--){
ll n; cin >> n;
ll bcn = 1;
for(int i = 1; i <= n; i++){
bcn = lcm(i, bcn);
}
cout << bcn << endl;
}
}
bool nt(ll n){
if(n < 2) return false;
for(int i = 2; i <= sqrt(n); i++){
if(n%i == 0) return false;
}
return true;
}
void INT::CPP0123(){
ll n; cin >> n;
if(nt(n)) cout << "YES\n";
else cout << "NO\n";
}
void solve2(int n){
for(int i = 2; i <= sqrt(n); i++){
int cnt = 0;
if(n % i == 0){
cout << i << " ";
while(n % i == 0){
cnt++;
n /= i;
}
cout << cnt << endl;
}
}
if(n != 1) cout << n << " 1";
}
void INT::CPP0124(){
int n; cin >> n;
solve2(n);
cout << endl;
}
void INT::CPP0125(){
int a, b;
cin >> a >> b;
int cnt = 0;
if(a > b){
int tmp = a;
a = b;
b = tmp;
}
for(int i = a; i <= b; i++){
if(nt(i)){
cout << i << " ";
}
}
}
void INT::CPP0126(){
int t; cin >> t;
while(t--){
int a, b;
cin >> a >> b;
int cnt = 0;
if(a > b){
int tmp = a;
a = b;
b = tmp;
}
for(int i = a; i <= b; i++){
if(nt(i)){
cout << i << " ";
}
}
cout << endl;
}
}
int prime[1000001];
void sieve(){
for(int i = 0; i <= 1000000; i++){
prime[i] = 1;
}
prime[0] = prime[1] = 0;
for(int i = 2; i <= 1000; i++){
if(prime[i]){
for(int j = i*i; j <= 1000000; j += i){
prime[j] = 0;
}
}
}
}
void INT::CPP0127(){
sieve();
int t; cin >> t;
while(t--){
int n; cin >> n;
int ok = 1;
for(int i = 0, j = n; i <= j;){
if(prime[i] && prime[j]){
if(i + j == n){
cout << i << " " << j << endl;
ok = 0;
break;
}
}
i++; j--;
}
if(ok) cout << "-1\n";
}
}
void solve3(ll n){
for(int i = 2; i <= sqrt(n); i++){
while(n % i == 0){
cout << i << " ";
n /= i;
}
}
if(n != 1) cout << n;
}
void INT::CPP0130(){
int t; cin >> t;
while(t--){
ll n; cin >> n;
solve3(n);
cout << endl;
}
}
ll solve4(ll n){
ll res;
for(int i = 2; i <= sqrt(n); i++){
while(n % i == 0){
res = i;
n/= i;
}
}
if(n > 1) res = n;
return res;
}
void INT::CPP0132(){
int t; cin >> t;
while(t--){
ll n; cin >> n;
cout << solve4(n) << endl;
}
}
void INT::CPP0133(){
int t; cin >> t;
while(t--){
int n; cin >> n;
for(int i = 2; i <= n; i++){
if(nt(i)){
cout << i << " ";
}
}
cout << endl;
}
}
void solve5(int n, int k){
int cnt = 0;
for(int i = 2; i <= sqrt(n); i++){
while(n % i == 0){
cnt++;
if(cnt == k){
cout << i << endl;
break;
}
n/=i;
}
}
if(n != 1){
cnt++;
if(cnt == k){
cout << n << endl;
}
}
if(cnt < k) cout << "-1\n";
}
void INT::CPP0134(){
int t; cin >> t;
while(t--){
int n, k; cin >> n >> k;
solve5(n,k);
}
}
ll f[100];
void fibo(){
f[1] = 1; f[2] = 1;
for(int i = 3; i < 93; i++){
f[i] = f[i - 1] + f[i - 2];
}
}
void INT::CPP0143(){
int t; cin >> t;
fibo();
while(t--){
int n; cin >> n;
cout << f[n] << endl;
}
}
void INT::CPP0152(){
int t; cin >> t;
while(t--){
int a, m;
cin >> a >> m;
int ok = 1;
for(int i = 0; i < m; i++){
if(a * i % m == 1){
cout << i << endl;
ok = 0;
break;
}
}
if(ok) cout << "-1\n";
}
}
void INT::CPP0153(){
int t;
cin >> t;
while(t--){
ll n, k;
cin >> n >> k;
int S = 0;
for(int i = 1; i <= n; i++){
S += i % k;
}
cout << S << endl;
}
}
void INT::CPP0154(){
int t;
cin >> t;
while(t--){
ll n, k;
cin >> n >> k;
int S = 0;
for(int i = 1; i <= n; i++){
S += i % k;
}
if(S == k) cout << "1\n";
else cout << "0\n";
}
}
bool sot(int n){
int c = n%10;
n/=10;
if(c > n%10)
while(n > 9){
int tmp = n%10;
if(tmp <= (n/10)%10) return false;
n/=10;
}
else if(c < n%10)
while(n > 9){
int tmp = n%10;
if(tmp >= (n/10)%10) return false;
n/=10;
}
else return false;
return true;
}
void INT::CPP0108(){
int t; cin >> t;
while(t--){
int n; cin >> n;
int cnt = 0;
int a = pow(10, n-1), b = pow(10, n);
for(int i = a; i < b; i++){
if(sot(i) && nt(i)){
cnt++;
}
}
cout << cnt << endl;
}
}
bool sosp(int n){
int cnt = 0;
for(int i = 2; i <= sqrt(n); i++){
int idx = 0;
while(n%i == 0){
idx++;
n/=i;
}
if(idx > 1) return false;
if(idx == 1) cnt++;
}
if(n != 1) cnt++;
return cnt == 3;
}
void INT::CPP0118(){
int t; cin >> t;
while(t--){
int n; cin >> n;
if(sosp(n)) cout << "1\n";
else cout << "0\n";
}
}
void INT::CPP0120(){
int t; cin >> t;
while(t--){
int m, n, a, b;
cin >> m >> n >> a >> b;
int cnt = 0;
for(int i = m; i <= n; i++){
if(i % a == 0 || i%b == 0) cnt++;
}
cout << cnt << endl;
}
}
ll solve6(int x, int y, int z, int n){
ll tmp = lcm(lcm(x,y),z);
ll idx = (ll)pow(10, n - 1);
ll res = (idx + tmp - 1)/ tmp * tmp;
if(res < (ll)pow(10, n)) return res;
else return -1;
}
void INT::CPP0173(){
int t; cin >> t;
while(t--){
int x, y, z, n;
cin >> x >> y >> z >> n;
cout << solve6(x, y, z, n) << endl;
}
}
void INT::CPP0119(){
int t;
cin >> t;
while(t--){
int n; cin >> n;
int cnt = 0;
for(int i = 1; i <= sqrt(n); i++){
if(n % i == 0){
if(i % 2 == 0) cnt++;
if(i != n/i && n/i % 2 == 0) cnt++;
}
}
cout << cnt << endl;
}
}
class STRING{
public:
void CPP0308();
void CPP0309();
void CPP0312();
void CPP0313();
void CPP0314();
void CPP0317();
void CPP0319();
void CPP0339();
void CPP0354();
void CPP0371();
void CPP0310();
void CPP0311();
void CPP0315();
void CPP0318();
void CPP0320();
void CPP0334();
void CPP0338();
void CPP0342();
void CPP0353();
void CPP0336();
void CPP0374();
void CPP0107();
void CPP0110();
};
void STRING::CPP0308(){
int t;
cin >> t;
while(t--){
string s;
cin >> s;
int cnt[100001]={0};
for(int i = 0; i < s.length(); i++){
cnt[(int)s[i]]++;
}
for(int i = 0; i < s.length(); i++){
if(cnt[(int) s[i]] == 1) cout << s[i];
}
cout << endl;
}
}
void STRING::CPP0309(){
int test;
cin >> test;
while(test--){
cin.ignore();
string s;
getline(cin, s);
int dem = 0;
for(int i = 0; i < s.length(); i++){
if(s[i] == ' ' || s[i] == '\n' || s[i] == '\t') dem++;
}
cout << dem + 1 << endl;
}
}
void STRING::CPP0312(){
int t; cin >> t;
while(t--){
string s;
cin >> s;
int k; cin >> k;
set <char> se;
for(int i = 0 ; i < s.size() ; i++){
se.insert(s[i]);
}
if(k >= (26 - se.size()) && s.size() >=26 ) cout <<"1"<<endl;
else cout <<"0"<< endl;
}
}
void STRING::CPP0313(){
string s;
getline(cin,s);
string s1; cin >> s1;
stringstream ss(s);
string x;
while(ss>>x){
if(x!=s1) cout << x <<' ';
}
}
void STRING::CPP0314(){
int t; cin >> t;
cin.ignore();
set <string> se;
while(t--){
string s;
getline(cin,s);
se.insert(s);
}
cout << se.size();
}
bool checkTN(string s){
int l = 0, r = s.length() - 1;
while(l <= r){
if(s[l] != s[r]) return false;
l++; r--;
}
return true;
}
bool check1(string s){
for(int i = 0; i < s.length(); i++){
if((s[i] - '0') % 2) return false;
}
return true;
}
void STRING::CPP0317(){
int t;
cin >> t;
while(t--){
string s;
cin >> s;
if(checkTN(s) && check1(s)) cout << "YES\n";
else cout << "NO\n";
}
}
void STRING::CPP0319(){
int m, s;
cin >> m >> s;
if(s > 9*m || (s == 0 && m > 1)){
cout << "-1 -1";
return;
}
int tmp = s;
int max[m] = {0}, min[m] = {0};
for(int i = 0; i < m; i++){
if(s >= 9){
max[i] = 9;
s -= 9;
}
else if(s != 0){
max[i] = s;
s = 0;
}
else break;
}
tmp--;
for(int i = m - 1; i >= 0; i--){
if(tmp >= 9){
min[i] = 9;
tmp -= 9;
}
else if(tmp != 0){
min[i] = tmp;
tmp = 0;
}
else break;
}
min[0] += 1;
for(int i = 0; i < m; i++) cout << min[i];
cout << " ";
for(int i = 0; i < m; i++) cout << max[i];
}
void STRING::CPP0339(){
int t;
cin >> t;
while(t--){
string s;
cin >> s;
int cnt = 0;
for(int i = 0; i < s.length(); i++){
for(int j = i; j < s.length(); j++){
if(s[i] == s[j]) cnt++;
}
}
cout << cnt << endl;
}
}
void STRING::CPP0354(){
int t; cin >> t;
while(t--){
string s; cin >> s;
int cnt =1;
for(int i = 0 ; i < s.size()-1 ; i++){
if(s[i] != s[i+1]){
cout << s[i] << cnt;
cnt = 1;
}
else if(s[i] == s[i+1])cnt++;
}
if(s[s.size()-2] == s[s.size()-1]) cout << s[s.size()-1] << cnt;
else cout << s[s.size()-1] << "1";
cout << endl;
}
}
void STRING::CPP0371(){
string s; cin >> s;
for(int i = 0 ; i < s.size() ; i++){
s[i]=tolower(s[i]);
if(s[i] != 'a' && s[i] != 'i' && s[i] != 'u' && s[i] != 'o' && s[i] != 'e' && s[i] != 'y')
cout << "." << s[i];
}
}
long long doi5(string s){
for(int i = 0; i < s.length(); i++){
if(s[i] == '6') s[i] = '5';
}
return stoll(s);
}
long long doi6(string s){
for(int i = 0; i < s.length(); i++){
if(s[i] == '5') s[i] = '6';
}
return stoll(s);
}
void STRING::CPP0310(){
int t; cin >> t;
cin.ignore();
while(t--){
string x1, x2;;
cin >> x1 >> x2;
long long min = doi5(x1) + doi5(x2);
long long max = doi6(x1) + doi6(x2);
cout << min << " " << max << endl;
}
}
void STRING::CPP0311(){
int t; cin >> t;
cin.ignore();
while(t--){
string s;
cin >> s;
map<char,int> mp;
int max_val = 0;
for(char x : s){
mp[x]++;
max_val = max(max_val,mp[x]);
}
if(s.length() - max_val >= max_val - 1){
cout << "1\n";
}
else cout << "0\n";
}
}
string test(string s) {
for (int i = s.length() - 1; i > 0; i--) {
if (s[i] < s[i - 1]) {
int x = i;
for (int j = i; j < s.length(); j++) {
if (s[j] > s[x] && s[j] < s[i - 1])
x = j;
}
swap(s[x], s[i-1]);
return s;
}
}
return "-1";
}
void STRING::CPP0315(){
int t; cin >> t;
while (t--) {
string s; cin >> s;
cout << test(s) << endl;
}
}
bool st(string s){
char tmp = s[5];
for(int i = 6; i < 11; i++){
if(s[i] != '.'){
if(s[i] <= tmp){
return false;
}
else tmp = s[i];
}
}
return true;
}
bool nq(string s){
for(int i = 6; i < 11; i++){
if(s[i]!=s[5]) return false;
}
return true;
}
bool tn2(string s){
if(s[9] != s[10]) return false;
for(int i = 6; i < 8; i++){
if(s[i] != s[5]) return false;
}
return true;
}
bool lp(string s){
for(int i = 5; i < 11; i++){
if(s[i] != '.'){
if(s[i] != '6' && s[i] != '8') return false;
}
}
return true;
}
void STRING::CPP0318(){
int t; cin >> t;
while(t--){
string s;
cin >>s ;
if(st(s) || nq(s) || tn2(s) || lp(s)){
cout << "YES\n";
}
else cout << "NO\n";
}
}
void STRING::CPP0320(){
int t; cin >> t;
cin.ignore();
while(t--){
string s;
cin >> s;
set<char> se;
int ok = 1;
for(int i = 0; i < s.length(); i++){
if(isdigit(s[i]) && s[0] != '0'){
se.insert(s[i]);
}
else{
cout << "INVALID\n";
ok = 0;
break;
}
}
if(ok){
if(se.size() < 10){
cout << "NO\n";
}
else cout << "YES\n";
}
}
}
void STRING::CPP0334(){
int t; cin >> t;
cin.ignore();
while(t--){
string s;
cin >> s;
int sum = 0, res = 0;
for(int i = 0; i < s.length(); i++){
if(isdigit(s[i])){
res = res*10 + (s[i] - '0');
}
else{
sum += res;
res = 0;
}
}
cout << sum + res << endl;
}
}
void STRING::CPP0338(){
faster();
int t; cin >> t;
while(t--){
string s;
int k;
cin >> s >> k;
set<char> se;
int cnt = 0;
for(int i = 0; i < s.length(); i++){
se.clear();
for(int j = i; j < s.length() ; j++){
se.insert(s[j]);
if(se.size() == k) cnt++;
else if(se.size() > k ) break;
}
}
cout << cnt << endl;
}
}
void STRING::CPP0342(){
int t; cin >> t;
while(t--){
map<int, int> mp;
set<char> x;
string s; cin >> s;
int sum = 0;
for(int i = 0; i < s.size(); i++){
if(isdigit(s[i])) sum+=s[i]-'0';
else if(isdigit(s[i])==0){
x.insert(s[i]);
mp[s[i]]++;
}
}
for(auto i : x){
while(mp[i]--) cout << i;
}
cout << sum << endl;
}
}
map<char, char> d;
void load() {
d['A'] = '2'; d['B'] = '2'; d['C'] = '2';
d['D'] = '3'; d['E'] = '3'; d['F'] = '3';
d['G'] = '4'; d['H'] = '4'; d['I'] = '4';
d['J'] = '5'; d['K'] = '5'; d['L'] = '5';
d['M'] = '6'; d['N'] = '6'; d['O'] = '6';
d['P'] = '7'; d['Q'] = '7'; d['R'] = '7'; d['S'] = '7';
d['T'] = '8'; d['U'] = '8'; d['V'] = '8';
d['W'] = '9'; d['X'] = '9'; d['Y'] = '9'; d['Z'] = '9';
}
bool check2(string s){
load();
int l = 0, r = s.length() - 1;
while(l <= r){
if(d[s[l]] != d[s[r]]) return false;
l++; r--;
}
return true;
}
void STRING::CPP0353(){
load();
int t; cin >> t;
while(t--){
string s;
cin >> s;
for(int i = 0; i < s.length(); i++){
s[i] = toupper(s[i]);
}
if(check2(s)) cout << "YES\n";
else cout << "NO\n";
}
}
void STRING::CPP0336(){
int t;
cin >> t;
while(t--){
string s1, s2;
cin >> s1 >> s2;
int cnt1[256] = {0}, cnt2[256] = {0};
for(char x : s2) cnt2[x]++;
int ans = INT_MAX, left = 0, cnt = 0, indx = -1;
for(int i = 0; i < s1.length(); i++){
cnt1[s1[i]]++;
if(cnt1[s1[i]] <= cnt2[s1[i]]) ++cnt;
if(cnt == s2.length()){
while(cnt1[s1[left]] > cnt2[s1[left]] || cnt2[s1[left]] == 0){
if(cnt1[s1[left]] > cnt2[s1[left]]) cnt1[s1[left]]--;
left++;
}
if(ans > i - left + 1){
ans = i - left + 1;
indx = left;
}
}
}
if(indx == -1) cout << "-1\n";
else cout << s1.substr(indx, ans) << endl;
}
}
void STRING::CPP0374(){
string s;
cin >> s;
int n = s.length();
int cnt = 0;
for(int i = 1; i < n - 1; i++){
if(s[i - 1] == 'A' && s[i] == 'B' && s[i + 1] == 'A'){
s[i] = 'A';
cnt++;
}
else if(s[i - 1] == 'B' && s[i] == 'A' && s[i + 1] == 'B'){
s[i] = 'B';
cnt++;
}
}
for(int i = 0; i < n - 1; i++){
if(s[i] != s[i+1]) cnt++;
}
if(s[n-1] == 'B' && s[n-2] == 'B') cnt++;
cout << cnt << endl;
}
void STRING::CPP0107(){
int t; cin >> t;
while(t--){
string M101 = "ABBADCCABDCCABD";
string M102 = "ACCABCDDBBCDDBB";
string a = "101";
string ma; cin >> ma;
char s[20];
int cnt = 0;
for(int i = 0; i < 15; i++){
cin >> s[i];
}
if(ma.compare(a) == 0)
for(int i = 0; i < 15; i++){
if(s[i] == M101[i]) cnt++;
}
else{
for(int i = 0; i < 15; i++){
if(s[i] == M102[i]) cnt++;
}
}
cout << fixed << setprecision(2) << 2.0*cnt/3 << endl;
}
}
void STRING::CPP0110(){
int t; cin >> t;
cin.ignore();
while(t--){
string s;
cin >> s;
int res;
for(int i = 0; i < s.length() - 2; i++){
if(s[i] - '0' == 0 && s[i+1] - '0' == 8 && s[i+2] - '0' == 4)
res = i;
}
for(int i = 0; i < res; i++){
cout << s[i];
}
for(int i = res + 3; i < s.length(); i++){
cout << s[i];
}
cout << endl;
}
}
int main(){
INT x;
//x.CPP0101();
STRING y;
y.CPP0374();
}Editor is loading...