2020软院算法组新生周练 - 第三周

A. 神的预言（Easy）

Problem Description

大陆上里有这样一则遥远的预言，神之子将降临与世间，所有的恶与罪将在神之子的剑下化为灰烬。你作为森罗大陆的勇士需要承担起和神之子沟通的使命，传言中神界使用的语言是m进制数，所以神之子也使用m进制数，因为神之子过于强大，他不屑与学习其他语言，作为勇士的你需要将当地的语言：10进制数翻译为神之子听得懂的m进制数。你能做到吗？由于恶势力过于庞大，会有多个情报向神之子报告，每个情报为一个十进制数n，你需要翻译成m进制数。

Input

多组输入
对于每组输入，输入两个数n，m，含义如题所示，
超出10进制的字母用大写字母表示。
保证 0 <= n <= 100000 , 2 <= m <= 16，n，m为10进制数。

Output

输出进制转化后的数

Same input

5 2
5 3
5 4
30 16

Same output

101
12
11
1E

标程

#include<stdio.h>

int main(){
    int n,m;
    int ans[1000];
    while(~scanf("%d%d",&n,&m)){
        int i = 0;
        while(n){
            ans[i++] = n%m;
            n /= m;
        }
        for(int j = i-1 ; j >= 0 ; --j){
            if(ans[j] < 10) printf("%d",ans[j]);
            else printf("%C",'A' + ans[j] - 10);
        }
        if(i == 0) printf("0");
        puts("");
    }
}

B. 神的预约（Hard）

Problem Description

丛林里有这样一则遥远的预言，神之子将降临与世间，所有的恶与罪将在神之子的剑下化为灰烬。你作为森罗大陆的勇士需要承担起众多大陆和神之子沟通的使命，传言中神界使用的语言是m进制数，所以神之子也使用m进制数，因为神之子过于强大，他不屑与学习其他语言，作为勇士的你需要将当地的语言：k进制数翻译为神之子听得懂的m进制。你能做到吗？由于恶势力过于庞大，会有多个情报向神之子报告，每个情报为一个k进制数n，你需要翻译成m进制数。

Input

多组输入
对于每组数据，输入三个数n，m，k，含义如题所示
超出10进制的字母用大写字母表示
保证 0 <= n <= 100000 , 2 <= m，k <= 16，m，k为10进制数，n为k进制数。

Output

输出进制转化后的数

Same input

5 2 10
5 3 10
5 4 10
30 16 10

Same output

101
12
11
1E

标程

#include <stdio.h>
#include <string.h>
int main() {
    char n[1005];
    int m, k;
    while (~scanf("%s%d%d", n, &m, &k)) {
        int x = 0, len = strlen(n);
        for (int i = len - 1, w = 1; i >= 0; --i, w *= k)
            if (n[i] >= 'A') x += w * (10 + n[i] - 'A');
            else x += w * (n[i] - '0');
        if (!x) { puts("0"); continue; }
        int a[1005], p = 0;
        while (x) a[p++] = x % m, x /= m;
        while (p--)
            if (a[p] >= 10) putchar(a[p] - 10 + 'A');
            else putchar('0' + a[p]);
        putchar('\n');
    }
    return 0;
}

C码头的箱子

Problem Description

码头集装箱上有很多箱子，咕咕咕想把码头箱子放到仓库里，码头上有太多箱子了，所以可以看做无穷个。现在仓库里有 n 堆箱子，每堆箱子分别有 a1，a2，a3，a4....an 个，他每次只能从码头搬动一个箱子到仓库，因为箱子实在是太重了，他每天最多只能搬动k个箱子，咕咕咕工作一天后想要仓库里的每堆箱子最大数和最小数的差值最大，这样问这个差值最大是多少。（注：可以不搬满k次）

Input

多组输入
第一行包含两个整数。n和k (2≤n≤1000000,1≤k≤50000 )-序列中的元素数和可以执行操作的最大次数。
第二行包含一个整数序列。a1,a2,…,an (1≤ai≤10000000000 ).

Output

操作次数不超过 k 次.请输出序列中的最大元素个数和最小元素个数之间的最大可能差值。

Same input

4 5
3 1 7 5
3 10
100 100 100
10 9
4 5 5 7 5 4 5 2 4 3

Same output

9
10
14

标程

#include<stdio.h>

int main(){
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        long long tmp;
        long long maxn = -1,minn = 10000000005;
        for(int i = 0 ; i < n ; ++i){
            scanf("%lld",&tmp);
            if(tmp > maxn) maxn = tmp;
            if(tmp < minn) minn = tmp;
        }
        printf("%lld\n",maxn - minn + k);
    }
}

D咕咕咕念数字（Easy）

Problem Description

Bernard学长和咕咕咕学长是好同学,两个人经常一起打比赛，比赛时候
咕咕咕学长负责读题，现在有很多组数字，咕咕咕学长要把它读出来给Bernard学长听。

input

先输入一个整数t(0<t<20),表示共有t组测试数据.
然后有t行,每行一个自然数n(0<=n<1000).

output

输出整数n的中文读法
每组输出占一行

Same input

7
3
10
19
24
465
780
900

Same output

七
三
一十
一十九
二十四
四百六十五
七百八十
九百

标程

#include<stdio.h>

void speak(int x){
    switch (x){
    case 1 : printf("一"); break;
    case 2 : printf("二"); break;
    case 3 : printf("三"); break;
    case 4 : printf("四"); break;
    case 5 : printf("五"); break;
    case 6 : printf("六"); break;
    case 7 : printf("七"); break;
    case 8 : printf("八"); break;
    case 9 : printf("九"); break;
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        if(n == 0) printf("零")
        if(n >= 100){
            speak(n/100);
            printf("百");
            n %= 100;
            if(n > 0 && n < 10) printf("零");
        }
        if(n >= 10){
            speak(n/10);
            printf("十");
            n %= 10;
        }
        if(n > 0){
            speak(n);
        }
        puts("");
    }
}

D咕咕咕念数字（Hard）

Problem Description

Bernard学长和咕咕咕学长是好同学,两个人经常一起打比赛，比赛时候
咕咕咕学长负责读题，现在有很多组数字，咕咕咕学长要把它读出来给Bernard学长听。

input

先输入一个整数t(0<t<60),表示共有t组测试数据.
然后有t行,每行一个自然数n(0<=n<100000).

output

输出整数n的中文读法
每组输出占一行

Same input

50555
50000
50500
50050
50005
50505
50055
55555

Same output

五万零五百五十五
五万
五万零五百
五万零五十
五万零五
五万零五百零五
五万零五十五
五万五千五百五十五