PAT_A分类题解

,

list:

vector的使用

1039 Course List for Student (25 分)
1047 Student List for Course (25 分)

set的使用

1063 Set Similarity (25 分)

string的使用

1060 Are They Equal (25 分)

map的使用

1100 Mars Numbers (20 分)
1054 The Dominant Color (20 分)
1071 Speech Patterns (25 分)

栈

1051 Pop Sequence (25 分)

队列

1056 Mice and Rice (25 分)

链表

1052 Linked List Sorting (25 分)
1074 Reversing Linked List (25 分)

简单模拟：

1042 Shuffling Machine (20 分)
1046 Shortest Distance (20 common.points)
1065 A+B and C (64bit) (20 分)
1002 A+B for Polynomials (25 分)

1039 Course List for Student (25 分)
题目链接
思路：
注意vector selectCourse[M]和vector selectCourse是不一样的东西。前者相当于是二维数组，后者相当于一维数组。
将学生姓名通过getid函数使每一个姓名都与一个数字相关联（类似hash表的思想）以此数字作为selectCourse的下标，用数组selectCourse[i]去存储对应学生所选课程的编号。
注意vector的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int N=40010;
const int M=26*26*26*10+1;
vector<int> selectCourse[M];//用来存储这个学生所选择的课程编号

int getid(char name[]){//将name转换为数字
    int id=0;
    for(int i=0;i<3;i++){
        id=id*26+(name[i]-'A');
    }
    id=id*10+(name[3]-'0');
    return id;
}
int main(){
    char name[5];
    int n,k;//人数和课程数
    scanf("%d%d",&n,&k);
    for(int i=0;i<k;i++){
        int course,x;//课程编号，以及选了这门课的人数
        scanf("%d%d",&course,&x);
        for(int j=0;j<x;j++){
            scanf("%s",name);
            int id=getid(name);//将学生名变为id
            selectCourse[id].push_back(course);//将课程编号加入这个学生数组中
        }
    }

    for(int i=0;i<n;i++){
        scanf("%s",name);
        int id=getid(name);
        sort(selectCourse[id].begin(),selectCourse[id].end());
        printf("%s %d",name,selectCourse[id].size());
        for(int j=0;j<selectCourse[id].size();j++){
            printf(" %d",selectCourse[id][j]);//这里注意
        }
        printf("\n");
    }
    return 0;
}

1047 Student List for Course (25 分)
题目链接
思路：
此题的思想与上一题差不多，不过定义的name数组是二维数组，输出name字符串的方法要注意一下，要能透彻的理解vector类似是一个可变长的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=40010;
const int maxc=2510;
vector<int> course[maxc];//存储选定某门课的学生的编号
char name[maxn][5];
int n;//选特定课的人数

bool cmp(int a,int b){
    return strcmp(name[a],name[b])<0;
}
int main(){
    int renshu,kechengshu,kebianhao;
    scanf("%d%d",&renshu,&kechengshu);//输入总人数和总课程个数
    for(int i=0;i<renshu;i++){
        scanf("%s %d",name[i],&n);//输入姓名，和总选课程数
        for(int j=0;j<n;j++){
            scanf("%d",&kebianhao);//输入每一个选择的课程编号
            course[kebianhao].push_back(i);
				//以课程编号作为此数组的下标，里面存的是对应的name数组的下标
        }
    }
    //下面开始输出
    for(int i=1;i<=kechengshu;i++){
        printf("%d %d\n",i,course[i].size());
        sort(course[i].begin(),course[i].end(),cmp);
        for(int j=0;j<course[i].size();j++){
            printf("%s\n",name[course[i][j]]);
			//课程编号为i的course中，以j循环输出选了这门课的学生的名字，
            //course[i][j]是上文中push_back的i，即为name[i]中的i
			//每个i对应了一个输入的name字符串
        }
    }
    return 0;
}

1063 Set Similarity (25 分)
题目链接
思路：
用set存储输入的数字，可以去重，然后用compare函数去对比两个不同的集合中的数字是否相同，如果相同，就使samen++,如果不同，就说明使一个新的元素，所以就让totaln++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<set>
using namespace std;
const int n=55;
set<int> st[n];
void compare(int x,int y){
    int totaln=st[y].size(),samen=0;
    for(set<int>::iterator it =st[x].begin();it!=st[x].end();it++){
        if(st[y].find(*it)!=st[y].end())    samen++;
        else    totaln++;
    }
    printf("%.1f%\n",samen*100.0/totaln);
}

