第二届 Hello World 程序设计竞赛题目

Hello_World

A. 舍罕王的反击

分值：20 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

舍罕王为了奖励发明国际象棋的人，允诺满足他一个条件，西萨 · 班 · 达依尔便提出，在棋盘的第一个格子放上一粒麦子，后面每个格子都放上前一个格子两倍数量的麦子，放满 $64$ 个格子就行，国王以为要不了多少粮食，就随口答应了。如果要完成这个承诺，国王总共需要拿出 $2^{64}-1=18446744073709551615$ 粒米，这完全是不可能的。
舍罕王为了挽尊，下定决心苦学等比数列，终于想到一个自信完全可以难倒达依尔的题目！并向达依尔提出，如果他无法回答这个问题，就可以收回之前的承诺，达依尔答应了。
“我说出一个正整数 $x$，只要你能够在今晚 $21:00$ 前算出最小的正整数 $q$，以及对应的 $n$，满足 $\sum_{i=1}^nq^{i-1}=x$（即首项为 $1$，公比为 $q$ 的等比数列前 $n$ 项和等于 $x$），你就可以获得所有粮食，否则我有权收回承诺。”
由于这个问题实在是太难了，达依尔一听到题目就认输了，机智如你能想到答案吗？

输入

输入为一个正整数 $x$，即舍罕王说出的整数。

输出

对于输入的整数，输出最小的正整数 $q$，以及对应的 $n$，满足 $\sum_{i=1}^nq^{i-1}=x$。

样例

说明

对于 $100\%$ 的数据，$1\leq x\leq10^9$
谁也不知道达依尔到底是不是真的想不出答案

B. 小班教学

分值：20 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

$Hello~World$ 程序设计协会决定对所有会员展开一次针对性的培训。协会有很多个会员，每个会员想学的编程语言都不一样。限制每个人只能在本次培训中学习一种编程语言，经过统计，会员们总共想学 $n$ 种编程语言，每种编程语言报名的人数分别为 $a_1,a_2,\cdots,a_n$。为了保证公平与方便管理，协会决定采用小班教学模式，所有的小班内人数相同，同一班级内语言的教学内容相同。由于人力有限，我们期望在满足以上前提条件的同时，班级数量尽可能地少，问：最少需要开多少个小班。

输入

第一行为一个整数 $n$，表示有 $n$ 种语言，第二行为 $n$ 个整数，每个整数之间用一个空格分隔，分别为 $a_1,a_3,\cdots,a_n$，表示每种语言的报名人数。

输出

输出最少需要开多少个小班。

样例

说明

对于 $50\%$ 的数据，$1\leq n\leq10^4,1\leq a_i\leq10^3$
对于 $70\%$ 的数据，$1\leq n\leq10^4,1\leq a_i\leq10^6$
对于 $100\%$ 的数据，$1\leq n\leq10^6,1\leq a_i\leq2^{31}-1$，答案不超过 int 能表示的范围

C. 小 Hi 的情书

分值：30 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：杨炳娜

题目描述

小HI想在 520 当天写情书给小 Yi 表白。但是小 Hi 很害羞，不希望别人看见这封情书，于是就利用一些规则对这封情书进行了加密，并将加密后的情书和加密法则送给了小 Yi。由于情书篇幅比较大，小 Hi 的加密法则解密起来过于烦琐，小 Yi 不能看懂，这样的话小 Hi 表白就失败了。小 Hi 拜托你去帮小 Yi 解密情书，使他表白成功！
已知小 Hi 的情书内容原文为一串不加标点的英文，如 "hello world my dear"。小 Hi 的加密法则为：

1. 对每个单词进行加密
2. 不改变单词的大小写
3. 针对每个单词，从第一个字母开始标序号，到最后一个字母，取出所有序号为奇数的字母，连起来作为加密后单词的前半部分。再倒着取出所有序号为偶数的字母，作为单词的后半部分

例如："abcdefg" 他加密后的前半部分为 "aceg"，加密后的后半部分为 "fdb"，整个字符串加密后为 "acegfdb"。

输入

第一行为一个整数 $n$，表示情书中总共有 $n$ 个单词，第二行为一串不带标点的字符串，单词仅包含大写字母与小写字母，每个单词之间用一个空格分隔，为加密后的情书。

输出

利用规则解密后的情书内容。

样例

说明

整篇情书的字母数量之和不大于 $5000$

D. 小 Hi 的 $RP$

分值：30 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：武玥彤

