PAT 刷题代码

//B1001
#include <iostream>
using namespace std;
int main(){

    int n;
    cin>>n;
    for (int i = 0; i<1000000000; i++){
        if (n == 1){
            cout<<'0'<<endl;
            return 0;
        }
        else{
            if(n%2 == 0){
                n = n * 0.5;
            }
            else{
                n = (3 * n+1)*0.5;
            };
            if (n==1){
                cout<<i+1<<endl;
                return 0;
            }
        }
    }
}

//B1002
# include <stdio.h>
# include <iostream>
# include <string>
using namespace std;

int main(){
    string n;
    cin>>n;
    int sum = 0;
    for (int i=0;i<int(n.size());i++){
        sum += n[i] - '0';
    }
//    cout<<sum;
    string sum1 = to_string(sum);
    for (int i = 0; i< int(sum1.size());i++){
        if (sum1[i] == '0') cout<<"ling";
        if (sum1[i] == '1') cout<<"yi";
        if (sum1[i] == '2') cout<<"er";
        if (sum1[i] == '3') cout<<"san";
        if (sum1[i] == '4') cout<<"si";
        if (sum1[i] == '5') cout<<"wu";
        if (sum1[i] == '6') cout<<"liu";
        if (sum1[i] == '7') cout<<"qi";
        if (sum1[i] == '8') cout<<"ba";
        if (sum1[i] == '9') cout<<"jiu";
        if (i != int(sum1.size())-1)  cout<<" ";
    }
    return 0;
}

//B1003
# include <stdio.h>
# include <iostream>
# include <string>
using namespace std;

int substr(string a){
    int pexist = 0,ppos = 0;
    for (int i = 0;i<a.size();i++){
        if (a[i] == 'P'){
            pexist = 1;
            ppos = i;
        }
        if (pexist == 1 && a[i] == 'T' && i > ppos+1){
            for (int j = 0;j<a.size();j++){
                if (a[j]!= 'P' && a[j]!= 'A' && a[j]!= 'T'){
                    return 0;
                }
            }
            return 1;
        }
    }
    return 0;
}

int judge(string n){
    if (substr(n) == 1){
        int ppos = n.find('P');
        int tpos = n.find('T');
//        cout<<ppos<<' '<<tpos-ppos-1<<' '<<n.size()-tpos-1<<' ';
        if (ppos*(tpos-ppos-1)==n.size()-tpos-1){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    else{
        cout<<"NO"<<endl;
    }
    return 0;
}

int main(){
    int num;
    cin>>num;
    string n[num];
    for (int i = 0;i<num;i++){
        cin>>n[i];
    }

    for (int i = 0;i<num;i++){
        judge(n[i]);
    }


}

//B1003
# include <stdio.h>
# include <iostream>
# include <string>
using namespace std;


int main(){
    int num;
    cin>>num;
    string n[num*2];
    int score[num];
    int count = 0;
    for (int i = 0;i<num*3;i++){
        if (i%3 == 2){
            cin>>score[(i-2)/3];
        }
        else{
            cin>>n[count++];
        }
    }

    int max,min,maxpos,minpos;
    max = min = score[0];
    maxpos = minpos = 0;
    for (int i = 0;i<num;i++){
        if (score[i]>max){
            max = score[i];
            maxpos = i;
        }
        if (score[i]<min){
            min = score[i];
            minpos = i;
        }
    }

    cout<<n[maxpos * 2]<<' '<<n[maxpos * 2+1]<<endl;
    cout<<n[minpos * 2]<<' '<<n[minpos * 2+1]<<endl;

}

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

int findanddel(int num[], int j,int n){
    for (int i = 0;i<n;i++){
        if (num[i] == j){
            num[i] = 1;
        }
    }
    return  0;
}

int main(){
    int n;
    cin>>n;
    int num[n];
    for (int i = 0;i<n;i++){
        cin>>num[i];
    }

    for (int i = 0;i<n;i++){
        int k = num[i];
        while(k!=1){
            if (k%2 == 0){
                k = k/2;
                findanddel(num,k,n);
            }
            else{
                k = (k*3+1)/2;
                findanddel(num,k,n);
            }
        }
    }
    sort(num,num + n);

    for (int i = n-1;i>=0;i--){
        if (num[i] == 1) break;
        else if (i!=n-1) cout<<' ';
        cout<<num[i];

    }
    return 0;
}

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

int main(){
    int n;
    cin>>n;
    int a[3];
    for(int i = 0;i<3;i++){
        a[i] = n%10;
        n =  n/10;
    }
    for (int i = 0; i<a[2]; i++){
        cout<<'B';
    }
    for (int i = 0; i<a[1]; i++){
        cout<<'S';
    }
    int count  = 0;
    for (int i = 0; i<a[0]; i++){
        cout<<++count;
    }
    return 0;
}

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

int min(int a,int b){
    if(a<b)return a;
    else return b;
}
int main(){
    int n;
    cin>>n;
    vector <int> su;
    su.push_back(2);
    for (int i = 2;i<n+1;i++){
        int judge = 1;
        for (int j = 0; j<su.size();j++){
            if (i%su[j] == 0){
                judge = 0;
            }
            if (su[j] > sqrt(n)) break;
        }
        if  (judge == 1){
            su.push_back(i);
        }

    }

//    for (int i = 0;i<su.size();i++){
//        cout<<su[i]<<' ';
//    }

    int count = 0;
    for (int i = 1;i<su.size();i++){
        if(su[i]>n)break;
        if(su[i]-su[i-1]==2){
            count++;
        }
    }
    cout<<count;
    return 0;
}

//B1008 我觉得题解的做法就是有病……
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;


int main(){
    int n,m;
    cin>>n>>m;
    int num[n];
    for (int i = 0;i<n;i++){
        cin>>num[i];
    }
    for (int i = 0;i<n;i++){
        cout<<num[(i-m+n*100)%n];
        if (i!=n-1) cout<<' ';
    }
    return 0;
}

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

int main(){
    string str;
    getline(cin,str);
//    cout<<str;
    str = str+" ";
    vector<string> strSplit;
    vector<char>s;
    for (int i  = 0;i<str.size()+1;i++){
//        for (int j =  0;j<s.size();j++){
//            cout<<s[j];
//        }
        if  (str[i]!=' '&&i!=str.size()) s.push_back(str[i]);
        else {
            string a;
            for (int j =  0;j<s.size();j++){
                a = a+s[j];
//                cout<<s[j];
            }
            s.clear();
            strSplit.push_back(a);
        }
    }

    for (int i = 1;i<strSplit.size();i++){
        if(i!=strSplit.size()-1) cout<<strSplit[strSplit.size()-i-1]<<" ";
        else cout<<strSplit[strSplit.size()-i-1];
    }

    return 0;
}

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

int main(){
//    cout<<"Enter Please"<<endl;
    int tmp;
    vector<int>num;
    vector<int>num2;
    while(cin>>tmp){
        if(tmp == 0) {
            cout<<"0 0";
            return 0;
        }
        num.push_back(tmp);
        cin>>tmp;
        num2.push_back(tmp);
        if(tmp == 0) break;

    }
//    cout<<num2.size()<<endl;
//    for(int i = 0;i<num.size();i++){
//        cout<<num[i];
//    }
//    cout<<'\n';
    for(int i = 0;i<int(num2.size());i++){
        if (num2[i] == 0 && i == 0) {
            cout<<"0 0";
            break;
        }
        if (num2[i]>0) cout<<num2[i]*num[i]<<' '<<num2[i]-1;
        if (i!=int(num2.size()-1) && num2[i+1]!=0) cout<<' ';
//        cout<<'E'<<num2[i];
    }
    return 0;
}

//B1011 大数相加u模板
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;

int cmp(string a, string b){
    if(a.size()>b.size()) return 1;
    else if(a.size()<b.size()) return -1;
    else {
        for (int i = 0;i<a.size();i++){
            if (a[i]!=b[i]){
                if (a[i]>b[i]) return 1;
                if (a[i]<b[i]) return -1;
            }
        }
        return 0;
    }
}

string add2(string a,string b){
    if (a == "0") return b;
    if (b == "0") return a;
    string c;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string a1(32-a.size(),'0');
    string b1(32-b.size(),'0');
    a = a + a1;
    b = b + b1;
    int jinwei = 0;
    for (int i = 0;i<32;i++){
        char tmp;
        tmp = a[i]+b[i]-48+jinwei;
        if (tmp>'9'){
            tmp -= 10;
            jinwei = 1;
        }
        else jinwei = 0;
        c += tmp;
    }
    reverse(c.begin(), c.end());
    int j = 0;
    string d;
    for(int i = 0;i<c.size();i++){
        if (c[i]!='0') j=1;
        if (j==1) d += c[i];
    }
    return d;
}

string abs(string a){

    if (a[0] != '-') return a;
    else {
        string b;
        for (int i = 1;i<a.size();i++){
            b += a[i];
        }
        return b;
    }

}


string sub2(string a,string b){
    string c;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string a1(32-a.size(),'0');
    string b1(32-b.size(),'0');
    a = a + a1;
    b = b + b1;
//    cout<<a<<' '<<b<<endl;
    int jinwei = 0;
    for (int i = 0;i<32;i++){
        char tmp;
        tmp = a[i]-b[i]+48-jinwei;
        if (tmp<'0'){
            tmp += 10;
            jinwei = 1;
        }
        else jinwei = 0;
        c += tmp;
    }
    reverse(c.begin(), c.end());
    int j = 0;
    string d;
    for(int i = 0;i<c.size();i++){
        if (c[i]!='0') j=1;
        if (j==1) d += c[i];
    }
    return d;
}


string sub(string a,string b){
    if (a== "0") {
        if (abs(b) == b) return "-"+abs(b);
        else return abs(b);

    }
    if (b == "0") return a;
    int big = cmp(abs(a), abs(b));
    if (big == 0) return "0";
    else if (big == 1){
        if (abs(a)==a && abs(b)==b) return sub2(a,b);
        else if (abs(a)!=a && abs(b)==b) return "-"+add2(abs(a),b);
        else if (abs(a)==a && abs(b)!=b) return add2(a,abs(b));
        else return "-"+sub2(abs(a),abs(b));
    }
    else {
        if (abs(a)==a && abs(b)==b) return "-"+sub2(b,a);
        else if (abs(a)!=a && abs(b)==b) return sub2(b,abs(a));
        else if (abs(a)==a && abs(b)!=b) return sub2(abs(b),a);
        else return sub2(abs(b),abs(a));

    }
    return "0";
}


string add(string a,string b){
    if (a[0] == '-' && b[0] == '-') return "-"+add2(abs(a), abs(b));
    else if (a[0] != '-' && b[0] == '-') return sub(a,abs(b));
    else if (a[0] == '-' && b[0] != '-') return sub(b,abs(a));
    else return add2(abs(a), abs(b));
}

string judge(string a,string b,string c){
//    cout<<add(a,b)<<endl;
    string result = sub(add(a,b),c);
//    cout<<result<<" ";
    if (result[0] == '-' || result == "0" ) return "false";
    else return "true";
//    return result;
}

string output(string a,string b,string c,int num){
    return "Case #" + to_string(num) + ": "+judge(a,b,c);
}

int main(){
//    cout<<"Enter Please"<<endl;
    int n;
    cin>>n;
    string a[n],b[n],c[n];
    if (n!=0){
        for (int i=0;i<n;i++){
            cin>>a[i]>>b[i]>>c[i];
        }
        for (int i=0;i<n;i++){
            cout<<output(a[i],b[i],c[i],i+1)<<endl;
        }
    }
    return 0;
}

int main1(){
    string a,b,c;
    cin>>a>>b>>c;
    string result = sub(add(a,b),c);
    cout<<result<<" "<<output(a,b,c,1)<<endl;
    return 0;
}

//B1012
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    cout<<"Enter Please"<<endl;
    int n;
    cin>>n;
    int num[n];
    for (int i = 0;i<n;i++){
        cin>>num[i];
    }
    int a1,a2,a3,a5;
    float a4 = 0.0;
    a1 = a2 = a3 = a5 =0;
    int count4 = 0;
    int count2 = 1;
    int judge2 = 0;
    for (int i = 0;i<n;i++){
        if (num[i] % 10 == 0) a1 += num[i];
        if (num[i] % 5 == 1) {
            judge2 = 1;
            a2 += count2 * num[i];
            count2 = count2 * (-1);
        }
        if (num[i] % 5 == 2) a3 += 1;
        if (num[i] % 5 == 3) {
            a4 += num[i];
            count4 +=1;
        }
        if (num[i] % 5 == 4) {
            if (a5<num[i]) a5 = num[i];
        }
    }
    a4 = a4/count4;
    string a11=a1>0?to_string(a1):"N";
    string a21=judge2 == 1?to_string(a2):"N";
    string a31=a3>0?to_string(a3):"N";
    string a51=a5>0?to_string(a5):"N";
//    int a11 = a1;
//    int a21 = a2;
//    int a31 = a3;
//    int a51 = a5;
    if (a4 >0){
        cout<<a11<<' '<<a21<<' '<<a31<<' '<<fixed<<setprecision(1)<<a4<<' '<<a51;
    }
    else{
        cout<<a11<<' '<<a21<<' '<<a31<<' '<<'N'<<' '<<a51;
    }

    return 0;
}

//B1013 朴素方法
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int m,n;
    cin>>m>>n;
    vector <int> su;
    su.push_back(2);
    int i = 1;
    while(su.size()<n+1){
        i++;
        int judge = 1;
        for (int j = 0; j<su.size();j++){
            if (i%su[j] == 0){
                judge = 0;
            }
            if (su[j] > sqrt(i)) break;
        }
        if  (judge == 1){
            su.push_back(i);
        }
    }
    for (int i = m-1;i<su.size()-1;i++){
        cout<<su[i];
        if ((i-m+2)%10 == 0 && i != su.size()-2)cout<<endl;
        else if (i != su.size()-2) cout<<' ';
        else break;
    }
    return 0;
}