int main(){
    int setn,setinn;//集合个数，集合中元素的个数
    int setshu;//集合中的数
    scanf("%d",&setn);
    for(int i=1;i<=setn;i++){
        scanf("%d",&setinn);
        for(int j=0;j<setinn;j++){
            scanf("%d",&setshu);
            st[i].insert(setshu);
        }
    }
    int duibishu,set1,set2;
    scanf("%d",&duibishu);
    for(int i=0;i<duibishu;i++){
        scanf("%d%d",&set1,&set2);
        compare(set1,set2);
    }
}

1060 Are They Equal (25 分)
题目链接
思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<string>
using namespace std;
int n;
string deal(string s,int &e){
    int k=0;//s的下标
    while(s.length()>0&&s[0]=='0'){
        s.erase(s.begin());
    }
    if(s[0]=='.'){
        s.erase(s.begin());
        while(s.length()>0&&s[0]=='0'){
            s.erase(s.begin());
            e--;
        }
    }else{
        while(k<s.length()&&s[k]!='.'){
            k++;
            e++;
        }
        if(k<s.length()){
            s.erase(s.begin()+k);
        }
    }
    if(s.length()==0){
        e=0;
    }
    int num=0;
    k=0;
    string res;
    while(num<n){
        if(k<s.length())    res+=s[k++];
        else res+='0';
        num++;
    }
    return res;
}
int main(){
    string s1,s2,s3,s4;
    cin>>n>>s1>>s2;
    int e1=0,e2=0;
    s3=deal(s1,e1);
    s4=deal(s2,e2);
    if(s3==s4&&e1==e2){
        cout<<"YES 0."<<s3<<"*10^"<<e1<<endl;
    }else{
        cout<<"NO 0."<<s3<<"*10^"<<e1<<" 0."<<s4<<"*10^"<<e2<<endl;
    }
    return 0;
}```
<a name="a5">1100 Mars Numbers (20 分)</a>
<a href="https://pintia.cn/problem-sets/994805342720868352/problems/994805367156883456">题目链接</a>
思路：
```c++
#include<stdio.h>
#include<iostream>
#include<string>
#include<map>
using namespace std;
string shuzi[13]={"tret","jan","feb","mar","apr","may","jun",
		"jly","aug","sep","oct","nov","dec"};
string beishuzi[13]={"tret","tam","hel","maa","huh","tou",
		"kes","hei","elo","syy","lok","mer","jou"};

string numtostr[170];//数字与火星文的映射
map<string,int> strtonum;//火星文与数字的映射
void init(){ 
    for(int i=0;i<13;i++){
        numtostr[i]=shuzi[i];//只有个位时，数->火星文
        strtonum[shuzi[i]]=i;//个位时，火星文->数
        numtostr[i*13]=beishuzi[i];//有十位时且个位为0时，数->火星文
        strtonum[beishuzi[i]]=i*13;//有十位时且个位为0时，火星文->数
    }
    //都不为0时
    for(int i=1;i<13;i++){//十位
        for(int j=1;j<13;j++){//个位
            string str=beishuzi[i]+" "+shuzi[j];
            numtostr[i*13+j]=str;//十位和个位都不为0的情况，数字->火星文
            strtonum[str]=i*13+j;//十位和个位都不为0的情况，火星文->数字
        }
    }
}
int main(){
    init();
    int geshu;
    scanf("%d%*c",&geshu);
    while(geshu--){
        string str;
        getline(cin,str);//
        if(str[0]>='0'&&str[0]<='9'){//如果是数字（这里的数字形式是字符串形式）
            int num=0;
            for(int i=0;i<str.length();i++){
                num=num*10+(str[i]-'0');//就先算出这个字符串代表的数字的值是多少
            }
            cout<<numtostr[num]<<endl;//输出这个数字值对应的火星文
        }else{
            cout<<strtonum[str]<<endl;//如果是火星文，直接查表输出对应的数字值，
        }
    }
    return 0;

}

