[活动]第78次编程比赛题目 — 编程爱好者社区

主题：[活动]第78次编程比赛题目

liuwenhan [专家分：20] 发布于 2008-11-30 12:27:00

1 . 1.  百度时间
Baidu的服务器上使用的不是北京时间，而是Baidu时间。Baidu时间的时分秒与北京时间相同，但是日期与北京时间不同，是用一个正整数表示从2000年1月1日开始经过了几天。

现在就请大家设计一个程序将北京时间转换为百度时间。在本题中，闰年的年份是400的倍数，或者是4的倍数但不是100的倍数。比如2000和8888均为闰年，但6100不是。

输入格式
输入数据的每一行为一个待转化的北京时间（不含空格和TAB），正确的格式包括两种：
一种为：YYYY-MM-DD，（YYYY表示四位数年份，MM为两位月份，DD为两位日期）；
另一种为：MM/DD/YYYY，（YYYY表示四位数年份，MM为两位月份，DD为两位日期）；

输出格式
每个数据输出一行。如果可以成功转换，输出一个正整数，否则输出Error。

输入样例例
2000-01-01
AStar2007
05/26/2007

输出样例例
0
Error
2702

1 . 2
已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写C语言函数实现从中去掉所有
ansi编码的的数字和字母（包括大小写).要求在原字串上返回结果。

int   filter_ansi(char*   gbk_string);
　　注：汉字的GBK编码范围是0x8140   -   0xFEFE

1 . 3 .  实习生小胖的百度网页过滤器
百度网页采集器(Baiduspider)每天从互联网收录数亿网页，互联网的网页质量参差不齐。百度的工程师们每天都在改进方法来判断一个网页质量的好坏，使质量差的网页出现在检索结果中较后的位置。现在实习生小胖想到一个很简单的方法来判断一个网页内容的好坏，方法如下：
1. 利用数据挖掘技术在互联网语料库中挖掘出一批有特点的词汇，分为好词和坏词两种，好词标上正的权重，坏词标上负的权重；
2. 通过好词和坏词词典对每个网页计算网页总权重：从第一个字开始匹配，找到一个好词则加上相应的权重，找到一个坏词则减去相应的权重，下一次匹配将从找到的词末尾的下一个位置开始。
3. 坏词采用正向最短匹配：从当前匹配位置开始的若干连续汉字，如果形成多个坏词，则只计算最短的那个坏词的权重，下一次匹配将从这个最短坏词末尾的下一个位置开始。
4. 好词采取正向最长匹配：从当前匹配位置开始的若干连续汉字，如果形成多个“有效”好词，则只计算最长“有效”好词的权重，下一次匹配从这个最长“有效”好词末尾的下一个位置开始。
5. “无效”好词的定义：好词的一部分本身是一个坏词；或者好词的一部分与后续相邻的若干字组成一个坏词。

现在小胖已经做好了第1步的工作，有一个好词和坏词的列表（词典），但是由于没有对中文文本处理的程序经验，他想请未来的百度之星们帮他完成这个程序。

输入格式
输入第一行为一个字符串（网页正文）。从第二行开始为词典，格式为“词空格词的权重”。权重为一个带符号32位整数。如果权重为正，则为好词，反之则为坏词；不存在重复的词，不存在权重为0的词。
作为“网页”的字符串中同时包含中文和ASCII字符，每个汉字占2个字节。并非“网页”中的所有字都在词典中。

输出格式
输出仅一行，为网页总权重（答案保证不超过带符号32位整数的范围）。

样例输入例
小胖之喷火龙骑士!!
小胖 6
喷火 -1
喷火龙 -1
火龙 -1
龙 4
龙骑 3
龙骑士 2
骑士 -2
士 3

样例输出例
7