//B1013 $ 1/7 格式！
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

const int MAXN=10000000;
int prime[MAXN];//保存素数
bool vis[MAXN] = {0};//初始化

int Prime(int n,int m)
{
    int cnt=0;
    for(int i=2;i<n;i++)
    {
        if(!vis[i])
            prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)//关键
                break;
        }
        if (cnt>m)break;
    }
    return cnt;//返回小于n的素数的个数
}

int main(){
    int m,n,count = 0;
    cin>>m>>n;
    Prime(10000000,n+5);
    for(int i = 0;count<n+2;i++){
        if(vis[i] == 0){
            if (count>m) {
                printf("%d",i);
                if ((count-m)%10 == 0)printf("\n");
                else if (count!=n+1)printf(" ");
            }
            count++;
        }
    }
    return 0;
}

//B1014/A1061
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

unsigned long int cmp(string a,string b){
    if (a.size()>b.size()) return b.size();
    else return a.size();
}
int main(){
    string a,b,c,d;
    cin>>a>>b>>c>>d;
    char day,hour;
    int minute = 0;
    int count = 0;

    for (int i = 0;i<cmp(a,b);i++){
        if (a[i] == b[i] && a[i]>='A' && a[i]<='G' && count == 0) {
            day = a[i];
            count++;
            continue;
        }
        if (a[i] == b[i] && a[i]>='A' && a[i]<='N' && count == 1) {
            hour = a[i];
            count++;
            break;
        }
        if (a[i] == b[i] && a[i]>='0' && a[i]<='9' && count == 1) {
            hour = a[i];
            count++;
            break;
        }
    }
    for (int i = 0;i<cmp(c,d);i++){
        if (c[i] == d[i] && c[i]>='A' && c[i]<='Z') {
            minute = i;
            break;
        }
        if (c[i] == d[i] && c[i]>='a' && c[i]<='z') {
            minute = i;
            break;
        }
    }

//    cout<<day<<hour<<minute<<endl;

    if (day == 'A') cout<<"MON ";
    if (day == 'B') cout<<"TUE ";
    if (day == 'C') cout<<"WED ";
    if (day == 'D') cout<<"THU ";
    if (day == 'E') cout<<"FRI ";
    if (day == 'F') cout<<"SAT ";
    if (day == 'G') cout<<"SUN ";
    if (hour >='A') cout<<hour-'A'+10<<':'<<setfill('0')<<setw(2)<<minute;
    else cout<<setfill('0')<<setw(2)<<hour<<':'<<setfill('0')<<setw(2)<<minute;
    return 0;
}

//B1015/A1062
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct{
    int id,d,c,sgn,total;
} student;

bool cmp(student a,student b)
{
    //'>'降序排序
    //'<'升序排序
    if(a.sgn!=b.sgn)return a.sgn<b.sgn;
    else if(a.total!=b.total)return a.total>b.total;
    else if(a.d!=b.d)return a.d>b.d;
    else return a.id<b.id;
    // 这里的if-else太妙了 //NOTE3
}
int main(){
    int num,l,h;
    cin>>num>>l>>h;
    student students[num];
    for (int i = 0;i<num;i++){
        cin>>students[i].id>>students[i].d>>students[i].c;
    }

    int failcount = 0;
    for (int i = 0;i<num;i++){
        students[i].total = students[i].d + students[i].c;
        if (students[i].d>=h && students[i].c>=h) students[i].sgn = 0;
        else if (students[i].d>=h && students[i].c<h && students[i].c>=l) {
            students[i].sgn = 1;}
        else if (students[i].c>=l && students[i].d>=l && students[i].d>=students[i].c) students[i].sgn = 2;
        else if (students[i].c>=l && students[i].d>=l) students[i].sgn = 3;
        else {
            students[i].sgn = 4;
            failcount ++;
        }
    }
    sort(students, students+num, cmp);
    student tmp;
    for (int j = 0;j<num;j++)
    {
        if (students[j].c == students[j+1].c && students[j].d == students[j+1].d && students[j].id > students[j+1].id ){
            tmp = students[j];
            students[j] = students[j+1];
            students[j+1] = tmp;
        }
    }
    cout<<num-failcount<<endl;
    for (int j = 0;j<num-failcount;j++)
    {
//        cout<<students[j].id<<" "<<students[j].d<<" "<<students[j].c<<" "<<students[j].sgn<<" "<<students[j].total<<endl;;
        cout<<students[j].id<<" "<<students[j].d<<" "<<students[j].c<<endl;;
    }
    return 0;
}

//B1017 $ 编译错误
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

struct bign{
    int len;
    int d[1000];
    bign(){
        len = 0;
        memset(d,0,sizeof(d));
    }
};

bign convert1(string n){
    bign a;
    for(int i = 0;i<n.size();i++){
        a.d[a.len++] = (int)(n[n.size()-1-i]-'0');
    }
    return a;
}

bign devide(bign a,int b,int &r){
    bign q;
    r = 0;
    q.len = a.len;
    for(int i = a.len-1;i>=0;i--){
        r = 10 * r + a.d[i];
        if (r<b) q.d[i] = 0;
        else {
            q.d[i] = r/b;
            r = r%b;
        }
    }
    while (q.len >= 2 && q.d[q.len-1] == 0){q.len--;}

    return q;
}

int main(){
    string n;
    cin>>n;
    int b,r=0;
    scanf("%d",&b);
    bign q = devide(convert1(n),b,r);
//    printf("%d\n",q.len);
    for(int i = 0;i<q.len;i++){
        printf("%d",q.d[q.len-1-i]);
    }
    printf(" %d",r);
    return 0;
}

//B1019/A1069 $6/7 直接输入6174的忘记考虑了
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    int a[4];
    int a1,a2,judge = 0;
    while((n!=6174 && n!= 0) || (n==6174 && judge == 0)){
        judge = 1;
        a[0] = n/1000;
        a[1] = (n-a[0]*1000)/100;
        a[2] = (n-a[0]*1000-a[1]*100)/10;
        a[3] = n%10;
        sort(a,a+4);
        a1 = a[3] + a[2] * 10 + a[1] * 100 + a[0] * 1000;
        a2 = a[0] + a[1] * 10 + a[2] * 100 + a[3] * 1000;
        n = a2-a1;
        printf("%04d - %04d = %04d\n",a2,a1,n);
    }
    return 0;
}

//B1020
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct{
    double amount,totalprice;
} moon;

bool cmp(moon a,moon b){
    return (a.totalprice/a.amount)>(b.totalprice/b.amount);
}

int main(){
    int n;
    double d,money;
    cin>>n>>d;
    vector<moon>mooncake;
    mooncake.resize(n);
    for(int i = 0;i<n;i++){scanf("%lf",&mooncake[i].amount);}
    for(int i = 0;i<n;i++){scanf("%lf",&mooncake[i].totalprice);}
    sort(mooncake.begin(),mooncake.end(),cmp);
    for(int i = 0;i<n;i++){
        if (d>mooncake[i].amount){d -=mooncake[i].amount;money+=mooncake[i].totalprice;}
        else{
            money+=mooncake[i].totalprice/mooncake[i].amount * d;
            break;
        }
    }
    printf("%.2lf",money);
    return 0;
}

//B1021
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    string k;
    cin>>k;
    int rst[10] = {};
    for(int i = 0;i<k.size();i++){
        rst[int(k[i]-'0')]++;
    }
    for(int i = 0;i<10;i++){
        if (rst[i]>0)cout<<i<<":"<<rst[i]<<endl;
    }
    return 0;
}

//B1022
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int a,b,c,d;
    vector<int>result;
    cin>>a>>b>>d;
    c = a + b;
    while (c/d > 0){
        result.push_back(c-d*(c/d));
        c = (c-c%d)/d;
    }
    result.push_back(c);
    for (int i = result.size()-1;i>-1;i--){
        cout<<result[i];
    }

    return 0;
}

//B1023
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int num[10];
    for(int i = 0;i<10;i++){scanf("%d",&num[i]);}
    for(int i = 1;i<10;i++){
        if (num[i]>0){cout<<i;num[i]-=1;break;}
    }
    for(int i = 0;i<10;i++){
        while(num[i]>0){cout<<i;num[i]-=1;}
    }
    return 0;
}

//B1024/A1073 这个是计算出来的，大数便不行了
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    double num[2];
    string input;
    cin>>input;
    int pose = 0;
    for(int i = 1;i<input.size();i++){
        if(input[i]=='E') {
            pose = i;
            break;
        }
    }
    num[0] = 10*(input[1]-'0');
    for(int i = 3;i<pose;i++){
        num[0]+=input[i]-'0';
        num[0] = num[0]*10;
    }

    long long a = (long long)num[0]/10;     //main part
    for(int i = pose+2;i<input.size();i++){
        num[1]+=input[i]-'0';
        num[1] = num[1]*10;
    }
    int b = (int)num[1]/10;   //^b
//    cout<<a<<' '<<b<<endl;
    if (input[0] == '-') cout<<'-';
    if (input[pose+1] == '-'){
        cout<<"0.";
        for(int i = 0;i<b-1;i++){cout<<'0';}
        cout<<a;}
    else{
        if (b>=(to_string(a).size())-1)
        cout<<fixed<<setprecision(0)<<a*pow(10, b-(to_string(a).size())+1);
        else{
            for(int i = 0;i<b+1;i++){
                cout<<to_string(a)[i];
            }
            cout<<'.';
            for(int i = b+1;i<to_string(a).size();i++){
                cout<<to_string(a)[i];
            }
        }
    }
    return 0;
}

//B1024/A1073 这个是字符串折腾出来的
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    double num[2];
    string input;
    cin>>input;
    int pose = 0;
    for(int i = 1;i<input.size();i++){
        if(input[i]=='E') {
            pose = i;
            break;
        }
    }
    vector<char>nums;
    nums.push_back(input[1]);
    for(int i = 3;i<pose;i++){
        nums.push_back(input[i]);
    }
    for(int i = pose+2;i<input.size();i++){
        num[1]+=input[i]-'0';
        num[1] = num[1]*10;
    }
    int b = (int)num[1]/10;   //^b
    if (input[0] == '-') cout<<'-';
    if (input[pose+1]=='+'){
        if (nums.size()<=b+1){  //这里“=”是大坑，否则会输出“35.”
            for(int i = 0;i<nums.size();i++){
                cout<<nums[i];
            }
            for(int i = 0;i<b+1-nums.size();i++){
                cout<<0;
            }
        }
        else{
            for(int i = 0;i<b+1;i++){
                cout<<nums[i];
            }
            cout<<'.';
            for(int i = b+1;i<nums.size();i++){
                cout<<nums[i];
            }
        }
    }
    else{
        cout<<"0.";
        for(int i = 0;i<b-1;i++){
            cout<<0;
        }
        for(int i = 0;i<nums.size();i++){
            cout<<nums[i];
        }
    }
    return 0;
}

//B1025/A1074 $ 4/7
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;

struct node{
    int key;
    int next,add;
};


int main(){
    int head,n,k;
    scanf("%d %d %d",&head,&n,&k);
    int key,add,next;
    node a[100010];

    for(int i = 0;i<n;i++){
        scanf("%d %d %d",&add,&key,&next);
        a[add].key = key;
        a[add].add = add;
        a[add].next = next;
    }

    vector <vector<int>> seq;
    int p = head;
    for(int i = 0;i<n && p!=-1 ;i++){   // 注意会有无效节点！
        vector <int> temp(2);
        seq.push_back(temp);
        seq[i][0] = a[p].key;
        seq[i][1] = a[p].add;
        p = a[p].next;
    }

    for (int i = 0;i<seq.size()-k+1;i+=k){ // 这个+1 影响了测试点1&2
        reverse(seq.begin()+i, seq.begin()+i+k);
    }

    for(int i = 0;i<seq.size()-1;i++){
        printf("%05d %d %05d\n",seq[i][1],seq[i][0],seq[i+1][1]);
    }
    int m = (int)seq.size();
    printf("%05d %d %d\n",seq[m-1][1],seq[m-1][0],-1);
    return 0;
}