1054 The Dominant Color (20 分)
题目链接
思路:用map比较方便，map是这个数字值与这个数字出现的次数的映射。
注意it迭代器，it->first是数字，it->second是次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<map>
using namespace std;
int main(){
    int hang,lie,col;
    scanf("%d%d",&hang,&lie);
    map<int,int>count;
    for(int i=0;i<hang;i++){
        for(int j=0;j<lie;j++){
            scanf("%d",&col);
            if(count.find(col)!=count.end())    count[col]++;//若已存在此数，个数就加一
            else    count[col]=1;//若不存在，就置为1
        }
    }
    int k=0,max=0;//最大数字值，该数字值出现的次数
    for(map<int,int>::iterator it=count.begin();it!=count.end();it++){
        if(it->second > max){
            k=it->first;//获取第一个关键字，即数字
            max=it->second;//获取第二关键字，即这个数字出现的次数
        }
    }
    printf("%d\n",k);
    return 0;
}

1071 Speech Patterns (25 分)
题目链接
思路：
与上一题的思路一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#include<iostream>
#include<map>
#include<string>
using namespace std;

bool check(char c){
    if(c>='0'&&c<='9')  return true;
    if(c>='A'&&c<='Z')  return true;
    if(c>='a'&&c<='z')  return true;
    return false;
}

int main(){
    map<string,int> count;
    string str;
    getline(cin,str);
    int i=0;
    while(i<str.length()){//
        string word;
        while(i<str.length()&&check(str[i])==true){
            if(str[i]>='A'&&str[i]<='Z'){
                str[i]+=32;//大写字母转为小写字母
            }
            word+=str[i];//将这个字符加入到这个单词中
            i++;//小标后移一位
        }
        if(word!=""){//单词非空的前提下，计算个数
            if(count.find(word)==count.end())   count[word]=1;//如果此单词不存在，就让个数为1
            else    count[word]++;//如果此单词存在，就将个数加一
        }
        while(i<str.length()&&check(str[i]==false)){
            i++;//跳过非单词字符
        }
    }

    //输出最多次数的单词，以及此单词的个数
    string ans;
    int max=0;
    for(map<string,int>::iterator it=count.begin();it!=count.end();it++){
        if(it->second>max){
            max=it->second;
            ans=it->first;
        }
    }
    cout<<ans<<" "<<max<<endl;
    return 0;
}