样例解释
从“网页”中找到的好词为“小胖”和“龙”，坏词为“喷火”和“骑士”。特别要说明一下“龙”被识别为好词的原因——“喷火”和“喷火龙”均为坏词，按正向最短匹配得到“喷火”，接着往下匹配到好词“龙”、“龙骑”和“龙骑士”，但是由于“骑士”是坏词，所以“龙骑”、“龙骑士”无效而“龙”是最长的有效好词。注意题目描述中的匹配规则，好词的“有效”和“无效”只考虑该好词的一部分与后续字是否能够组成坏词，而不考虑和前面的字是否能够组成坏词——样例中的 “龙”虽然可以与前面的字组成坏词“喷火龙”和“火龙”，但由于这两个词都是未能匹配成功的坏词，因此对好词“龙”的词性没有影响，可以累积“龙”的权重。

注意事项
输入数据的中文采用GBK编码。
GBK：是又一个汉字编码标准，全称《汉字内码扩展规范》。采用双字节表示，总体编码范围为 8140-FEFE，首字节在 81-FE 之间，尾字节在 40-FE 之间，排除xx7F。总计 23940 个码位，共收入  21886 个汉字和图形符号，其中汉字（包括部首和构件）21003 个，图形符号 883 个。

1.4. Wii游戏开始啦！
为了在紧张的上班时间让员工们轻松些，百度休息室里放置着按摩椅、CD、高尔夫套装和Wii游戏机等休闲用品。其中最受欢迎的当然是游戏机。

Wii游戏机有两个手柄，每个手柄使用两节电池（这两个电池可以是不同的品牌），其中至少一块电池没电时该手柄没电。

工程师们在玩游戏时，总是用最简单的方式更换电池：有手柄没电时把所有没电的电池拿走，一一换上新电池即可（有电的电池总是继续使用）。当有手柄没电但没有新电池可用时才停止玩Wii。

告诉你每个品牌电池的使用时间以及该品牌电池的个数，请计算工程师们玩游戏时间的最小值和最大值。

输入格式
输入第一行为一个正整数n，表示电池的种数。接下来n行，每行两个整数L和F，表示使用时间为L的电池有F个（电池不必成对出现，即F可以是奇数）。

输出格式
输出仅一行，包含两个整数，分别表示工程师们的最短游戏时间和最长游戏时间（短的时间在前）。两个整数之间以空格隔开。

输入样例例
3
3 2
5 2
8 2

输出样例例
5 8

样例解释
有三对电池，使用时间分别为3小时、5小时和8小时。
方案1：一开始给手柄1使用一对3小时的电池，给手柄2使用一对5小时的电池，则3小时后手柄1没电，换上一对8小时的。再过2小时后，手柄2没电。此时已经没有电池可用了。总时间为5小时。
方案2：一开始给手柄1使用一对8小时的电池，给手柄2使用一对5小时的电池，则5小时后手柄2没电，换上一对3小时的。再过3小时后，手柄1和手柄2同时没电。此时已经没有电池可用了。总时间为8小时。

2.问题

某栋写字楼6层，有1部电梯，编写一个电梯仿真程序

A. 考虑如下条件

1. 每层楼都有上行和下行两个按键

2.电梯一开始停在1层

3.电梯可以容纳8个人

4.乘坐电梯的客人的请求频率，时间间隔和到达楼层是随机的

5.电梯的上下一层需要1秒

6.电梯空间有限，同时只能容纳一定数量的客人，如果已经达到人数额度，电梯将不理会任何请求

7.不考虑客人请求当前楼层和不请求楼层的情况

8.电梯的响应延迟为0（比如，电梯往3楼上行，3楼的客人在电梯到达3楼之前按上行键，程序有权调度电梯在3楼开门）

9.电梯的开关门时间和客人上下电梯时间为0，匀速运行

10.电梯调度算法不能预读尚未发生的请求（比如在10秒的时候电梯无法预知11秒时某层客人的请求)

11.客人请求发生在整数秒

B. 目标

1.在运送所有客人到达目标楼层的前提下电梯的总行程尽可能小

2. 设计一个接口，实现调度算法的可替换性（比如，通过重新实现该接口可以使系统使用其它算法）

