第五届华为“创新杯”编程大赛初赛题目（第一场）

suika — Sat, 11 May 2013 05:03:29 +0000

分了两场，每场三道题
这次华为终于用online judge了 OTL…… 难度也是比去年的提高了不少（去年题还都停留在字符串操作上见：http://blog.thpiano.com/?p=543）
不过就是华为那边服务器运行结果慢如牛，比完了都不知道结果……
顺便所有题都没有输入输出范围，部分题意也有些含糊
先把题目和自己的烂代码贴一下吧

第一题：磁盘数据恢复（点此展开）

题目描述
在存储领域，RAID5是一种兼顾数据安全、成本和性能的磁盘阵列技术方案，它是把数据和校验信息均匀地分散到阵列的各个磁盘上，每个磁盘上既有数据，又有校验信息，当一个数据盘损坏时，系统可以根据同一带区（下图中的D1D2D3P1）的其他数据块和对应的校验信息来重构损坏的数据。如下所示为数据D1D2D3D4D5D6D7D8D9D10D11D12即其相应校验信息P1P2P3P4在阵列中的分布（D为数据，P为校验信息，每一列为一阵列磁盘，每一行为一带区）：

D1(0x1a) D2(0x2a) D3(?) P1(0x6a)
D4(0x4a) D5(0x5a) P2(?) D6(0x6a)
D7(0x7a) P3(0x6a) D8(?) D9(0x9a)
P4(0xad) D10(0xaf) D11(?) D12(0xac)

系统已经把数据信息{D1(0x1a), D2(0x2a), D3(?), D4(0x6a), D5(0x5a), D6(0x6a), D7(0x7a), D8(?), D9(0x9a), D10(0xaf), D11(?), D12(0xac)}及其异或校验码信息{P1(0x6a), P2(?), P3(0x6a), P4(0xad)}按照RAID5技术如上依次存储在四个阵列磁盘中，但不幸的是部分磁盘数据已经损坏，如上图所示第3列（即第3块磁盘），请将其同一带区中丢失的信息恢复出来。

注意：数据校验信息是通过异或计算得来的。

例如：其中“?”表示待恢复的数据和校验码信息。在输入数据时为方便操作，“?”用0xff表示，测试用例中会保证其它正常数据不会出现0xff。以上输入信息变为{ 0x1a, 0x2a, 0xff, 0x6a, 0x4a, 0x5a, 0xff, 0x6a, 0x7a, 0x6a, 0xff, 0x9a, 0xad, 0xaf, 0xff, 0xac }

丢失数据和校验信息的恢复：D3=0x5a, P2=0x7a, D8= 0x8a, D11=0xae

输入
以空格隔开的16进制数字(数据共计16个，如上图中所示规模)

输出
以空格隔开的恢复后的数据和校验信息

样例输入
0x1a 0x2a 0xff 0x6a 0x4a 0x5a 0xff 0x6a 0x7a 0x6a 0xff 0x9a 0xad 0xaf 0xff 0xac
样例输出
0x5a 0x7a 0x8a 0xae

题目写了这么长，就是个异或
签到题

第一题自己的AC代码

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

int main(){
int x, tmp, i ,j;
x = -1;
int count = 0;
while(scanf("%x", &tmp) != EOF){
if (tmp != -1){
x ^= tmp;
}
++count;
if (count % 4 == 0){
x &= 255;
printf("0x%x", x);
if (count % 16 == 0){
printf("\n");
}else{
printf(" ");
}
x = -1;
}
}
return 0;
}

第二题：容量转换

题目描述
随着大数据时代的到来，也就意味着越来越多的数据需要被存储与分析。10年前，市场上主流的硬盘容量也就20GB，而今天，硬盘容量已达到

TB级别。在一些大型企业的数据中心，购买的存储容量多达几十，上百个PB，甚至达到EB级别。但用户在使用过程中，如果将EB级的容量使用

MB呈现，将带来极大的困扰，比如华为网盘给你分配了50M的空间，而你仅使用了11M，还剩下39M，如果华为告诉你，你的网盘空间剩余

33936KB或0.000037TB，你将很难认知当前你的网盘空间只有39M了。但如果转换到GB，则剩余就应该是0.038G，虽能够较好的感知容量剩余大