1051 Pop Sequence (25 分)
题目链接
思路：
用数组存储输入的数字，用current去指向每一个待出栈元素
最里面一层的while语句是核心判定方法，while循环会一直判定栈顶元素是不是与出栈序列中的current指向的元素相同。如果相同就出栈，如果不同了才会去执行外层的for循环，如果此时for循环成立，则才会再执行st.push(i)语句,即入栈。这里不要理解错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<stack>
using namespace std;
const int maxn=1010;
int arr[maxn];
stack<int> st;
int main(){
    int m,n,t;
    scanf("%d%d%d",&m,&n,&t);
    while(t--){
        while(!st.empty()){
            st.pop();//清空栈
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&arr[i]);//读入数据
        }
        int current=1;//指向出栈序列中的待出栈元素
        bool flag=true;
        for(int i=1;i<=n;i++){
            st.push(i);//入栈
            if(st.size()>m){//栈中元素个数超过上限
                flag=false;
                break;
            }
            while (!st.empty()&&st.top()==arr[current]){//核心判断
                st.pop();//出栈
                current++;
            }  
        } 
        if(st.empty()==true&&flag==true){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
}

1056 Mice and Rice (25 分)
题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
#include<queue>
using namespace std;
const int maxn=1010;
struct mouse{
    int weight;
    int r;
}mouse[maxn];
int main(){
    int np,ng,order;
    scanf("%d%d",&np,&ng);
    for(int i=0;i<np;i++){
        scanf("%d",&mouse[i].weight);
    }
    queue<int> q;
    for(int i=0;i<np;i++){
        scanf("%d",&order);
        q.push(order);
    }
    int temp=np,group;//temp是当前轮的参赛老鼠数，group是当前轮的组数
    while(q.size()!=1){
        if(temp%ng==0)  group=temp/ng;//计算出组数
        else group=temp/ng+1;//计算出组数，如不能整除，就加一组
        for(int i=0;i<group;i++){
            int k=q.front();//k存放最大质量的老鼠的编号
            for(int j=0;j<ng;j++){//组内找出最大质量
                if(i*ng+j>=temp)    break;//此为最后一组时的情况
                int front=q.front();//队首老鼠的编号
                if(mouse[front].weight>mouse[k].weight){
                    k=front;//找出这组中最大质量的老鼠
                }
                mouse[front].r=group+1;
                q.pop();//
            }
            q.push(k);
        }
        temp=group;//下一轮老鼠的总数为group
    }
    mouse[q.front()].r=1;
    for(int i=0;i<np;i++){
        printf("%d",mouse[i].r);
        if(i<np-1)  printf(" ");
    }
    return 0;
}

1052 Linked List Sorting (25 分)
题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct Node{
    int address,data,next;//地址，数据，下一个地址
    bool flag;
}node[maxn];

//无效结点指的是那些不在链表上的结点
bool cmp(Node a,Node b){
    if(a.flag==false||b.flag==false){
        return a.flag>b.flag;//有无效结点，且把无效结点放在后面
        //无效结点的flag=0,有效结点的flag为1，所以能实现把无效结点放在后面
    }else{
        return a.data<b.data;//都是有效结点，则按要求排序,即按数据从小到大的排序
    }
}
int main(){
    for(int i=0;i<maxn;i++){
        node[i].flag=false;//初始化
    }
    int n,begin,address;
    scanf("%d%d",&n,&begin);//输入个数和开始结点
    for(int i=0;i<n;i++){
        scanf("%d",&address);//输入地址
        scanf("%d%d",&node[address].data,&node[address].next);
        node[address].address=address;
    }
    int count=0,p=begin;
    while(p!=-1){
        node[p].flag=true;
        count++;
        p=node[p].next;
    }
    if(count==0){
        printf("0 -1");//均为无效结点的情况
    }else{
        sort(node,node+maxn,cmp);
        printf("%d %05d\n",count,node[0].address);
        for(int i=0;i<count;i++){
            if(i!=count-1){//  %05d不能正确的输出-1
                printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
            }else{
                printf("%05d %d -1\n",node[i].address,node[i].data);
            }
        }
    }
    return 0;
}

1074 Reversing Linked List (25 分)
题目链接
思路：
将有效结点按照order从0开始排列，无效结点的order都是maxn，再通过sort排序，就可以将有效结点和无效结点排分开来。（要考虑到有无效结点的存在）

因为题目需要每k个结点就要反转一次，所以，我们可以将每k个结点看为一组，我们可以对每一组从后往前的输出结点，但是，关键是每一组的最后一个结点的next的处理：
如果i号结点（假设i号结点是一组中的最后一个结点）不在最后一个完整组中，那么i号结点的next就是（i+2）*k-1,即i+1组的最后一个结点。
如果i号结点是在最后一个完整组中，且其后没有不完整组了，则i的next为-1，
如果i号结点在最后一个不完整组中，且其后还有一组不完整组，则i的next为（i+1)*k，即为不完整组中的第一个结点。
此题输出的格式处理较麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct Node{
    int address,data,next;
    int order;//此为链表上的序号，无效结点的序号规定为maxn
}node[maxn];
bool cmp(Node a,Node b){
    return a.order<b.order;
}

int main(){
    for(int i=0;i<maxn;i++){
        node[i].order=maxn;//全部先初始化为无效结点
    }
    int begin,n,k,address;
    scanf("%d%d%d",&begin,&n,&k);//起始地址，结点个数，步长
    for(int i=0;i<n;i++){
        scanf("%d",&address);
        scanf("%d%d",&node[address].data,&node[address].next);
        node[address].address=address;
    }

    int p=begin,count=0;
    while(p!=-1){//对链表上的结点进行编号
        node[p].order=count++;
        p=node[p].next;
    }
    sort(node,node+maxn,cmp);
    n=count;

    for(int i=0;i<n/k;i++){//遍历n/k组
        for(int j=(i+1)*k-1;j>i*k;j--){//倒着输出
            printf("%05d %d %05d\n",node[j].address,node[j].data,node[j-1].address);
        }
        printf("%05d %d",node[i*k].address,node[i*k].data);
        if(i<n/k-1){
            printf("%05d\n",node[(i+2)*k-1].address);
        }else{
            if(n%k==0){
                printf("-1\n");
            }else{
                printf("%05d\n",node[(i+1)*k].address);
                for(int i=n/k*k;i<n;i++){
                    printf("%05d %d ",node[i].address,node[i].data);
                    if(i<n-1){//这里的if-else是为了区分输出最后一个结点的address
                    //因为最后一个结点的address为-1，%05d不能正确输出-1
                        printf("%05d\n",node[i+1].address);
                    }else{
                        printf("-1\n");
                    }
                }
            }
        }
    }
    return 0;
}