C. 输入和输出

输入:

input.txt

客人的请求序列，格式为到达时间，所在楼层，请求楼层，假设该输入是按照时间递增的

比如：

input.txt

1 2 3

2 3 1

在1秒的时候有客人请求从2层到3层，2秒的时候有客人请求从3层到1层
输出: 设计一种简单实用的输出可以清晰地反映电梯的运转情况

[color=808000]前四题任选一题,最后一题选做,有兴趣的朋友可以做一下.上面的题目都是出自论坛里的,还很少人回答!
这是很好的锻炼机会,希望大家踊跃参加，提交自己写的代码。请相信自己 ,期待很好的代码出现！

希望以前参加过的继续参加!

比赛结束时间: 2008 .12 .9 13:00:00

比赛已经结束了，好激动啊
明天上午公布结果，谢谢大家了，只要参加就是好样的
[/color]

最后更新于：2008-12-09 13:09:00

本帖地址： http://bbs.pfan.cn/post/290274.html

回复列表（共19个回复）

11 楼

alexanderip [专家分：30] 发布于 2008-12-09 00:52:00

        temp[index] = '\0';
        yearNum = atoi(temp);

        if(month[0] == '0'){              //检查月份是否输入正确
            if(month[1] >= '0' && month[1] <= '9'){
                temp[0] = month[1];
                temp[1] = '\0';
            }else
                return MSG_ERROR;
        }else if(month[0] == '1'){
            if(month[1] >= '0' && month[1] <= '2'){
                temp[0] = month[0];
                temp[1] = month[1];
                temp[2] = '\0';
            }else
                return MSG_ERROR;
        }else
            return MSG_ERROR;

        monthNum = atoi(temp);

        //检查日是否输入正确
        if(day[0] >= '0' && day[0] <= '3' && day[1] >= '0' && day[1] <= '9'){
            if(day[0] == '0')
                temp[0] = day[1];
            else{
                temp[0] = day[0];
                temp[1] = day[1];
            }

            temp[2] = '\0';
        }else
            return MSG_ERROR;

        dayNum = atoi(temp);

        if(checkLeapYear(yearNum) == TRUE)          //检查是否闰年

12 楼

alexanderip [专家分：30] 发布于 2008-12-09 00:53:00

    if(monthNum == 2 && dayNum > 29)         //若为闰年二月是否二十九日
                return MSG_ERROR;
            else
                if(monthNum == 2 && dayNum > 28)         //若为闰年二月是否二十九日
                    return MSG_ERROR;

        numOfLongMonth = 0;
        if(monthNum <= 7){                       //检查小于八月份的日子大小

            if(monthNum % 2 == 0){          //小月份的检查
                if(dayNum > 30)
                    return MSG_ERROR;
            }else
                if(dayNum > 31)               //小月份的检查
                    return MSG_ERROR;

            if(monthNum != 1)                     //计算有多少长月
                for(index = 1; index < monthNum; index++)
                    if(index%2 != 0)
                        numOfLongMonth++;
        }else{                           //检查大于七月份的月份日子长度是否正确
            if(monthNum % 2 == 0){
                if(dayNum > 31)
                    return MSG_ERROR;
            }else
                if(dayNum > 30)
                    return MSG_ERROR;
            //计算有多少长月

        if(monthNum != 1)                     //计算有多少长月
                for(index = 1; index <= 7 ;index++)
                    if(index%2 != 0)
                        numOfLongMonth++;

13 楼

alexanderip [专家分：30] 发布于 2008-12-09 00:53:00

    for(index = 8; index < monthNum; index++)
                if(index%2 == 0 )
                    numOfLongMonth++;
        }

        countLeapYear = 0;
        for(index = 2000; index < yearNum;index++){           //计算由2000年至该年有多少闰年
            if(checkLeapYear(index) == TRUE){
                countLeapYear++;
            }
        }

        if(checkLeapYear(index) == TRUE && monthNum > 2){
                countLeapYear++;
            }

        //计算总日数
        if(monthNum < 2)
        numOfDay = NORMAL_YEAR_DAY*(yearNum - 2000) + countLeapYear+ numOfLongMonth*31 + (monthNum-numOfLongMonth-1)*30-1+dayNum;
         else
          numOfDay = NORMAL_YEAR_DAY*(yearNum - 2000) + countLeapYear+ numOfLongMonth*31 + (monthNum-numOfLongMonth-1)*30-3+dayNum;
        return numOfDay;
}