小，但此时造成了容量损失为39MB-38.92MB=0.08MB，此种转换不可取，因此显示为39M为最优的容量（既能有效识别容量大小，也能够尽可能

减少容量精度损失）。
因此，需要完成一个容量转换算法：给定一个在KB~EB范围内的任意容量大小，需要将其转换到(1~1024)范围内且合适的容量单位上进行呈现

，要求：
1）转换后容量的精度保留3位小数，且精度位需要下取整以保证转换后的容量一定可用；如3.1256，精度位下取整后，数字为3.125。
2）如果容量转换后输出为0.000，则始终以整数形式输出，结果应为0GB；其余结果都需要保留3位精度。

输入
容量输入格式=容量数字+空格+单位，如2.536 PB；单位有KB、MB、GB、TB、PB、EB

输出
转换后容量输出格式=容量数字+单位，如2.536PB；单位有KB、MB、GB、TB、PB、EB；

样例输入
0.00335 TB
样例输出
3.430GB

自己的代码wa了，找不到wa在哪，求各位指点……
最大数字应该是2的60次方，double也应该存的下才对，难道要大数乘法 OTL

第二题自己的代码

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

#include

char level[6] = {'E', 'P', 'T', 'G', 'M', 'K'};
int main(){
char l[30];
double num;
int i;
while(scanf("%lf", &num) != EOF){
scanf("%s", l);
for (i = 0; i < 6; ++i){
if (l[0] == level[i]){
break;
}
}
while(num < 1 && i < 5){
num *= 1024;
++i;
}
while(num >= 1024 && i > 0){
num /= 1024;
--i;
}
num = int(num * 1000) / 1000.0;
if (num < 0.001){
printf("0GB\n");
}else{
printf("%.3lf%cB\n", num, level[i]);
}
}
return 0;
}

第三题：判断给定的数字是否满足给定的条件

题目描述
判断给定的数字是否满足给定的条件。
说明：
1、条件是一个字符串，其格式由数学上的“开闭区间”，"&&"和"||"组成。其格式为：[5,7]&&(6,9]||(10,20)，该条件表示

“大于等于5，小于等于7”并且“大于6，小于9”或者“大于10，小于20”。
2、 &&优先级高于||

输入
1、字符串1：上述描述格式的条件：如[5,7]&&(6,9]||(10,20)

2、数字：判断是否满足条件的数字：9

说明：上诉两个参数是在一行中输入的，其格式为：字符串1+空格+数字。如[1,2]||(3,4) 3

输出
如果满足条件，则输出1，否则0

样例输入
[1,2]||(3,4] 3
样例输出
0

只能粗略地把&&合并，最后是TLE
估计要用线段树

第三题自己的代码

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

#include
#include

typedef struct{
double start;
double end;
bool e;
}Space;
std::vector<Space> v;

void unionSpace(){
int i;
for (i = 1; i < v.size(); ++i){
if (v[i].e == true){
if (v[i].start < v[i-1].start){
v[i].start = v[i-1].start;
}
if (v[i].end > v[i-1].end){
v[i].end = v[i-1].end;
}
v[i-1].end = v[i-1].start - 1; // waste
}
}
}

bool isIn(double n){
for (int i = 0; i < v.size(); ++i){
if (n >= v[i].start && n <= v[i].end){
return true;
}
}
return false;
}

int main(){
int i;
double num;
Space tmpS;
tmpS.e = false;
char tmp;
while(scanf("%c", &tmp) != EOF){
if (tmp == '('){
scanf("%lf", &num);
tmpS.start = num + 0.0001;
}else if (tmp == '['){
scanf("%lf", &num);
tmpS.start = num;
}else if (tmp == ','){
scanf("%lf", &num);
tmpS.end = num;
}else if (tmp == ')'){
tmpS.end -= 0.0001;
v.push_back(tmpS);
}else if (tmp == ']'){
v.push_back(tmpS);
}else if (tmp == '&'){
tmpS.e = true;
scanf("%c", &tmp);
}else if (tmp == '|'){
tmpS.e = false;
scanf("%c", &tmp);
}else{
scanf("%lf", &num);
unionSpace();
printf("%d\n", isIn(num));
v.clear();
}

}
return 0;
}

第二场的另起一篇发吧，感觉有点长