//00100 6 5
//00000 4 99999
//00100 1 12309
//68237 6 -1
//33218 3 00000
//99999 5 68237
//12309 2 33218

//00000 6 3
//00000 1 11111
//11111 2 22222
//22222 3 -1
//33333 4 44444
//44444 5 55555
//55555 6 -1

//B1027
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    char a;
    cin>>n>>a;
    if (n == 1){
        cout<<a<<endl<<0;
        return 0;
    }
    int m = sqrt((n+1)/2);
    int left = n+1-2*m*m;
    for (int i = m;i>1;i--){
        for (int j = 0;j<m-i;j++){
            cout<<' ';
        }
        for (int j =0;j<2*i-1;j++){
            cout<<a;
        }
        cout<<endl;;
    }
    for (int j = 0;j<m-1;j++){
        cout<<' ';
    }
    cout<<a<<endl;
    for (int i = 2;i<m+1;i++){
        for (int j = 0;j<m-i;j++){
            cout<<' ';
        }
        for (int j =0;j<2*i-1;j++){
            cout<<a;
        }
        cout<<endl;;
    }
    cout<<left;
    return 0;
}

//B1028 TODO 4/5
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct{
    char name[20];
    int date;
} man;

bool cmp(man a,man b)
{
    return a.date<b.date;
}

int main(){
    int n;
    cin>>n;
    man people[n];
    int a,b,c;
    for (int i = 0;i<n;i++){
        scanf("%s %d/%d/%d" ,people[i].name,&a,&b,&c);
        people[i].date = a*10000+b*100+c;
    }
    sort(people, people+n,cmp);

//    for (int i = 0;i<n;i++){
//        cout<<people[i].name<<' '<<people[i].date<<endl;
//    }

    int max = 0,min = n-1;
    for(int i = 0;i<n;i++){
        if (i == 0) {
            if (people[0].date>18140905) max = 0;}
        else{
            if (people[i].date>18140905 && people[i-1].date<=18140905) max = i;     //测试点2
            if (people[i-1].date<=20140906 && people[i].date>20140906) min = i-1;   //测试点1
        }
    }
    cout<<min-max+1<<' '<<people[max].name<<' '<<people[min].name;
    return 0;
}

//B1029/A1084
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>  //strlen
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;


int main(){
    char a[1000],b[1000];
    int hashtable[128] = {};    // NOTE9 所有东西的初始化不能忘！
    scanf("%s %s",b,a);
    int lena = (int)strlen(a);
    //NOTE8 取char长度，要#include <cstring>
    int lenb = (int)strlen(b);
    for(int i = 0;i<lena;i++){
//        if (a[i] == '\0')break;
        if (a[i]>='A' && a[i]<='Z')hashtable[a[i]-'A']+=1;
        else if (a[i]>='a' && a[i]<='z')hashtable[a[i]-'a']+=1;
        else if (a[i]>='0' && a[i]<='9')hashtable[a[i]-'0'+26]+=1;
        else if (a[i]=='_')hashtable[36]+=1;
    }
    for(int i = 0;i<lenb;i++){
//        if (b[i] == '\0')break;
        int t = 0;
        if (b[i]>='A' && b[i]<='Z')t=b[i]-'A';
        else if (b[i]>='a' && b[i]<='z')t=b[i]-'a';
        else if (b[i]>='0' && b[i]<='9')t=b[i]-'0'+26;
        else if (b[i]=='_')t=36;
        if (hashtable[t]==0) {
            if (b[i]>='a' && b[i]<='z')cout<<(char)(b[i]-'a'+'A');
            else cout<<b[i];
            hashtable[t]+=1;}
    }
    return 0;
}

//B1030/A1085 二分算法
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n,p,max = 0,tmp = 1;
    long long maxnum = 0;
    cin>>n>>p;
    vector<long long>a;
    a.resize(n);
    for(int i = 0;i<n;i++){scanf("%lld",&a[i]);}
    sort(a.begin(),a.end());
    for(int i = 0;i<n;i++){
        maxnum = a[i] * p;
        tmp = (int)(upper_bound(a.begin()+i+1, a.end(), (long long)a[i] * p) - a.begin() - i);
        if (max < tmp){
            max = tmp;
        }
    }
    cout<<max;
    return 0;
}

//B1030/A1085 TwoPointer
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n,p,max = 1;
    cin>>n>>p;
    vector<long long>a;
    a.resize(n);
    for(int i = 0;i<n;i++){scanf("%lld",&a[i]);}
    sort(a.begin(),a.end());
    int maxpos = 0;
    for(int i = 0;i<n;i++){
        while(a[maxpos]<=(long long)a[i]*p && maxpos<n){
            if(maxpos>=n)break;
            if(maxpos-i+1>=max)max = maxpos - i+1;
            maxpos++;
        }
    }
    cout<<max;
    return 0;
}

//B1031
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    int judge = 0;
    cin>>n;
    const int num = n;
    int weight[17] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
    char id[num][19];    //NOTE2
    for(int i = 0;i<num;i++){
        scanf("%s",id[i]);
        id[i][18] = '0';
    }
    for(int i = 0;i<n;i++){
        int sum = 0;
        for(int j = 0;j<17;j++){
            if (id[i][j]>='0'&& id[i][j]<='9'){
                sum += weight[j]*(int)(id[i][j]-'0');
            }
            else {
                id[i][18] = '1';
                break;
            }
        }
//        cout<<i<<"sum="<<sum<<endl;
        if (   (sum%11 == 0&&id[i][17] == '1' )
            || (sum%11 == 1&&id[i][17] == '0' )
            || (sum%11 == 2&&id[i][17] == 'X' )
            || (sum%11 == 3&&id[i][17] == '9' )
            || (sum%11 == 4&&id[i][17] == '8' )
            || (sum%11 == 5&&id[i][17] == '7' )
            || (sum%11 == 6&&id[i][17] == '6' )
            || (sum%11 == 7&&id[i][17] == '5' )
            || (sum%11 == 8&&id[i][17] == '4' )
            || (sum%11 == 9&&id[i][17] == '3' )
            || (sum%11 == 10&&id[i][17] == '2' )
            )
        {
//            cout<<sum%11<<' '<<id[i][17]<<endl;;
            continue;}
        else {
            id[i][18] = '1';
        }
    }
    for(int i = 0;i<num;i++){
        if (id[i][18]=='1') {
            judge = 1;
            for (int j=0;j<18;j++){
                cout<<id[i][j];
            }
            cout<<endl;
        }
        else continue;
    }
    if (judge == 0) {cout<<"All passed";return 0;}
    else return 0;
}

//B1032
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[100000] = {};
    int b,c;
    for (int i = 0;i<n;i++){
        cin>>b>>c;
        a[b]+=c;
    }
    int max = 0,pos = 0;
    for (int i = 0;i<100000;i++){
        if(max<a[i]) {
            max = a[i];
            pos = i;
        }
    }
    cout<<pos<<' '<<a[pos];
    return 0;
}

//B1033 TODO 3/5
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>  //strlen
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    char a[1000],b[1000];
    bool hashtable[128] = {0};
    hashtable[50]=false;
    scanf("%s %s",a,b);
    int lena = (int)strlen(a);
    int lenb = (int)strlen(b);
    for(int i = 0;i<lena;i++){
        if (a[i]>='A' && a[i]<='Z'){
            hashtable[a[i]-'A']=true;}
        else if (a[i]>='a' && a[i]<='z')hashtable[a[i]-'a']=true;
        else if (a[i]>='0' && a[i]<='9')hashtable[a[i]-'0'+26]=true;
        else if (a[i]=='_')hashtable[36]=true;
        else if (a[i]==',')hashtable[37]=true;
        else if (a[i]=='.')hashtable[38]=true;
        else if (a[i]=='-')hashtable[39]=true;
        else if (a[i]=='+')hashtable[40]=true;
    }
    for(int i = 0;i<lenb;i++){
        int t = 0,shift = 1;
        if (b[i]>='A' && b[i]<='Z'){t=b[i]-'A';shift = 0;}
        else if (b[i]>='a' && b[i]<='z')t=b[i]-'a';
        else if (b[i]>='0' && b[i]<='9')t=b[i]-'0'+26;
        else if (b[i]=='_')t=36;
        else if (b[i]==',')t=37;
        else if (b[i]=='.')t=38;
        else if (b[i]=='-')t=39;
        else if (b[i]=='+')t=40;
//        cout<<t<<' '<<hashtable[t]<<' '<<shift<<' '<<hashtable[40]<<' ';
//        cout<<b[i]<<endl;
        if (hashtable[t]==false) {
            if (hashtable[40] == true && b[i]>='A' && b[i]<='Z'){
                continue;
            }
            else cout<<b[i];
        }
    }
    return 0;
}

//B1034/A1088 $ 2/4 分数四则运算模板
// 测试点2  是 long long 的原因
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
typedef long long LL;
using namespace std;

typedef struct{
    LL up,down;
} fractionnum;

LL maxfactor(LL a,LL b){
    a = abs(a); // !!
    if (b!= 0) return maxfactor(b, a%b);
    else return a;
}

fractionnum yue(fractionnum a){
    if (a.up == 0){a.down = 1;return a;}
    if (a.down < 0){a.down = -a.down;a.up = -a.up;}

    long long max = maxfactor(a.down, a.up);
    if (max == a.down){
        a.up = a.up/a.down;
        a.down = 1;
    }
    else if (max > 1){
        a.up = a.up/max;
        a.down = a.down/max;
    }
    return a;
}

fractionnum pluss(fractionnum a,fractionnum b){
    fractionnum temp;
    temp.down = a.down * b.down;
    temp.up = a.up * b.down + a.down * b.up;
    return yue(temp);
}

fractionnum minuss(fractionnum a,fractionnum b){
    b.up = -1 * b.up;
    return pluss(a,b);
}

fractionnum multi(fractionnum a,fractionnum b){
    fractionnum temp;
    temp.down = a.down * b.down;
    temp.up = a.up * b.up;
    return yue(temp);
}

fractionnum devide(fractionnum a,fractionnum b){
    fractionnum temp;
    temp.down = a.down * b.up;
    temp.up = a.up * b.down;
    return yue(temp);
}

void printpartition(fractionnum a){
    a = yue(a);
    if (a.up<0)printf("(-");

    if (maxfactor(abs(a.down), a.up) == a.down){
        printf("%lld",abs(a.up)/a.down);
    }
    else{
        if (abs(a.up)>a.down){
            printf("%lld %lld/%lld",abs(a.up)/a.down,abs(a.up) % a.down,a.down);}
        else {printf("%lld/%lld",abs(a.up),a.down);}
    }
    if (a.up<0)printf(")");
}

int main(){
    fractionnum a,b;
    scanf("%lld/%lld",&a.up,&a.down);
    scanf("%lld/%lld",&b.up,&b.down);
    printpartition(a);printf(" + ");
    printpartition(b);printf(" = ");
    printpartition(pluss(a, b));printf("\n");
    printpartition(a);printf(" - ");
    printpartition(b);printf(" = ");
    printpartition(minuss(a, b));printf("\n");
    printpartition(a);printf(" * ");
    printpartition(b);printf(" = ");
    printpartition(multi(a, b));printf("\n");
    printpartition(a);printf(" / ");
    printpartition(b);printf(" = ");
    if (b.up == 0){printf("Inf\n");}
    else {printpartition(devide(a, b));printf("\n");}// 这里忘记加大括号！测试点 3 格式错误
    return 0;
}

//B1035/A1089
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int>a;a.resize(n);
    vector<int>b;b.resize(n);
    int bpos = 0,judge = 0;
    for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
    for(int i = 0;i<n;i++){
        scanf("%d",&b[i]);
        if(judge == 0 && b[i]<b[i-1]){bpos = i;judge = 1;}
    }
    judge = 0;
    for(int i = bpos+1;i<n;i++){
        if(b[i]!=a[i]){judge = 1;break;}
    }
    if (judge == 1){
        cout<<"Merge Sort\n";
        int key = 0;
        for(int seg = 2;seg<2*n;seg=seg*2){
            for(int i = 0;i<n;i+=seg){
                if (i+seg<n) sort(a.begin()+i,a.begin()+i+seg);
                else sort(a.begin()+i,a.end());
            }
            if (key == 1){
                for(int i = 0;i<n;i++){
                    cout<<a[i];
                    if (i!=n-1)cout<<' ';
                }
                break;
            }
            judge = 1;
            for(int i = 0;i<n;i++){if(a[i]!=b[i]){judge = 0;break;}}
            if (judge == 1)key = 1;
        }
    }
    else {
        cout<<"Insertion Sort\n";
        for(int i = 0;i<bpos;i++){
            if (b[i]>b[bpos] && judge == 0){
                cout<<b[bpos]<<' ';
                judge +=1;}
            cout<<b[i]<<' ';
        }
        for(int i = bpos+1;i<n;i++){
            cout<<b[i];
            if(i!=n-1)cout<<' ';
        }
    }
    return 0;
}