1042 Shuffling Machine (20 分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
const int N=54; 
int originaln[N+1];//存放原始序列
int nextn[N+1]; //
int finallyn[N+1];//存放改变后的序列
char huase[5]={'S','H','C','D','J'};
int main(){
    //花色与牌号的关系是：
    //当牌号为x时：huase[(x-1)/13]为牌号对应的花色
    //（x-1）%13+1即为它在所属花色下的编号
    int k;
    scanf("%d",&k);
    for(int i=1;i<=N;i++){
        originaln[i]=i;//初始化牌的编号
    }
    for(int i=1;i<=N;i++){
        scanf("%d",&nextn[i]);
    }
    for(int step=0;step<k;step++){//执行k次
        for(int i=1;i<=N;i++){
             finallyn[nextn[i]]=originaln[i];//位置为j的牌号为originaln[j]，
            //要放在位置为nextn[j]上
        }
        for(int i=1;i<=N;i++){
            originaln[i]=finallyn[i];
        }
    }
    for(int i=1;i<=N;i++){
        if(i!=1)    printf(" ");
        //originaln[i]--;
        printf("%c%d",huase[(originaln[i]-1)/13],(finallyn[i]-1)%13+1);//这里要注意

    }
    return 0;
}

1046 Shortest Distance (20 common.points)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100005;
int pointers;

int chaxun;
int main(){
    int pointerzu[maxn];
    int shi=0,zhong=0,zongchang=0;
    int changbu=0;
    scanf("%d",&pointers);
    for(int i=0;i<pointers;i++){
        scanf("%d",&pointerzu[i]);
        zongchang+=pointerzu[i];
    }
    scanf("%d",&chaxun);
    for(int i=0;i<chaxun;i++){
        scanf("%d%d",&shi,&zhong);
        int chang=0;
        if(shi>zhong){
            // int temp=shi;
            // shi=zhong;
            // zhong=temp;
            swap(shi,zhong);
        }
        for(int j=shi-1;j<zhong-1;j++){
            chang+=pointerzu[j];         
        }
        changbu=zongchang-chang;
        if(changbu<chang){
            chang=changbu;
        }
        printf("%d\n",chang);
    }
    return 0;
}

上面的方法里面有for循环的嵌套，在运行的时候可能会运行超时，所以可以优化一下：

1065 A+B and C (64bit) (20 分)
注意：这题要注意溢出的判断，如果两个正数之和为负数，就为正溢出，如果两个负数相加为正数，就为负溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
int main(){
    long long a,b,c;
    int n;
    int tcase=1;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        long long res=a+b;
        bool flag;
        if(a>0&&b>0&&res<0) flag=true;//正溢出，
        else if(a<0&&b<0&&res>=0)   flag=false;//负溢出
        else if(res>c)  flag=true;
        else    flag=false;
        if(flag==true)  printf("Case #%d: true\n",tcase++);
        else    printf("Case #%d: false\n",tcase++);   
    }
    return 0;
}

1002 A+B for Polynomials (25 分)
思路：用数组下标作为次项，对应的数组中存放的是对应此项的系数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
const int maxn=1111;
double p[maxn]={};
int main(){
    int count=0;//个数
    int cixiang=0;//次项
    double a;
    
        scanf("%d",&count);
        for(int i=0;i<count;i++){
            scanf("%d %lf",&cixiang,&a);
            // scanf("%lf",&p[cixiang]);//该次项对应的系数
            p[cixiang]+=a;//注意这样写，直接输入系数，像上面那样是错的，因为遇到相同的次数的话，会覆盖掉之前存的系数
        }
        scanf("%d",&count);
        // double xishu;
        for(int i=0;i<count;i++){
            scanf("%d %lf",&cixiang,&a);
            p[cixiang]+=a;
			//下面为另一种实线思路：功能同p[cixiang]+=a,但是不简洁
            // if(!p[cixiang]==0){
            //     scanf("%lf",&xishu);
            //     p[cixiang]+=xishu;
            // }else{
            //     scanf("%lf",&p[cixiang]);
            // }
        }
        int shu=0;
        for(int i=0;i<maxn;i++){
            if(p[i]!=0) shu++;//统计有多少非零项
        } 
        printf("%d",shu);
        for(int i=maxn-1;i>=0;i--){
            if(p[i]!=0){
                printf(" %d %.1f",i,p[i]);
            }
        }
        return 0;
}