题目描述

第二届 $Hello~World$ 算法竞赛马上就要开始了，小 Hi 从一周前就开始紧张，他祈祷自己能够拿到满意的分数——这时候上帝出现了，告诉他其实每个人都有一个 $RP$ 值，并且以周为单位，在一周的开始，上帝给每个人每天都设了一个 $RP$ 值，$RP$ 值越高，他在这天就越幸运。
上帝给了小 Hi 一个机会，允许他可以调整自己的 $RP$ 值，若他将自己一周中某一天的 $RP$ 值增加 $1$，在一周的另一天他的 $RP$ 值必须要减少 $1$，他有无数次调整的机会，但是一旦确定下来，就不能改变，他接下来这一周就必须按照这个 $RP$ 值生活。在调整的过程中 $RP$ 值必须始终保持在区间 $[0,9]$ 以内，不能超出这个范围，且每天的 $RP$ 值都必须为整数。若小 Hi 每天严格遵守这样的 $RP$ 值生活，到比赛当天，他的比赛分数就等于过去 $7$ 天每一天 $RP$ 值的乘积，否则他将受到惩罚得到 $0$ 分。

输入

第一行为一个整数 $T$，表示有 $T$ 组数据，接下去 $T$ 行，每行 $7$ 个整数 $a_i$，第 $i$ 个整数表示第 $i$ 天小 Hi 的 $RP$ 值。

输出

输出小 Hi 能得到的最大的比赛分值。

样例

说明

对于 $50\%$ 的数据，$0\leq a_1+a_2+\cdots+a_7\leq20$
对于 $100\%$ 的数据，$1\leq T\leq100,0\leq a_i\leq9$

E. 小 Yi 的照片

分值：32 分 | 时间限制：2 s | 空间限制：262144 KB | 出题人：杨炳娜

题目描述

作为女孩子，小 Yi 一向对自己的照片很在意。一次旅游过程中，小 Yi 让小 Hi 帮她拍了很多风景照，但是直男小 Hi 拍的都很直男。 为了不让小 Yi 生气，小 Hi 决定对图片进行美颜后再发给小 Yi，但是小 Hi 并不会使用美颜软件，他决定自己写一个磨皮程序，对小 Yi 的照片进行美颜，你能帮帮小 Hi 吗?
小 Hi 在经过了解后，知道了图片的磨皮是在提取了图片各像素点的的像素值之后，对这些像素值组成的矩阵进行中值滤波去噪处理。
中值滤波是对一个滑动窗口内的诸像素灰度值排序，用其中值代替窗口中心像素的原来灰度值，它是一种非线性的图像平滑法，滤波后的数据保留原图像的变化趋势，同时去除了尖峰脉冲对分析造成的影响。
将原图片的灰度值提取出来后，得到一个 $n\times m$ 的灰度值矩阵，对该矩阵进行以下操作后，得到一个新的灰度值矩阵：

1. 对于原矩阵中每一个大小为 $s\times s$（$s$ 为奇数）的子矩阵，若其中心坐标为 $(x,y)$，则新矩阵 $(x,y)$ 处的值等于子矩阵内所有数字的中位数；
2. 新矩阵中其他数字等于原矩阵内的数字。

以一维信号的中值滤波举例。对灰度序列 $80,120,90,200,100,110,70$，如果按大小顺序排列，其结果为 $70,80,90,100,110,120,200$，其中间位置上的灰度值为 $100$，则该灰度序列的中值即为 $100$。一维信号中值滤波实际上就是用中值代替规定位置（一般指原始信号序列中心位置）的信号值。对前面所举的序列而言，中值滤波的结果是用中值 $100$ 替代序列 $80,120,90,200,100,110,70$ 中的信号序列中心位置值 $200$，得到的滤波序列就是 $80,120,90,100,100,110,70$。在此序列中 $200$ 是一个噪声信号，则用此方法即可去除这个噪声点。
上面的例子所使用的滤波窗口大小为 $7$，如果窗口大小为 $3$，则中值滤波的结果为 $80,90,120,100,110,100,70$。
小 Hi 已经获得了小 Yi 图片的像素值，请你帮助他，建立一个 $s\times s$（$s$ 为奇数）的滤波窗口，以窗口中所有数字的中位数作为中值，替换窗口中心位置的数字，把小 Yi 的图片成功的进行磨皮处理。

输入