//B1036
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    char a;
    cin>>n>>a;
    for (int i =0;i<n;i++){
        cout<<a;
    }
    cout<<endl;
    int t;
    if (n%2 == 0) t = n/2;
    else t = n/2+1;
    for (int i =0;i<t-2;i++){
        cout<<a;
        for (int j =0;j<n-2;j++){
            cout<<' ';
        }
        cout<<a<<endl;;
    }
    for (int i =0;i<n;i++){
        cout<<a;
    }
    cout<<endl;

    return 0;
}

//B1037
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int g1,s1,k1,g2,s2,k2,g3,s3,k3;
    scanf("%d.%d.%d %d.%d.%d",&g1,&s1,&k1,&g2,&s2,&k2);
    int sum1,sum2,diff;
    sum1 = g1 * 17 * 29 + s1 * 29 + k1;
    sum2 = g2 * 17 * 29 + s2 * 29 + k2;
    if (sum1>sum2){
        diff = sum1-sum2;
        g3 = diff/(17*29);
        s3 = (diff-g3*17*29)/29;
        k3 = diff - g3 * 17 * 29 - s3 * 29;
        printf("-%d.%d.%d",g3,s3,k3);
    }
    else if (sum1<sum2){
        diff = sum2-sum1;
        g3 = diff/(17*29);
        s3 = (diff-g3*17*29)/29;
        k3 = diff - g3 * 17 * 29 - s3 * 29;
        printf("%d.%d.%d",g3,s3,k3);
    }
    else{
        cout<<"0.0.0";
        return 0;
    }

    return 0;
}

//B1038
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>  //strlen
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n,k;
    int hundred[101] = {};
    scanf("%d",&n);
    int score[n];
    for(int i = 0;i<n;i++){
        scanf("%d",&score[i]);
        hundred[score[i]]+=1;}
    scanf("%d",&k);
    int query[k];
    for(int i = 0;i<k;i++){scanf("%d",&query[i]);}
    for(int i = 0;i<k;i++){
        printf("%d",hundred[query[i]]);
        if (i<k-1)cout<<' ';
    }
    return 0;
}

//B1039/A1092
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    char a[1000],b[1000];
    scanf("%s %s",a,b);
    int hash[128] = {};
    int lena = (int)strlen(a);
    int lenb = (int)strlen(b);
    for(int i = 0;i<lena;i++) hash[(int)a[i]]+=1;
    int judge = 1,left = 0;
    for(int i = 0;i<lenb;i++){
        hash[(int)b[i]]-=1;
        if (hash[(int)b[i]]<0) judge = 0;
    }
    int num = 0;
    if (judge == 0){
        cout<<"No ";
        for(int i = 0;i<128;i++){
            if(hash[i] < 0)num += hash[i];
        }
    }
    else{
        cout<<"Yes ";
        for(int i = 0;i<128;i++){
            if(hash[i] > 0)num += hash[i];
        }
    }
    cout<<abs(num);
    return 0;
}

//B1040/A1093
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    string a;
    cin>>a;
    vector<int>p;p.resize(a.size());
    vector<int>t;t.resize(a.size());
    int countp=0,countt = 0;
    long long count=0;;
    for(int i = 0;i<a.size();i++){
        if(a[i] == 'P')countp+=1;
        if(a[i] == 'A')p[i] = countp;
    }
    for(int i = a.size()-1;i>=0;i--){
        if(a[i] == 'T')countt+=1;
        if(a[i] == 'A')t[i] = countt;
    }
    for(int i = 0;i<a.size();i++){
        if(a[i] == 'A')count+=(long long)p[i]*t[i];
    }
    cout<<count%1000000007;
    return 0;
}

//B1041
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n,m;
//    cout<<123;
    cin>>n;
    long long a[n][3];
    for (int i = 0;i<n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    cin>>m;
    int b[m];
    for (int i = 0;i<m;i++){
        cin>>b[i];
    }

    for(int i = 0;i<m;i++){
        for(int j = 0;j<n;j++){
            if (b[i] == a[j][1]){
                cout<<a[j][0]<<' '<<a[j][2]<<endl;
                break;
            }
        }
    }
    return 0;
}

//B1042
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    char a[1000];
    cin.getline(a,1000);
    int hash[27] = {};
    int lena = (int)strlen(a);
    for(int i = 0;i<lena;i++) {
        if (a[i]>='a'&&a[i]<='z') hash[(int)(a[i]-'a')]+=1;
        if (a[i]>='A'&&a[i]<='Z') hash[(int)(a[i]-'A')]+=1;
    }
    int max = 0;
    char maxchar;
    for(int i = 0;i<27;i++){

        if(hash[i] > max) {max = hash[i];maxchar = (char)(i+'a');}
    }
    cout<<maxchar<<' ';
    cout<<max;
    return 0;
}

//B1043 4/5错误答案 只需要处理 PATest 6个字母就好了啊！！(其实错误是因为没审题，应该分配10000…)
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    char a[1000];
    cin.getline(a,1000);
    int hash[52] = {};
    int lena = (int)strlen(a);
    for(int i = 0;i<lena;i++) {
        if (a[i]>='a'&&a[i]<='z') hash[(int)(a[i]-'a')]+=1;
        if (a[i]>='A'&&a[i]<='Z') hash[(int)(a[i]-'A'+26)]+=1;
    }

    for(int i = 0;i<lena;i++) {
        int judge = 0;
        if (hash['P'-'A'+26]>0) {cout<<'P';hash['P'-'A'+26]-=1;judge = 1;}
        if (hash['A'-'A'+26]>0) {cout<<'A';hash['A'-'A'+26]-=1;judge = 1;}
        if (hash['T'-'A'+26]>0) {cout<<'T';hash['T'-'A'+26]-=1;judge = 1;}
        if (hash['e'-'a']>0) {cout<<'e';hash['e'-'a']-=1;judge = 1;}
        if (hash['s'-'a']>0) {cout<<'s';hash['s'-'a']-=1;judge = 1;}
        if (hash['t'-'a']>0) {cout<<'t';hash['t'-'a']-=1;judge = 1;}
        if (judge == 0)break;
    }
    return 0;
}

//B1043
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    char a[50000];
    cin.getline(a,50000);
    int hash[6] = {};
    int lena = (int)strlen(a);
    int sum = 0;
    for(int i = 0;i<lena;i++) {
        if (a[i]=='P'){hash[0]++;sum+=1;}
        else if (a[i]=='A'){hash[1]++;sum+=1;}
        else if (a[i]=='T'){hash[2]++;sum+=1;}
        else if (a[i]=='e'){hash[3]++;sum+=1;}
        else if (a[i]=='s'){hash[4]++;sum+=1;}
        else if (a[i]=='t'){hash[5]++;sum+=1;}
    }

    for(int i = 0;i<lena;i++) {
        if (hash[0]>0) {cout<<'P';hash[0]-=1;sum-=1;}
        if (hash[1]>0) {cout<<'A';hash[1]-=1;sum-=1;}
        if (hash[2]>0) {cout<<'T';hash[2]-=1;sum-=1;}
        if (hash[3]>0) {cout<<'e';hash[3]-=1;sum-=1;}
        if (hash[4]>0) {cout<<'s';hash[4]-=1;sum-=1;}
        if (hash[5]>0) {cout<<'t';hash[5]-=1;sum-=1;}

        if (sum <= -1)break;
    }
    return 0;
}

//B1044/A1100 $ 0/5
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <map>
#include <string>
using namespace std;

int toint(string a){
    int b = 0;
    for(int i = 0;i<a.size();i++){
        b = b*10 + (int)(a[i] - '0');
    }
    return b;
}


int main(){
    string a[13] = {"tret","jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
    string b[13] = {"tret","tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};

    map<string,int> str2int;
    string int2str[169];
    // 这个大小开错了，导致两个测试点错误：多了就会有重复！
    for(int i = 0;i<169;i++){
        string temp;
        if (i/13 != 0 && i%13 != 0)
            temp = b[i/13]+" "+a[i%13];
        else if (i/13 == 0) temp = a[i%13];
        else temp = b[i/13];
        int2str[i] = temp;
        str2int[temp] = i;
//        cout<<i<<' '<<temp<<endl;
    }
//    printf("%d",str2int["tam"]);
    int n;
    string str;
    scanf("%d%*c",&n);   // 这里一定要接收换行符！！
    // NOTE 16 scanf 接收换行符
    while(n--){
        getline(cin,str);
        if(str[0]>='0'&&str[0]<='9'){
            int temp = toint(str);
            cout<<int2str[temp]<<endl;
        }
        else{
            cout<<str2int[str]<<endl;
        }
    }
    return 0;
}

//B1045/A1101
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int>a;a.resize(n);
    for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
    vector<int>left;left.resize(n);
    vector<int>right;right.resize(n);
    vector<int>result;result.resize(n);
    int max = a[0],min = a[n-1];
    left[0] = 1;right[n-1] = 1;
    for(int i = 0;i<n;i++){
        if (a[i]>=max){max = a[i];left[i] = 1;}
        else {left[i] = 0;}
    }
    for(int i = n-1;i>=0;i--){
        if (a[i]<=min){min = a[i];right[i] = 1;}
        else {right[i] = 0;}
    }
    int count = 0;
    for(int i = 0;i<n;i++){
        if (left[i] == 1 && right[i] == 1){
//            result.push_back(a[i]);
            result[count++] = a[i];}
    }
    printf("%d\n",count);
    vector<int>finalresult;finalresult.resize(count);
    for(int i = 0;i<count;i++){finalresult[i] = result[i];}
//    说是大小顺序，但其实一定是从小到大的！这一步拷贝排序完全是多余的！
//    sort(finalresult.begin(),finalresult.end());
    for(int i = 0;i<count;i++){
        printf("%d",result[i]);
        if (i<count - 1)printf(" ");
    }
    printf("\n");
    return 0;
}

//B1047
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int>team;
    team.resize(1000);
    for(int i = 0;i<n;i++){
        int a,b,c;
        scanf("%d-%d %d",&a,&b,&c);
        team[a]+=c;
    }
    int max = 0,mteam = 0;
    for(int i = 0;i<1000;i++){
        if (team[i]>max){max = team[i];mteam = i;}
    }
    cout<<mteam<<' '<<max;
    return 0;
}

//B1048 TODO 4/6
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int cmp(string a,string b){
    if(a.size()>b.size()) return (int)b.size();
    else return (int)a.size();
}
string max(string a,string b){
    if(a.size()<b.size()) return b;
    else return a;
}
int main(){
    string a,b,c;
    cin>>a>>b;
    for(int i = 0;i<cmp(a,b);i++){
        if(i%2==0){
            int temp = (a[a.size()-i-1]+b[b.size()-i-1]-'0'-'0')%13;
//            cout<<"ji "<<temp<<endl;
            if (temp<10) c.push_back((char)(temp+'0'));
            else if (temp==10) c.push_back('J');
            else if (temp==11) c.push_back('Q');
            else if (temp==12) c.push_back('K');
        }
        else{
//            cout<<"ou "<<(char)((10-a[a.size()-i-1]+b[b.size()-i-1])%10+'0')<<endl;
            c.push_back((char)((10-a[a.size()-i-1]+b[b.size()-i-1])%10+'0'));
        }
//        cout<<c<<endl;
    }
    for(int i = cmp(a,b);i<max(a,b).size();i++){
        c.push_back(max(a,b)[max(a,b).size()-i-1]);
    }
    for(int i = 0;i<c.size();i++){
        cout<<c[c.size()-1-i];
    }
    return 0;
}

//B1049/A1104 &AC
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<double>a;a.resize(n);
    for(int i = 0;i<n;i++){
        scanf("%lf",&a[i]);
    }
    double finalproduct = 0.0;
    for(int i = 0;i<n;i++){
        finalproduct += a[i] * (i+1) * (n-i);
    }
    printf("%.02lf",finalproduct);

    return 0;
}

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

int main(){
    int a,b,result;
    string op;
    cin>>a>>b;
    result = a+b;
//    cout<<result;
    op = to_string(result);
//    cout<<op.size();
    int judge = 1;
    for(int i = 0;i<op.size();i++){
        if (i%3 == op.size()%3 && judge == 0){
            cout<<',';
            i-=1;
            judge = 1;
        }
        else {
            cout<<op[i];
            if (op[i] == '-')judge = 1;
            else judge = 0;
        }
    }return 0;
}

//A1003 $ 不会
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn = 510;
const int INF = 0x3fffffff;

struct node{
    int v,weight;
    node(int _v,int _w):v(_v),weight(_w){};
};
int n,m,s,u;
vector<node>adj[maxn];
int dis[maxn];
//int dis[maxn] = {INF}; // NOTE20 只能0可以简单的初始化，其它的初值需要用 fill 函数
int weight[maxn],pathnum[maxn] = {0},teamnum[maxn] = {0};
bool vis[maxn] = {false};