int date2num(char date[]){
    if(date[10] != '\0'){                   //日期长度并不能长过十个字符
        return MSG_ERROR;
    }else if((date[4] == '-') && (date[7] =='-')){           //初步判断格式是否正确
        return giveNum(date,&date[5],&date[8]);
    }else if((date[2] == '/' )&&( date[5]== '/')){
        return giveNum(&date[6], date,&date[3]);
    }else

14 楼

alexanderip [专家分：30] 发布于 2008-12-09 00:53:00

    return MSG_ERROR;
}

int main(){
    char date[DATE_FORMAT_LENGTH];
    int numOfDay;

    printf("请输入日期(YYYY-MM-DD OR MM/DD/YYYY) 按q离开\n");
    scanf("%s",date);   //输入日期
    while(date[0] != 'q'){             //按q离开程序
        numOfDay = date2num(date);        //获取总日数

        if(numOfDay  ==  MSG_ERROR)      //若输入数据具有错误，则输出错误讯息
            printf("Error\n");
        else
            printf("%d\n", numOfDay);      //若正确，则输出日数

        printf("请输入日期(YYYY-MM-DD OR MM/DD/YYYY)\n");
        scanf("%s",date);     //输入日期
    }
}

15 楼

yj1221 [专家分：20] 发布于 2008-12-09 12:05:00

// c:\myFile.txt
2000-01-01
AStar2007
05/26/2007

//  程序主程序

#include <iostream>
#include <cctype>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

FILE *fp;

bool yearMonthDayRead(int &year, int &month, int &day); // 读入年月日