第一行三个整数 $n, m, s$，分别表示像素矩阵的行数、列数与滑动窗口的大小。
接下来 $n$ 行，每行 $m$ 个整数。每个整数在 $[0,255]$ 范围内，为图片各位置的的像素点灰度值。

输出

$n$ 行，每行 $m$ 个数，数字之间用一个空格隔开。
为处理好的图片各位置的像素点值。

样例

提示

对于 $75\%$ 的数据，$1\leq n,m\leq100,1\leq s\leq 5$
对于 $100\%$ 的数据，$1\leq n,m\leq500,1\leq s\leq10$，$s\leq\min(n,m)$，且 $s$ 为奇数
你可能需要头文件 algorithm 提供排序函数：
void sort(int *begin, int *end) 对地址在 [begin, end) 区间的数字按从小到大进行排序，用法如下：

#include <stdio.h>
#include <algorithm>            // 头文件
using namespace std;            // 命名空间
int main() {
    int num[] = {3, 2, 1, 5, 7};
    sort(num, num + 5);         // 排序
    for(int i = 0; i < 5; ++i) {
        printf("%d ", num[i]);  // 输出排序后的数组
    }
    return 0;
}

F. 星际穿越

分值：40 分 | 时间限制：12 s | 空间限制：262144 KB | 出题人：孙昊哲

题目描述

阿尔法星上面环绕了一个传送站可以把资源传送回遥远的地球，传送站的轨道可以认为是一个椭圆，它的长轴与短轴分别为 $a$ 与 $b$，以椭圆的中心为原点，两个焦点所在直线为 $x$ 轴，椭圆所在平面为 $xOy$ 平面，则可以建立空间直角坐标系，现在由于 $shz$ 飞船上的燃料快用完了，所以只要尽快进入椭圆的轨道就可以等待飞船与传送站相遇。
现在 $shz$ 给出了自己的坐标 $(x_0,y_0,0)$，他想知道自己需要航行多远才能进入轨道。

输入

第一行为一个整数 $T~(1\leq T\leq100)$，接下来有 $T$ 组数据，每组数据为四个整数 $a,b,x_0,y_0~(0<b\leq a\leq50,-50\leq x_0,y_0\leq50)$，分别表示椭圆的长轴与短轴，以及 $shz$ 飞船的坐标 $(x_0,y_0,0)$。

输出

到达传送站轨道的最短距离（答案保留 $2$ 位小数）。

样例

G. 送分题 贴代码

分值：40 分 | 时间限制：3 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

延续第一届 $Hello~World$ 算法竞赛的优良传统，一场比赛中我们必须要有一道非常友好的送分题，目的在于让我们的选手有极致的参赛体验——即使其他所有题目都不会，至少有一道题能够让他拿到保底分数，去年我们要解决的是 $A+B$ 的问题，显然今年的送分题看起来更酷炫：
对于一个包含 $n$ 个整数的数组 $A$，数组的下标范围为 $[1,n]$，且 $\forall i\in[1,n],~A_i=n-i+1$（即一个形如 $\{n,n-1,n-2,\cdots,3,2,1\}$ 的倒序数组），对该数组使用归并排序使得最终得到一个顺序数组（也就是 $\forall i\in[1,n],~A_i=i$），问在排序过程中总共需要进行多少次数字的大小比较操作？
由于这个问题实在是太酷炫了，把我们的吉祥物小 Hi 难倒了，于是他向我们协会的另一个吉祥物小 Yi 请教，作为数据结构 $Master$，小 Yi 不出三分钟就给出了代码：

#include <stdio.h>
#include <stdlib.h>
int Merge(int *num, int l, int m, int r) {
    int cnt = 0;
    int Index = 0;
    int Index1 = l;
    int Index2 = m + 1;
    int *tmp = (int*)malloc(sizeof(int) * (r - l + 1));
    while(Index1 <= m && Index2 <= r) {
        ++cnt;
        if(num[Index1] < num[Index2]) {
            tmp[Index++] = num[Index1++];
        } else {
            tmp[Index++] = num[Index2++];
        }
    }
    while(Index1 <= m) {
        tmp[Index++] = num[Index1++];
    }
    while(Index2 <= r) {
        tmp[Index++] = num[Index2++];
    }
    for(int i = l; i <= r; ++i) {
        num[i] = tmp[i - l];
    }
    free(tmp);
    return cnt;
}
int mergeSort(int *num, int l, int r) {
    if(l == r) {
        return 0;
    }
    int m = (l + r) / 2;
    return mergeSort(num, l, m) + mergeSort(num, m + 1, r) 
    + Merge(num, l, m, r);
}
int f(int n) {
    int *num = (int*)malloc(sizeof(int) * (n + 1));
    for(int i = 1; i <= n; ++i) {
        num[i] = n - i + 1;
    }
    int cnt = mergeSort(num, 1, n);
    free(num);
    return cnt;
}
int main() {
    int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%d\n", f(n));
    }
    return 0;
}