void Dj(int s){
    fill(dis,dis+maxn,INF);
    dis[s] = 0;pathnum[s] = 1;teamnum[s] = weight[s];
    for(int i = 0;i<n;i++){

        int MIN = INF,k = -1;
        for(int j = 0;j<n;j++){
            if (dis[j] < MIN && vis[j] == false){
                MIN = dis[j];
                k = j;
            }
        }
        if (k == -1)return;
        vis[k] = true;
//        printf("%d ",k);
        for(int j = 0;j<adj[k].size();j++){
            int v = adj[k][j].v;
//            printf("--%d--",adj[k][j].v);
            if (vis[v] == false){
                if(dis[v] > dis[k] + adj[k][j].weight)
                {
                    dis[v] = dis[k] + adj[k][j].weight;
                    pathnum[v] = pathnum[k];
                    teamnum[v] = teamnum[k] + weight[v];
                }
                else if (dis[v] == dis[k] + adj[k][j].weight)
                {
                    if (teamnum[v] < teamnum[k] + weight[v])
                    {
                        teamnum[v] = teamnum[k] + weight[v];
                    }
                    pathnum[v] += pathnum[k];
                }
            }
        }
//        printf("%d %d %d %d  ",i,k,pathnum[u],teamnum[u]);
//        for(int p = 0;p<n;p++){printf(" %d-%d",dis[p],vis[p]);}
//        printf("\n");
    }
}


int main(){
    scanf("%d %d %d %d",&n,&m,&s,&u);
    for(int i = 0;i<n;i++){scanf("%d",&weight[i]);}
    for(int i = 0;i<m;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        adj[a].push_back(node(b,c));
        adj[b].push_back(node(a,c));
    }

//    for(int i = 0;i<n;i++){
//        printf("%d ",i);
//        for(int j = 0;j<adj[i].size();j++)
//        {
//            printf("%d-%d ",adj[i][j].v,adj[i][j].weight);
//        }
//        printf("\n");
//    }

    Dj(s);
    printf("%d %d\n",pathnum[u],teamnum[u]);
    return 0;
}

//A1004 6/6
#include <queue>
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
struct Node{
    int layer;
    vector<int>child;
};
vector<Node>tree;

void inorder(int root){
    queue<int>q;
    q.push(root);
    tree[root].layer = 1;
    while(!q.empty()){
        int front = q.front();
//        printf("%d\n",front);
        q.pop();
        for(int i = 0;i<tree[front].child.size();i++){
            q.push(tree[front].child[i]);
            tree[tree[front].child[i]].layer = tree[front].layer + 1;
        }
    }
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    tree.resize(n+1);
    for(int i = 0;i<m;i++){
        int childsize,number;
        scanf("%d %d",&number,&childsize);
        tree[number].child.resize(childsize);
        for(int j = 0;j<childsize;j++){
            scanf("%d",&tree[number].child[j]);
        }
    }


//    for(int i = 0;i<n;i++){
//        printf("%d ",i);
//        for (int j = 0;j<tree[i].child.size();j++){
//            printf(" %d",tree[i].child[j]);
//        }
//        printf("\n");
//    }

    inorder(1);

//    for(int i = 0;i<n;i++){
//        printf("%d %d",i,tree[i].layer);
//        for (int j = 0;j<tree[i].child.size();j++){
//            printf(" %d",tree[i].child[j]);
//        }
//        printf("\n");
//    }

    vector<int>count(n+1);
    int maxlayer = 0;
    for(int i = 0;i<n+1;i++){
        if (tree[i].child.size() == 0) count[tree[i].layer]++;
        if (tree[i].layer > maxlayer) maxlayer = tree[i].layer;
    }

    for (int i = 1;i<maxlayer+1;i++){
        printf("%d",count[i]);
        if (i<maxlayer) printf(" ");
    }
    return 0;
}

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

int main(){
    string a;
    int sum = 0;
    cin>>a;
    for (int i = 0;i<a.size();i++){
        sum += a[i]-'0';
    }
    string result = to_string(sum);
    for (int i = 0;i<result.size();i++){
        switch (result[i]-'0'){
            case 0:cout<<"zero";break;
            case 1:cout<<"one";break;
            case 2:cout<<"two";break;
            case 3:cout<<"three";break;
            case 4:cout<<"four";break;
            case 5:cout<<"five";break;
            case 6:cout<<"six";break;
            case 7:cout<<"seven";break;
            case 8:cout<<"eight";break;
            case 9:cout<<"nine";break;
        }
        if (i!=result.size()-1)cout<<' ';
    }
    return 0;
}

//A1006
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct{
    char name[20];
    int date1,date2;
} man;

bool cmp1(man a,man b)
{
    return a.date1<b.date1;
}

bool cmp2(man a,man b)
{
    return a.date2>b.date2;
}

int main(){
    int n;
    cin>>n;
    man people[n];
    int a,b,c,d,e,f;
    for (int i = 0;i<n;i++){
        scanf("%s %d:%d:%d %d:%d:%d" ,people[i].name,&a,&b,&c,&d,&e,&f);
        people[i].date1 = a*10000+b*100+c;
        people[i].date2 = d*10000+e*100+f;
    }
    sort(people, people+n,cmp1);
    cout<<people[0].name<<' ';
    sort(people, people+n,cmp2);
    cout<<people[0].name<<endl;
    return 0;
}

//A1007 $ 5/25 审题!
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int n,flag = 0;
    scanf("%d",&n);
    int a[n],dp[n],posstart[n];
    for(int i = 0;i<n;i++){
        scanf("%d",&a[i]);
        if (a[i]>=0)flag = 1;
    }
    if (flag == 0){
        printf("0 %d %d",a[0],a[n-1]);
        return 0;
    }
    dp[0] = a[0];
    for(int i = 1;i<n;i++){
        if (dp[i-1]+a[i] > a[i]){
            dp[i] = dp[i-1]+a[i];
            posstart[i] = posstart[i-1];
        }
        else{
            dp[i] = a[i];
            posstart[i] = i;
        }
    }

    int maxendpos = 0;
    for (int i = 0;i<n;i++){
        if (dp[i] > dp[maxendpos]){
            maxendpos = i;
        }
    }

    printf("%d %d %d",dp[maxendpos],a[posstart[maxendpos]],a[maxendpos]);

    return 0;
}

//A1008 $AC 虽然没考虑列表相邻相同的情况，但还是AC了
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int>a;a.resize(n);
    for(int i = 0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int finalproduct = 0,now = 0;
    for(int i = 0;i<n;i++){
        if (a[i]>now)finalproduct+= 6 * (a[i]-now) + 5;
        else finalproduct+= 4 * (-a[i]+now) + 5;
        now = a[i];
    }
    printf("%d",finalproduct);
    return 0;
}

//A1010 TODO 13/20
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

// string a 转换成 k 进制 longlong
long long convert(string a,int k){
    long long num = 0;
    for(int i = (int)a.size()-1;i>=0;i--){
        int temp = 0;
        if (a[i] >= '0' && a[i]<='9')temp = a[i] - '0';
        else temp = a[i] - 'a' + 10;
        if (k<=temp)return 0;
        num += temp * pow(k, (a.size()-1-i));
    }
    return num;
}

// 找到最大的进制数
int maxradix(string a){
    int radix = 0;
    for(int i = 0;i<a.size();i++){
        if (a[i] >= '0' && a[i]<='9'){
            if ((a[i]-'0')>radix) radix = a[i]-'0';
        }
        else {
            if ((a[i]-'a'+10)>radix) radix = a[i]-'a'+10;
        }
    }
    return radix;
}

int main(){
    int tag,radix;
    string a,b;
    cin>>a>>b>>tag>>radix;
    long long anum;
    if (tag == 1){
        anum = convert (a,radix);
    }
    else{
        anum = convert (b,radix);
        b = a;
    }
    int left = 0,right = max(maxradix(b),radix)+1,sgn = 0;
    while(left<=right){
        int mid = (left + right)/2;
        if (anum < convert(b, mid)) right = mid-1;
        else if (anum > convert(b, mid)) left = mid+1;
        else {cout<<mid;sgn = 1;break;}
//        cout<<mid<<endl;
    }
    if (sgn == 0)cout<<"Impossible";
    return 0;
}

//A1011
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int n;
    double a[3][3];
    int pos[3];
    for (int i = 0;i<3;i++){
        for (int j = 0;j<3;j++){
            cin>>a[i][j];
        }
        double max = 0;
        for (int j = 0;j<3;j++){
            if (a[i][j]>max){
                max = a[i][j];
                pos[i] = j;
            }
        }
    }
    for (int i = 0;i<3;i++){
        if (pos[i] == 0) cout<<"W ";
        else if (pos[i] == 1) cout<<"T ";
        else if (pos[i] == 2) cout<<"L ";
    }
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<(a[1][pos[1]] * a[0][pos[0]] *a[2][pos[2]] * 0.65 - 1)*2;

    return 0;
}

//A1012
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int now;
typedef struct{
    int id;
    int grade[4];
    int rank[4];
} student;

bool cmp(student a,student b)
{
    return a.grade[now]>b.grade[now];
}

int main(){
    int n,m;
    cin>>n>>m;
    student stu[n],stuchk[m];
    for(int i = 0;i<n;i++){
        cin>>stu[i].id>>stu[i].grade[0]>>stu[i].grade[1]>>stu[i].grade[2];
        stu[i].grade[3] = stu[i].grade[0]+stu[i].grade[1]+stu[i].grade[2];
    }
    for(int i = 0;i<m;i++){
        cin>>stuchk[i].id;
    }
    for(now = 0;now<4;now++){
        sort(stu, stu+n, cmp);
        for(int i = 0;i<n;i++){
            if (i == 0) stu[i].rank[now] = i;
            if (stu[i].grade[now]!=stu[i-1].grade[now]) stu[i].rank[now] = i;
            else stu[i].rank[now] = stu[i-1].rank[now]; //这里有并列排名的时候，rank要一样！//NOTE4
        }
    }
//    for(int i = 0;i<n;i++){
//        printf("%d %d %d %d %d %d %d %d %d \n",
//               stu[i].id,stu[i].grade[0],stu[i].grade[1],stu[i].grade[2],stu[i].grade[3],stu[i].rank[0],stu[i].rank[1],stu[i].rank[2],stu[i].rank[3]);
//    }
    int toop[4] = {3,0,1,2};
    for(int i = 0;i<m;i++){
//        cout<<i<<stuchk[i].id<<' ';
        int sgn = 0;
        for(int j = 0;j<n;j++){
            if (stuchk[i].id == stu[j].id){
                int min = n,minsgn = 5;
                for(int k = 0;k<4;k++){
                    if (stu[j].rank[toop[k]]<min) {
                        min = stu[j].rank[toop[k]];
                        minsgn = toop[k];}
                }
                cout<<min+1<<' ';
                switch (minsgn){
                    case 0:{cout<<"C"<<endl;break;}
                    case 1:{cout<<"M"<<endl;break;}
                    case 2:{cout<<"E"<<endl;break;}
                    case 3:{cout<<"A"<<endl;break;}
                    default:continue;
                }
                sgn = 1;
                break;
            }
        }
        if (sgn == 0)cout<<"N/A"<<endl;
    }
    return 0;
}

//A1013 $ 18/25 想复杂了
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1010;
int n,m,k;

vector<int>graph[maxn];

bool BFS(int start,int end,int nopass){
    queue<int>q;
    bool vis[maxn] = {false};
    q.push(start);vis[start] = true;
    while(!q.empty()){
        int top = q.front();q.pop();
        if (top == end)return true;
        for(int i = 0;i<graph[top].size();i++){
            int temp = graph[top][i];
            if (temp != nopass && vis[temp] == false){
                q.push(temp);
                vis[temp] = true;
            }
        }
    }
    return false;
}

int getNum(int nopass){

    int count = 0;
    for(int i = 1;i<graph[nopass].size();i++){
//        printf("%d %d %d\n",graph[nopass][0],graph[nopass][i],BFS(graph[nopass][0], graph[nopass][i], nopass));
        if (!BFS(graph[nopass][0], graph[nopass][i], nopass)){
            count ++;
            int a = graph[nopass][0];
            int b = graph[nopass][i];
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
    }
    return count;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1;i<m+1;i++){
        int temp1,temp2;
        scanf("%d%d",&temp1,&temp2);
        graph[temp2].push_back(temp1);
        graph[temp1].push_back(temp2);
    }

//    for(int i = 1;i<n+1;i++){
//        printf("\n%d",i);
//        for(int j = 0;j<graph[i].size();j++){
//            printf(" %d",graph[i][j]);
//        }
//    }

    int query[k];
    for(int i = 0;i<k;i++){scanf("%d",&query[i]);}
    for(int i = 0;i<k;i++){printf("%d\n",getNum(query[i]));}

    return 0;
}

//A1013 并查集 $ 25/25
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1010;
int father[maxn];
bool vis[maxn];
vector<int>g[maxn];

void init(int n){
    for(int i = 1;i<=n;i++){
        father[i] = i;
        vis[i] = false;
    }
}

int findfather(int k){
    int a = k;
    while(father[k]!=k){
        k = father[k];
    }
    while(father[a]!=a){
        int z = father[a];
        father[a] = k;
        a = z;
    }
    return k;
}