int main()
{
    if( (fp = fopen("c:\\myFile.txt", "r")) == NULL)
    {
        cout << "打开文件错误!" << endl;
        return 0;
    }

    int monthDay[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; // 每月应该的天数

    int year = 2000;
    int month = 1;
    int day = 1;

    bool flag = true; //
    char ch = fgetc(fp);
    int sum = 0;

16 楼

yj1221 [专家分：20] 发布于 2008-12-09 12:07:00

//  读入文件部分，总感觉这很不好修改，不知道怎么改更好，希望楼主给点建议
// ------------------------------------------------------------------------------
    while( ch != EOF )
    {
        flag = true; // 成功为真，否则为假
        if( isdigit(ch) )
        {
            sum = 0;
            while( isdigit(ch) ) // 判断是否为数字
            {
                sum = sum*10 + (ch - '0');
                ch = fgetc(fp);
            }

            if( ch == '-')
            {
                year = sum;  //   赋值 year

                sum = 0;
                ch = fgetc(fp);

                if( isdigit(ch) )
                {
                    while( isdigit(ch) )
                    {
                        sum = sum*10 + (ch - '0');
                        ch = fgetc(fp);
                    }

                    if( ch == '-')
                    {
                        month = sum;  // 赋值month

                        sum = 0;
                        ch = fgetc(fp);

                        if( isdigit(ch) )
                        {
                            while( isdigit(ch) )
                            {
                                sum = sum*10 + (ch - '0');
                                ch = fgetc(fp);
                            }

                            day = sum;  // 赋值day

                            // 去掉字符，直到回车
                            while( ch != '\n' )
                                ch = fgetc(fp);
                            ch = fgetc(fp); // 去掉回车
                        }

17 楼

yj1221 [专家分：20] 发布于 2008-12-09 12:07:00

else
                        {
                            flag = false;
                            // 去掉字符，直到回车
                            while( ch != '\n' )
                                ch = fgetc(fp);
                            ch = fgetc(fp); // 去掉回车
                        }
                    }
                    else
                    {
                        flag = false;
                        // 去掉字符，直到回车
                        while( ch != '\n' )
                            ch = fgetc(fp);
                        ch = fgetc(fp); // 去掉回车
                    }
                }
                else
                {
                    flag = false;
                    // 去掉字符，直到回车
                    while( ch != '\n' )
                        ch = fgetc(fp);
                    ch = fgetc(fp); // 去掉回车
                }
            }
            else if( ch == '/')
            {
                month = sum;  // 赋值month

                sum = 0;
                ch = fgetc(fp);

                if( isdigit(ch) )
                {
                    while( isdigit(ch) )
                    {
                        sum = sum*10 + (ch - '0');
                        ch = fgetc(fp);
                    }

                    if( ch == '/')
                    {
                        day = sum;  // 赋值day

                        sum = 0;
                        ch = fgetc(fp);

18 楼

yj1221 [专家分：20] 发布于 2008-12-09 12:08:00

    if( isdigit(ch) )
                        {
                            while( isdigit(ch) )
                            {
                                sum = sum*10 + (ch - '0');
                                ch = fgetc(fp);
                            }

                            year = sum; // 赋值year

                            // 去掉字符，直到回车
                            while( ch != '\n' )
                                ch = fgetc(fp);
                            ch = fgetc(fp); // 去掉回车
                        }
                        else
                        {
                            flag = false;
                            // 去掉字符，直到回车
                            while( ch != '\n' )
                                ch = fgetc(fp);
                            ch = fgetc(fp); // 去掉回车
                        }
                    }
                    else
                    {
                        flag = false;
                        // 去掉字符，直到回车
                        while( ch != '\n' )
                            ch = fgetc(fp);
                        ch = fgetc(fp); // 去掉回车
                    }
                }
                else
                {
                    flag = false;
                    // 去掉字符，直到回车
                    while( ch != '\n' )
                        ch = fgetc(fp);
                    ch = fgetc(fp); // 去掉回车
                }
            }
            else
            {
                flag  = false;
                // 去掉字符，直到回车
                while( ch != '\n' )
                    ch = fgetc(fp);
                ch = fgetc(fp); // 去掉回车
            }
        }
        else
        {
            flag = false;
            // 去掉字符，直到回车
            while( ch != '\n' )
                ch = fgetc(fp);
            ch = fgetc(fp); // 去掉回车
        }
//       读入文件部分
// ----------------------------------------------------------------------------------

19 楼

yj1221 [专家分：20] 发布于 2008-12-09 12:08:00

    //  对读入的数据进行处理
        if(flag)
        {
            // 2000年之前为错误
            if(year < 2000)
            {
                cout << "Error!" << endl;
                continue; // 跳过下面的循环语句
            }

            int sumDay = 0;

            //  从2000年开始，加上当年之前所有年的日期之和
            for(int i = 2000; i < year; ++i)
            {
                if( (i%400 == 0) || (i%4 == 0 && i%100 != 0) )
                    sumDay += 366;
                else
                    sumDay += 365;
            }

            // 如果本年是闰年，将二月的天数改为29
            if( (year%400 == 0) || (year%4 == 0 && year%100 != 0) )
                monthDay[2]++; // 闰年的二月为29天

            // 加上当年这天之前的所有日期之和
            for(i = 1; i < month; ++i)
                sumDay += monthDay[i];

            // 加上当月的天数
            for(i = 1; i < day; ++i)
                sumDay ++;

        //    cout << "sumDay is " << sumDay << endl;
            cout << sumDay << endl;
        }
        else
        {
            cout << "Error!" << endl;
        }

    //  将二月的日期改为28天
        monthDay[2] = 28;
    }
    return 0;
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[活动]第78次编程比赛题目

回复列表（共19个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[活动]第78次编程比赛题目

回复列表 （共19个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共19个回复）