并且告诉小 Hi，只要运行上面的代码，就能得到正确的结果，其中输入的 $T$ 表示有 $T$ 组数据，每组数据的 $n$ 也就是题面描述的数组大小，而 printf 的 f(n)，就是所求的答案——归并排序过程中的比较次数。

输入

第一行为一个整数 $T$，表示有 $T$ 组数据，接下去 $T$ 行，每行一个整数 $n$，表示数组的大小。

输出

对于每一个给定的 $n$，输出对应的答案。

样例

说明

请注意数据范围与时间限制，程序必须在 $3s$ 内运行结束并得到正确结果
对于 $40\%$ 的数据，$1\leq T\leq10^5,~1\leq n\leq10^3$
对于 $80\%$ 的数据，$1\leq T\leq10^6,~1\leq n\leq10^5$
对于 $100\%$ 的数据，$1\leq T\leq10^6,~1\leq n\leq10^7$

H. Hack 双哈希

分值：50 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

在一场黑客攻防赛中，小 Hi 与小 Yi 被分配到同一组。
第一局比赛小 Hi 负责防守而小 Yi 进行攻击，小 Yi 发现了小 Hi 代码中一个关于字符串哈希的漏洞，尽管小 Hi 的哈希冲突（两个不同字符串用指定的哈希算法能得到相同的哈希值）概率只有 $\frac{1}{1000000007}$，但是由于这种哈希方式能够进行逆运算，因此小 Yi 很快就得到一个与源代码哈希值相同的字符串，将其注入到小 Hi 的代码中，导致程序崩溃，小 Yi 率先获得 1 分。
第二局角色对换，由小 Yi 负责防守而小 Hi 进行攻击，小 Yi 自恃数据结构 $Master$，在代码中故意出现同样的漏洞，但与小 Hi 不同的是，小 Yi 在原先小 Hi 的代码基础之上，又添加了另一种几乎无法逆推计算的哈希代码，即用两种算法对字符串进行了哈希，使得哈希冲突的概率降低到 $\frac{1}{536870912\times1000000007}$，小 Yi 的字符串哈希代码如下：

int Hash1(char *str) {
    int ret = 0;
    for(int i = 0; str[i] != '\0'; ++i) {
        if((i & 1) == 0) {
            ret ^= ((ret << 7) ^ str[i] ^ (ret >> 3));
        } else {
            ret ^= (~((ret << 11) ^ str[i] ^ (ret >> 5)));
        }
    }
    return ret & 0x2FFFFFFF;
}
int Hash2(char *str) {
    int ret = 0;
    int MOD = 1000000007;
    for(int i = 0; str[i] != '\0'; ++i) {
        ret = ((long long)ret * 26 + (str[i] - 'a' + 1)) % MOD;
    }
    return ret;
}
long long Hash(char *str) {
    return (long long)Hash1(str) * 1000000000 + Hash2(str);
}

其中 Hash2 函数就是小 Hi 原先的哈希代码，而 Hash 函数是小 Yi 的双哈希返回值，小 Hi 只要找到与“指定字符串”冲突的字符串，将其注入到小 Yi 的代码中，就能让程序崩溃。但作为攻击者的小 Hi 现在一脸懵逼，他使用了一次场外求助的机会，求助对象就是你，你能否帮助小 Hi 以牙还牙，拿回第二局比赛的这一分？
“指定字符串”也就是将以上代码所有字母提取出来，并全部转化为小写字母之后的字符串：

"inthashcharstrintretforintistriiifiretretstriretelseretretstriretreturnretxfffffffinthashcharstrintretintmodforintistriiretlonglongretstriamodreturnretlonglonghashcharstrreturnlonglonghashstrhashstr"

输入

无。

输出

输出一个字符串 $s$，要求 $s$ 的字符串长度满足 $0\leq|s|\leq100000$，所有字符均为小写字母，且调用 Hash(s) 后返回的数字（哈希值）与“指定字符串”的哈希值相等。只要字符串满足以上条件，即认为答案正确，答案不唯一。