void Union(int a,int b){
    int faa = findfather(a);
    int fab = findfather(b);
    if (faa != fab) father[a] = b;
}

int main(){
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    init(n);
    for(int i = 1;i<m+1;i++){
        int temp1,temp2;
        scanf("%d%d",&temp1,&temp2);
        g[temp1].push_back(temp2);
        g[temp2].push_back(temp1);
    }
    int cur;
    for(int i = 0;i<k;i++){
        scanf("%d",&cur);
        init(n);
        for(int ii = 1;ii <= n;ii++){
            for(int jj = 0;jj<g[ii].size();jj++){
                int u = ii,v = g[ii][jj];
                if (u!=cur && v != cur){
                    Union(u, v);
                }
            }
        }
        int count= 0;
        for(int i = 1;i<=n;i++){
            if (i == cur)continue;
            int fai = findfather(i);
            if (vis[fai] == false){
                count++;
                vis[fai] = true;
            }
        }
        printf("%d\n",count-1);
    }
    return 0;
}

//A1015 $ 1/4 TODO 2/4
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

bool isPrime(int n)
{
    if (n<1)return false;
    for(int i=2;i<(int)sqrt(1.0*n)+1;i++)
    {
        if(n % i == 0)return false;
    }
    return true;
}

// NOTE 11 进制转换模板
// k1 进制 string a 转换成 k2 进制（都<=10）
int convert(string a,int k1,int k2){
    int num = 0;
    for(int i = (int)a.size()-1;i>=0;i--){
        int temp = 0;
        if (a[i] >= '0' && a[i]<='9')temp = a[i] - '0';
        num += temp * pow(k1, (a.size()-1-i));
    }
    vector<int>tempvec;
    if (k2 == 10) return num;
    else{
        while(num>=k2){
            tempvec.push_back(num % k2);
            num /= k2;
        }
        tempvec.push_back(num);
    }
    num = 0;
    for(int i = 0;i<tempvec.size();i++){
        num = num * 10 + tempvec[tempvec.size()-i-1];
    }
    return num;
}

int main(){
    vector<int>n1;
    vector<int>d;
    int temp = 1,count = 0;
    while(temp>0){
        scanf("%d",&temp);
        if (temp<0)break;
        if (count % 2 == 1) d.push_back(temp);
        else n1.push_back(temp);
        count++;
    }

    for(int i = 0;i<n1.size();i++){
        if (isPrime(n1[i]) == false)printf("No\n");
        else{
//            cout<<n1[i]<<' '<<d[i]<<' ';
//            cout<<convert(to_string(n1[i]),10,d[i])<<' ';
            string str = to_string(convert(to_string(n1[i]),10,d[i]));
//            cout<<str<<' ';
            reverse(str.begin(),str.end());
//            cout<<str<<' '<<endl;
            if (isPrime(convert(str,d[i],10))) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

//A1016 TODO 写了一晚上，一分没有T_T 0/4
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct {
    int time[4];
    //  int time[4] = {}; //这样就不对了，这是为啥呢TODO
    bool online = 0;
}record;

typedef struct {
    string name;
    vector<record>records;
}client;

bool cmp(record a,record b){
    if(a.time[0]!=b.time[0])return a.time[0]<b.time[0];
    else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1];
    else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2];
    else return a.time[3]<b.time[3];
}

bool cmpname(client a,client b){
    return a.name<b.name;
}

int main(){
    int toll[24],n;
    for(int i = 0;i<24;i++){cin>>toll[i];}
    cin>>n;
    vector<client>clients;
    for(int i = 0;i<n;i++){
        string temp;
        char temp2[100];
        record temp1;
        cin>>temp;
        int k = 0;
        int sgn = 0;
        for(int i = 0;i<clients.size();i++){
            if (clients[i].name == temp){k = i;sgn = 1;}
        }
        if (sgn == 0){
            clients.resize(clients.size()+1);
            clients[clients.size()-1].name = temp;
            k = (int)clients.size()-1;
        }
    scanf("%d:%d:%d:%d %s",&temp1.time[0],&temp1.time[1],&temp1.time[2],&temp1.time[3],temp2);
        if (temp2[1] == 'n') temp1.online = 1;      //online=1
        else temp1.online = 0;
        clients[k].records.push_back(temp1);
    }

    //完成输入，下面开始操作
    sort(clients.begin(),clients.end(),cmpname);    //排列姓名
    for(int i = 0;i<clients.size();i++){
        double totalmoney = 0;
        sort(clients[i].records.begin(),clients[i].records.end(),cmp); //排列记录时间
        while(clients[i].records[clients[i].records.size()-1].online == 1){ //删除最后落单的online
            clients[i].records.pop_back();
        }
        while(clients[i].records[0].online == 1 && clients[i].records[1].online == 1){ //删除最前落单的online
            clients[i].records.erase(clients[i].records.begin());
        }
        bool k = 1; //用于切换offline和online
        int printname = 0;
        for(int j = 0;j<clients[i].records.size();j++){
            record temp;
            if (k==clients[i].records[j].online){
                if(printname == 0){
                    cout<<clients[i].name<<' '<<setw(2)<< setfill('0')<<clients[i].records[0].time[0]<<endl;
                    printname = 1;
                }
                cout<<setw(2)<< setfill('0')<<clients[i].records[j].time[1]<<':'<<setw(2)<< setfill('0')<<clients[i].records[j].time[2]<<':'<<setw(2)<< setfill('0')<<clients[i].records[j].time[3];                k = !k; //用于切换offline和online
                if(clients[i].records[j].online == 1){
                    temp = clients[i].records[j];   //记录online
                    cout<<' ';
                }
                else{
                    int time = (clients[i].records[j].time[1]*1440+clients[i].records[j].time[2]*60+clients[i].records[j].time[3])-(temp.time[1]*1440+temp.time[2]*60+temp.time[3]);
                    double money = 0;
                    double start,end;
                    for(int day = temp.time[1];
                        day<clients[i].records[j].time[1]+1;day++){
                        for(int hour = temp.time[2];
                            hour < clients[i].records[j].time[2]+1;hour++){
                            if (temp.time[1]==clients[i].records[j].time[1] && temp.time[2]==clients[i].records[j].time[2]){    //避免临界情况
                                start = temp.time[3];end = clients[i].records[j].time[3];
                            }
                            else if (day == temp.time[1] && hour == temp.time[2]){start = temp.time[3];end = 60;}
                            else if (day == clients[i].records[j].time[1] && hour == clients[i].records[j].time[2]){start = 0;end = clients[i].records[j].time[3];}
                            else {start = 0;end = 60;}
                            money = money + (double)toll[hour] * (end-start) / 100;
                        }
                    }
                    cout<<' '<<time<<" $"<<fixed<<setprecision(2)<<money<<endl;
                    totalmoney = totalmoney + money;
                }
            }
        }
        if (totalmoney > 0){
        cout<<"Total amount: $"<<fixed<<setprecision(2)<<totalmoney<<endl;
        }
    }
    return 0;
}
//// 比较坑的临界数据
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
5
a 01:01:01:03 on
a 01:02:00:01 once_flag
CYLL 01:28:15:41 once_flag
a 01:05:02:24 once_flag
a 01:02:00:02 off_t

//A1016 第二个改版，1/4了呜呜呜 TODO
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct {
    int time[4];
    char name[100];
    //  int time[4] = {}; //这样就不对了，这是为啥呢TODO
    bool online = 0;
}record;

bool cmp(record a,record b){
    if(a.time[0]!=b.time[0])return a.time[0]<b.time[0];
    else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1];
    else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2];
    else return a.time[3]<b.time[3];
}

bool cmpname(record a,record b){
    if (strcmp(a.name,b.name)!=0) return strcmp(a.name,b.name)<0;
    else if(a.time[0]!=b.time[0])return a.time[0]<b.time[0];
    else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1];
    else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2];
    else return a.time[3]<b.time[3];
}

int main(){
    int toll[24],n;
    for(int i = 0;i<24;i++){cin>>toll[i];}
    cin>>n;
    vector<record>recs;
    for(int i = 0;i<n;i++){
        string temp;
        char temp2[100];
        record temp1;
        scanf("%s %d:%d:%d:%d %s",temp1.name,&temp1.time[0],&temp1.time[1],&temp1.time[2],&temp1.time[3],temp2);
        if (temp2[1] == 'n') temp1.online = 1;      //online=1
        else temp1.online = 0;
        recs.push_back(temp1);
    }

    //完成输入，下面开始操作
    sort(recs.begin(),recs.end(),cmpname);    //排列姓名

    vector<record>recs4real;
    for(int i = 0;i<recs.size()-1;i++){
        if (strcmp(recs[i].name,recs[i+1].name)==0 && recs[i].online == 1 && recs[i+1].online == 0){
            recs4real.push_back(recs[i]);
            recs4real.push_back(recs[i+1]);
            i = 1+i;
        }
    }

//    for(int i = 0;i<recs4real.size();i+=2){
//        printf("%s %02d:%02d:%02d:%02d %d\n",recs4real[i].name,recs4real[i].time[0],recs4real[i].time[1],recs4real[i].time[2],recs4real[i].time[3],(int)recs4real[i].online);
//    }cout<<endl;


    char tempname[20];
    int time = 0;
    double totalmoney = 0;
    for(int i = 0;i<recs4real.size();i+=2){

        if (strcmp(recs4real[i].name,tempname) != 0){
            printf("%s %02d\n",recs4real[i].name,recs4real[i].time[0]);
            sscanf(recs4real[i].name,"%s",tempname);
        }

        int passtime = (recs4real[i+1].time[1]*1440+recs4real[i+1].time[2]*60+recs4real[i+1].time[3])-(recs4real[i].time[1]*1440+recs4real[i].time[2]*60+recs4real[i].time[3]);
        double money = 0;
        double start,end;
        for(int day = recs4real[i].time[1];
            day<recs4real[i+1].time[1]+1;day++){
            for(int hour = recs4real[i].time[2];
                hour < recs4real[i+1].time[2]+1;hour++){
                if (recs4real[i].time[1]==recs4real[i+1].time[1] && recs4real[i].time[2]==recs4real[i+1].time[2]){    //避免临界情况
                    start = recs4real[i].time[3];end = recs4real[i+1].time[3];
                }
                else if (day == recs4real[i].time[1] && hour == recs4real[i].time[2]){start = recs4real[i].time[3];end = 60;}
                else if (day == recs4real[i+1].time[1] && hour == recs4real[i+1].time[2]){start = 0;end = recs4real[i+1].time[3];}
                else {start = 0;end = 60;}
                money = money + (double)toll[hour] * (end-start) / 100;
            }
        }
        totalmoney += money;
        printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n",recs4real[i].time[1],recs4real[i].time[2],recs4real[i].time[3],recs4real[i+1].time[1],recs4real[i+1].time[2],recs4real[i+1].time[3],passtime,money);

        if (strcmp(recs4real[i].name,recs4real[i+2].name) != 0){
            printf("%s $%.2f\n","Total amount:",totalmoney);
            totalmoney = 0;
        }

    }

    return 0;
}

//A1018 $ 16/30
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;
const int maxn = 510;
const int INF = 0x3fffffff;

struct edge{
    int v,length;
    edge(int _a,int _b):v(_a),length(_b){};
};

int cmax,n,sp,m;
int bikenum[maxn],dis[maxn];
bool vis[maxn] = {};
vector<edge>adj[maxn];
vector<int>pre[maxn],best,tempbest;

void Dj(int start){
    fill(dis,dis+maxn,INF);
    dis[start] = 0;
    for(int ii = 0;ii<n;ii++){
        int k = -1,MIN = INF;
        for(int i = 0;i<n;i++){
            if (dis[i]<MIN && vis[i] == false){
                MIN = dis[i];
                k = i;
            }
        }
        if (k == -1)return;
        vis[k] = true;
        for(int i = 0;i<adj[k].size();i++){
            int v = adj[k][i].v;
            if (vis[v] == false && dis[v] > dis[k] + adj[k][i].length){
                dis[v] = dis[k] + adj[k][i].length;
                pre[v].clear();
                pre[v].push_back(k);
            }else if(dis[v] == dis[k] + adj[k][i].length){
                pre[v].push_back(k);
            }
        }
    }
}

// 题意没有读明白！need有正有负！审题！而且途中每个都要调到最优！！
int minneed = INF,minremain = INF;
void DFS(int now){
    if (now == 0){
        tempbest.push_back(0);
        int need = 0,remain = 0;
        for(int i = (int)tempbest.size()-2;i>=0;i--){
            int n = bikenum[tempbest[i]] - cmax/2;
//            printf("%d ",n);
            if (n > 0){
                remain += n;
            }
            else{
                if (remain > -n ){
                    remain = remain + n;
                }
                else{
                    need = need - n - remain;
                    remain = 0;
                }
            }
//            printf(" _%d_%d_ ",need,remain);

        }
        if (need < minneed){
            minneed = need;
            minremain = remain;
            best = tempbest;
        }else if (need == minneed && remain < minremain){
            minneed = need;
            minremain = remain;
            best = tempbest;
        }
//        printf("__%d__%d__\n",minneed,minremain);
        tempbest.pop_back();
        return;
    }
    tempbest.push_back(now);
    for(int i = 0;i<pre[now].size();i++){
        DFS(pre[now][i]);
    }
    tempbest.pop_back();
}


int main(){
    scanf("%d %d %d %d",&cmax,&n,&sp,&m);
    for(int i = 1;i<=n;i++){scanf("%d",&bikenum[i]);}
    for(int i = 0;i<m;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        adj[a].push_back(edge(b,c));
        adj[b].push_back(edge(a,c));
    }

    Dj(0);
    DFS(sp);

    printf("%d ",minneed);
    for(int i = 0;i<best.size();i++){
        printf("%d",best[best.size() - 1- i]);
        if (i<best.size()-1)printf("->");
    }
    printf(" %d",minremain);

    return 0;
}

//A1019
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int c,d;
    cin>>c>>d;
    vector<int>result;
    while (c/d > 0){
        result.push_back(c-d*(c/d));
        c = (c-c%d)/d;
    }
    result.push_back(c);
    int judge = 1;
    for(int i = 0;i<(result.size()+1)/2;i++){
        if (result[i]!=result[result.size()-1-i]){
            cout<<"No";
            judge = 0;
            break;
        }
    }
    if (judge == 1){
        cout<<"Yes";
    }
    cout<<endl;
    for(int i = 0;i<result.size();i++){
        cout<<result[result.size()-1-i];
        if (i<result.size()-1) cout<<' ';
    }
    return 0;
}

//A1020 $ 6/6
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct node{
    int data;
    node* lchild;
    node* rchild;
}Node;

vector<int>layer(0),post(30),in(30);

node* create(int postL,int postR,int inL,int inR){
    if (postL>postR)return NULL;
    node* root = new node;
    root->data = post[postR];
//    printf("%d\n",root->data);
    int k;
    for(k = inL;k<inR;k++){
        if (post[postR] == in[k]){
            break;
        }
    }
    int leftnum = k-inL;
    root->lchild = create(postL, postL+leftnum-1, inL, k-1);
    root->rchild = create(postL+leftnum,postR-1,k+1,inR);
    return root;
}

void layerorder(node* root,vector<int>&layer){
    queue<node*>q;
    q.push(root);
    node *now = new node;
    while(!q.empty()){
        layer.push_back(q.front()->data);
//        printf("%d\n",q.front()->data);
        now = q.front();
        q.pop();
        if (now->lchild != NULL)q.push(now->lchild);
        if (now->rchild != NULL)q.push(now->rchild);
    }
}

int main(){
    int n;
    scanf("%d",&n);
    post.resize(n);in.resize(n);
    for(int i = 0;i<n;i++){scanf("%d",&post[i]);}
    for(int i = 0;i<n;i++){scanf("%d",&in[i]);}
    node* root = new node;
    root = create(0, n-1, 0, n-1);
    layerorder(root, layer);
    for(int i = 0;i<n;i++){
        printf("%d",layer[i]);
        if (i<n-1) printf(" ");
    }
    return 0;
}

//A1021 不会 $ 23/25
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100000;

int n;
vector<int>g[maxn];
int father[maxn];
bool vis[maxn] = {false};
bool isfather[maxn] = {false};

void init(int n){
    for(int i = 1;i<n+1;i++){
        father[i] = i;
    }
}

int findfather(int n){
    int a = n;
    while(father[n]!=n){
        n = father[n];
    }
    while(a!=father[a]){
        int z = father[a];
        father[a] = n;
        a = z;
    }
    return n;
}

void Union(int a,int b){
    int faa = findfather(a);
    int fab = findfather(b);
    if (faa != fab){father[faa] = fab;}
}

int countblock(){
    for(int i = 1;i<n+1;i++){
        isfather[findfather(i)] = true;
    }
    int count = 0;
    for(int i = 1;i<n+1;i++){
        if (isfather[i] == true)count++;
    }
    return count;
}

int maxdepth = 0;
vector<int>temp,ans;
void DFS(int start,int depth,int pre){
    if (depth > maxdepth){
        temp.clear();
        temp.push_back(start);
        maxdepth = depth;
    }else if (depth == maxdepth){
        temp.push_back(start);
    }
    for(int i = 0;i<g[start].size();i++){
        if (g[start][i] == pre)continue;
        DFS(g[start][i], depth+1, start);
    }
}

int main(){
    scanf("%d",&n);
    init(n);
    for(int i = 0;i<n-1;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
        Union(a,b);
    }
    int blocks = countblock();
    if (blocks!=1){
        printf("Error: %d components",blocks);
    }
    else{
        DFS(1, 1, -1);
        ans = temp;
        DFS(ans[0], 1, -1);
        for(int i = 0;i<temp.size();i++){
            ans.push_back(temp[i]);
        }
        sort(ans.begin(),ans.end());
        for(int i = 0;i<ans.size();i++){
            if (ans[i]!=ans[i-1])printf("%d\n",ans[i]);
        }
    }
    return 0;
}

//A1022 $ 不会
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <iomanip>
#include <set>
#include <map>
#include <string>
using namespace std;

int main(){
    int n,m;
    map<string,set<int>>books;
    int tempid;
    string temp;
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%d%*c",&tempid);
        getline(cin,temp);books[temp].insert(tempid);
        getline(cin,temp);books[temp].insert(tempid);
        getline(cin,temp);
        int start = 0;
        for(int i = 0;i<temp.size();i++){
            if (temp[i] == ' '){
                books[temp.substr(start,i-start)].insert(tempid);
                start = i+1;
            }
        }
        books[temp.substr(start,temp.size()-start)].insert(tempid);
        getline(cin,temp);books[temp].insert(tempid);
        getline(cin,temp);books[temp].insert(tempid);
        }
    scanf("%d",&m);
    for(int i = 0;i<m;i++){
        scanf("%d: ",&tempid);
        getline(cin,temp);
        cout<<tempid<<": "<<temp<<endl;
        if (books.find(temp) == books.end())printf("Not Found\n");
        else{
            for(set<int>::iterator it = books[temp].begin();it!=books[temp].end();it++){
                printf("%07d\n",*it);
            }
            //        cout<<1231<<endl;
        }
    }
}

//A1024 $ 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

bool check (string a){
    if (a.size() == 1) return true;
    for (int i = 0;i<a.size()/2+1;i++){
        if (a[i]!=a[a.size()-1-i]) return false;
    }
    return true;
}

string plusn (string a){
    string b = a;
    reverse(a.begin(), a.end());
//    cout<<a<<' '<<b;
    string c;
    c.resize(a.size()+1);
    int p = 0;
    for(int i = (int)a.size()-1;i>=0;i--){
        int temp = (int)(a[i]+b[i]+p - '0' - '0');
//        cout<<temp<<endl;
        c[i+1] = (char)(temp % 10 +'0');
        p = (temp - temp % 10) / 10;
    }
    if (p!=0){
        c[0] = (char)( p +'0');
        return c;
    }
    else {
        string d;
        d.resize(c.size()-1);
        for(int i = 0;i<c.size()-1;i++){
            d[i] = c[i+1];
        }
        return d;
    }
}

int main(){
    int k;
    string a;
//    scanf("%s%d",&a,&k);
    cin>>a>>k;
    int count = 0;
    while(check(a)!=1 && count<k){
        a = plusn(a);
        count += 1;
    }
    cout<<a<<"\n"<<count;
//    string a;
//    cin>>a;
//    cout<<plusn(a);
}

//A1025 TODO 1/4
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct {
    int score,localrank,rank,group;
    string id;
}student;
// NOTE 19 cmp 写法
bool cmp1(student a,student b){
    if (a.group != b.group) return a.group < b.group;
    else return a.score>b.score;
}

bool cmp(student a,student b){
    return a.score>b.score;
}

int main(){
    int n;
    cin>>n;
    vector<student>students;
    for(int i = 0;i<n;i++){
        int temp;
        cin>>temp;
        student tempstu;
        tempstu.id.resize(30);
        for(int j=0;j<temp;j++){
            cin>>tempstu.id>>tempstu.score;
            tempstu.group = i+1;
            students.push_back(tempstu);
        }
    }
    sort(students.begin(), students.end(), cmp1);
    int count = 0;
    for(int i = 0;i<students.size();i++){
        if (i>0){
            if (students[i].group == students[i-1].group){
                if (students[i].score!=students[i-1].score) students[i].localrank = i-count;
                else students[i].localrank = students[i-1].localrank;

            }
            else{
                count = i;
                students[i].localrank = i-count;

            }
        }
        else{
            students[i].localrank = 0;
        }
    }

//    for(int i = 0;i<students.size();i++){
//        cout<<students[i].id<<' '<<students[i].score<<' '<<students[i].rank+1<<' '<<students[i].group<<' '<<students[i].localrank+1<<endl;
//    }
    sort(students.begin(), students.end(), cmp);
    for(int i = 0;i<students.size();i++){
        if (i == 0) students[i].rank = i;
        if (students[i].score!=students[i-1].score) students[i].rank = i;
        else students[i].rank = students[i-1].rank;
    }
    cout<<students.size()<<endl;
    for(int i = 0;i<students.size();i++){
        cout<<students[i].id<<' '<<students[i].rank+1<<' '<<students[i].group<<' '<<students[i].localrank+1<<endl;
    }

    return 0;
}

//A1027
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<'#';
    int result[6]={a/13,a-a/13*13,b/13,b-b/13*13,c/13,c-c/13*13};
    for (int i = 0;i<6;i++){
        if (result[i]<10) cout<<result[i];
        else cout<<(char)(result[i]-10+'A');
    }
    return 0;
}

//A1028
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <string.h>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct {
    int id,score;
    char name[10];  //分配的太多不行！测试点6会有段错误
}stu;

bool cmpid(stu a,stu b){
    return a.id<b.id;
}
bool cmpscore(stu a,stu b){
    if (a.score == b.score) return a.id<b.id;
    else return a.score<b.score;
}
bool cmpname(stu a,stu b){
    if (strcmp(a.name,b.name) == 0) return a.id<b.id;
    else return strcmp(a.name,b.name)<0;    //NOTE7 char数组要这样比大小
}

int main(){
    int n,k;
    cin>>n>>k;
    stu student[n];
    for(int i = 0;i<n;i++){
        scanf("%d %s %d",&student[i].id,student[i].name,&student[i].score);
    }
    switch (k){
        case 1:sort(student, student+n, cmpid);break;
        case 2:sort(student, student+n, cmpname);break;
        case 3:sort(student, student+n, cmpscore);break;
    }
    for(int i = 0;i<n;i++){
        cout<<setw(6)<<setfill('0')<<student[i].id<<' '<<student[i].name<<' '<<student[i].score<<endl;
    }
    return 0;
}

//A1029 直接用long会爆内存…… TODO 8/9 还是有一个内存超限
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    int lena,lenb;
    scanf("%d",&lena);
    int a[lena+1];
    for(int i = 0;i<lena;i++){scanf("%d",&a[i]);}
    scanf("%d",&lenb);
    int b[lenb+1];
    for(int i = 0;i<lenb;i++){scanf("%d",&b[i]);}
//    sort (a,a+lena);
//    sort (b,b+lenb);
    a[lena] = b[lenb] = 0x7fffffff;
    int median = (lena + lenb + 1)/2;
    int pa=0,pb=0,k=2;
    for(int i = 0;i<median;i++){
        if (a[pa]<b[pb]){pa+=1;k=0;}
        else {pb+=1;k=1;}
//        if (a[pa]<b[pb]){cout<<a[pa]<<' ';pa+=1;k=0;}
//        else {cout<<b[pb]<<' ';pb+=1;k=1;}

    }
    if (k == 0){cout<<a[pa-1];}
    else if (k == 1){cout<<b[pb-1];}
    return 0;
}

//A1030 $ 30/30
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 510;
const int INF = 0x3fffffff;

struct node {
    int v,dis,cost;
    node(int _v,int _dis,int _cost):v(_v),dis(_dis),cost(_cost){};
};

int n,m,s,d;
int dis[maxn],cost[maxn][maxn];
bool vis[maxn] = {false};
vector<node>adj[maxn];
vector<int>pre[maxn],best,tempbest;

void Dj(int start){
    fill(dis,dis+maxn,INF);
    dis[start] = 0;
    for(int ii = 0;ii<n;ii++){
        int MIN = INF,k = -1;
        for(int i = 0;i<n;i++){
            if (vis[i] == false && dis[i]<MIN){
                k = i;
                MIN = dis[k];
            }
        }
        if (k == -1)return;vis[k] = true;
        for(int i = 0;i<adj[k].size();i++){
            int v = adj[k][i].v;
            if (dis[v] > dis[k] + adj[k][i].dis){
                dis[v] = dis[k] + adj[k][i].dis;
                pre[v].clear();
                pre[v].push_back(k);
            }else if (dis[v] == dis[k] + adj[k][i].dis){
                pre[v].push_back(k);
            }
        }
    }
}


int getCost(){
    int tempcost = 0;
//    printf("\n");
    for(int i = 1;i<tempbest.size();i++){
        tempcost += cost[tempbest[i-1]][tempbest[i]];
//        printf("%d ",cost[tempbest[i-1]][tempbest[i]]);
    }
//    printf("tempcost=%d\n",tempcost);
    return tempcost;
}

int minCost = INF;
void DFS(int k){
    if (k == s){
        tempbest.push_back(k);
        int temp = getCost();
        if(temp<minCost){
            minCost = temp;
            best = tempbest;
        }
        tempbest.pop_back();
        return;
    }
    tempbest.push_back(k);
    for(int i = 0;i<pre[k].size();i++){
        DFS(pre[k][i]);
    }
    tempbest.pop_back();
}

int main(){
    scanf("%d %d %d %d",&n,&m,&s,&d);
    for(int i = 0;i<m;i++){
        int c1,c2,dis,tempcost;
        scanf("%d %d %d %d",&c1,&c2,&dis,&tempcost);
        adj[c1].push_back(node(c2,dis,tempcost));
        adj[c2].push_back(node(c1,dis,tempcost));
        cost[c1][c2] = cost[c2][c1] = tempcost;
    }

    Dj(s);

//    for(int i = 0;i<n;i++){
//        printf("%d ",dis[i]);
//    }printf("\n");
//
//    for(int i = 0;i<n;i++){
//        for(int j = 0;j<pre[i].size();j++){
//            printf("%d ",pre[i][j]);
//        }printf("\n");
//    }

    DFS(d);

    for(int i = 0;i<best.size();i++){
        printf("%d ",best[best.size()-1-i]);
    }
    printf("%d %d",dis[d],minCost);
}

//A1031
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main(){
    string a;
    cin>>a;
    int length = a.size();
    int lines = (length+2)/3;   //total lines(include last)
    int width = length - lines*2;   //width-2
    for (int i = 0;i<lines-1;i++){
        cout<<a[i];
        for(int j = 0;j<width;j++){
            cout<<' ';
        }
        cout<<a[a.size()-1-i]<<endl;
    }
    for (int i = 0;i<width+2;i++){
        cout<<a[lines-1+i];
    }
    return 0;
}

//A1032 不会
#include <stdio.h>
#include <stdlib.h>
using namespace std;

struct node{
    int data;
    int next;
    bool flag;
};

int main(){
    node a[100010];
    int s1,s2,n;
    scanf("%d %d %d",&s1,&s2,&n);

    for (int i = 0;i<100010;i++){
        a[i].flag = 0;
    }

    int add,next;
    for(int i = 0;i<n;i++){
        scanf("%d %*c %d",&add,&next);
        a[add].next = next;
    }

    int p = s1;
    while(p!=-1){a[p].flag = 1;p = a[p].next;}
    p = s2;
    while(p!=-1){
        if (a[p].flag == 1)break;
        p = a[p].next;
    }
    if (p!=-1)printf("%05d",p);
    else printf("-1");
    return 0;
}

//A1033 TODO 4/7
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct{
    double price,distance;
} station;

bool cmp(station a,station b){
    if (abs(a.distance-b.distance)>0.01)return a.distance<b.distance;
    else return a.price<b.price;
}
bool cmp2(station a,station b){
    if (abs(a.price-b.price)>0.01)return a.price<b.price;
    else return a.distance<b.distance;
}

int main(){
    double cmax,distance,davg,n;
    scanf("%lf%lf%lf%lf",&cmax,&distance,&davg,&n);
    vector<station>gas;
    gas.resize(n);
    for(int i = 0;i<n;i++){scanf("%lf %lf",&gas[i].price,&gas[i].distance);}
    sort(gas.begin(), gas.end(), cmp);

//    cout<<endl;
//    for(int i = 0;i<n;i++){printf("%.2lf %.2lf\n",gas[i].price,gas[i].distance);}
//    cout<<endl;

    double maxdistance = 0,k = -1;
    double totalmoney = 0;
    int judgeall = 1;
    double nowleft = 0;
    for(int i = 0;i<n;i++){
        if (i == k){
            judgeall = 0;   // 如果一开始0处没有，或者中间不够了，则judgeall=1，不输出money

            // 判断是否为最后一段路
            if(distance < (cmax * davg + gas[i].distance)){
                totalmoney += gas[i].price * ((distance-gas[i].distance) /davg-nowleft);
//                cout<<"\n  money3+"<< gas[i].price * ((distance-gas[i].distance) /davg-nowleft)<<' ';
                break;}

            // 找到可达最便宜的
            int judge = 0;
            double minprice = 100;
            for(int j = i+1;j<n;j++){
//                cout<<"  "<<gas[j].distance <<' '<< nowleft * davg<<endl;;
                if(gas[j].distance <= (nowleft * davg + cmax * davg + gas[i].distance)){
                    if (gas[j].price < minprice){minprice = gas[j].price;k = j;judge = 1;
                    }
                }
            }

//            cout<<i<<' '<<gas[k].price<<' '<<gas[k].distance<<' ';
            if (judge == 0){printf("The maximum travel distance = %.2lf",maxdistance+cmax*davg);judgeall = 1;break;}


            if(minprice<gas[i].price){  // 后面有更便宜的，油加到那里即可
                totalmoney += gas[i].price * ((gas[k].distance - gas[i].distance) /davg - nowleft);
//                cout<<"\n  money1+"<< gas[i].price * ((gas[k].distance - gas[i].distance) /davg - nowleft)<<' ';
                nowleft = 0;
            }
            else{   //当前最便宜，加满
                totalmoney += gas[i].price * (cmax - nowleft);
                nowleft = cmax - (gas[k].distance - gas[i].distance)/davg;
//                cout<<"\n  money2+"<< gas[i].price * (cmax - nowleft)<<' ';
            }
            maxdistance += gas[k].distance - gas[i].distance;


//            cout<<totalmoney<<endl;
        }
        else if (k<0){
            int sgn = 0;
            for(int j = 0;j<n;j++){if (gas[j].distance<0.00001)sgn = 1;}
            if (sgn == 1){k = 0;i-=1;}
            else {cout<<"The maximum travel distance = 0.00";break;}
            // 测试点2为没有0号加油站
        }


    }
    if (judgeall == 0)printf("%.2lf",totalmoney);
    return 0;
}

//A1034 $ 25/30 TODO 5/6
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 50000;

struct node {
    int v,w;
    node(int _v,int _w):v(_v),w(_w){}
};

vector<node>adj[maxn];
int vis[maxn] = {0},nodeWeight[maxn] = {0},gs[maxn] = {0},gcount[maxn] = {0},gleader[maxn] ={-1},gleaderweight[maxn] ={0};

void DFS(int u,int depth,int group){
    vis[u] = group;
    gcount[group]++;
    for(int i = 0;i<adj[u].size();i++){
        gs[group] += adj[u][i].w/2;
        if (vis[adj[u][i].v] == 0)
            DFS(adj[u][i].v,depth+1,group);

    }
}

int DFSTravel(int n){
    int group = 1;
    for(int i = 0;i<maxn;i++){
        if (vis[i]==0 && adj[i].size()>0){
            DFS(i,1,group);
            group +=1;
        }
    }
    return group;
}

void process(char a[],char b[],int w){
    int anum = 0,bnum = 0;
    for(int i = 0;i<3;i++){
        anum = anum*26 + (int)(a[i]-'A');
        bnum = bnum*26 + (int)(b[i]-'A');
    }
//    printf("%d,%d,%d\n",anum,bnum,w);
    adj[anum].push_back(node(bnum,w));
    adj[bnum].push_back(node(anum,w));
}

void getsum(int k){
    int sum = 0;
    for(int i = 0;i<adj[k].size();i++){
        sum += adj[k][i].w;
    }
    nodeWeight[k] = sum;
}

void str(int i,char c[4]){
    int count = 2;
    while(count>=0){
        int a = i%26;
        i = i/26;
        c[count--] = (char)(a+'A');
    }

}

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i = 0;i<n;i++){
        char a[4],b[4];
        int w;
        scanf("%s %s %d",a,b,&w);
//        printf("--%s,%s\n",a,b);
        process(a,b,w);
    }

    int group = DFSTravel(n);

    for(int i = 0;i<maxn;i++){
        if (adj[i].size()!=0){
            getsum(i);
            if (nodeWeight[i]>gleaderweight[vis[i]]){
                gleaderweight[vis[i]] = nodeWeight[i];
                gleader[vis[i]] = i;
            }
        }
    }

//    printf("gid glen  id  idTimes records");
//    for(int i = 0;i<maxn;i++){
//        if (adj[i].size()!=0){
//            printf("\n%d %4d %6d %4d   |%5d %2d ",vis[i],gcount[vis[i]],gleader[vis[i]],gs[vis[i]],i,nodeWeight[i]);
//            for(int j = 0;j<adj[i].size();j++){
//                printf("%5d-%2d ",adj[i][j].v,adj[i][j].w);
//            }
//        }
//    }

    int countgroup = 0;
    for(int i = 0;i<group;i++){
        if (gcount[i]>2 && gs[i]>k)countgroup++;
    }
    printf("%d\n",countgroup);
    for(int i = 0;i<group;i++){
        if (gcount[i]>2 && gs[i]>k){
            char c[4];
            str(gleader[i],c);
            printf("%s %d\n",c,gcount[i]);
        }
    }
    return 0;
}

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

int main(){
    int n;
    cin>>n;
    string a[n],b[n];
    vector<int>c;
    c.resize(n);
    int sgn = 0,count = 0;
    for(int i = 0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<b[i].size();j++){
            if (b[i][j] == 'l') {
                b[i][j] = 'L';
                c[i] = 1;
                sgn = 1;}
            if (b[i][j] == '1') {
                b[i][j] = '@';
                c[i] = 1;
                sgn = 1;}
            if (b[i][j] == '0') {
                b[i][j] = '%';
                c[i] = 1;
                sgn = 1;}
            if (b[i][j] == 'O') {
                b[i][j] = 'o';
                c[i] = 1;
                sgn = 1;}
        }
        if (c[i] == 1) count++;
    }
    if (sgn == 0 && n == 1 ) cout<<"There is 1 account and no account is modified";
    else if (sgn == 0 && n > 1 ) cout<<"There are "<<n<<" accounts and no account is modified";
    else{
        cout<<count<<endl;
        for(int i = 0;i<n;i++){
            if (c[i]>0){
                cout<<a[i]<<' '<<b[i]<<endl;
            }
        }
    }
    return 0;
}

//A1036
// 一开始零分，是由于输入的问题。string输入需谨慎啊
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct{
    char name[20],class1[20];
    int score;
    char gender;
}man;

bool cmp(man a,man b)
{
    //'>'降序排序
    //'<'升序排序
    if(a.score>b.score)
    {
        return true;
    }
    return false;
}

int main(){
    int n;
    cin>>n;
    man people[n];
    for (int i = 0;i<n;i++){
        scanf("%s %s %s %d" ,people[i].name,&people[i].gender,people[i].class1,&people[i].score);
    }
    sort(people, people+n,cmp);
    int m = 1,f = 1,k = 0,mi = 0,fi = 0;
    for(int i = 0;i<n;i++){
        if(people[i].gender == 'F'){
            cout<<people[i].name<<' '<<people[i].class1<<endl;
            fi = i;
            f = 0;
            break;
        }
    }
    if (f == 1){
        cout<<"Absent"<<endl;
        k = 1;
    }
    for(int i = 0;i<n;i++){
        if(people[n-1-i].gender == 'M'){
            cout<<people[n-1-i].name<<' '<<people[n-1-i].class1<<endl;
            mi = n-1-i;
            m = 0;
            break;
        }
    }
    if (m == 1){
        cout<<"Absent"<<endl;
        k = 1;
    }
    if(k == 1) cout<<"NA";
//    else cout<<people[fi].score<<' '<<people[mi].score<<abs(people[fi].score-people[mi].score);
    else cout<<abs(people[fi].score-people[mi].score);
    return 0;
}

//A1036
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

typedef struct{
    char name[20],class1[20];
    int score;
}man;

bool cmp(man a,man b)
{
    //'>'降序排序
    //'<'升序排序
    if(a.score>b.score)
    {
        return true;
    }
    return false;
}

int main(){
    int n;
    cin>>n;
    man tmp,m,f;
    char gender;
    m.score = 101;
    f.score = -1;
    for (int i = 0;i<n;i++){
        scanf("%s %c %s %d" ,tmp.name,&gender,tmp.class1,&tmp.score); //NOTE1
        if(gender == 'F' && tmp.score>f.score) f = tmp;
        else if(gender == 'M' && tmp.score<m.score) m = tmp;
    }

    if (f.score == -1) cout<<"Absent";
    else cout<<f.name<<' '<<f.class1;
    cout<<endl;
    if (m.score == 101) cout<<"Absent";
    else cout<<m.name<<' '<<m.class1;
    cout<<endl;
    if (m.score == 101 || f.score == -1)cout<<"NA";
    else cout<<abs(f.score-m.score);

    return 0;
}