JavaScript

Pro. ID
��ҳ
��������


redraiment心情驿站

杭州电子科技大学Judge Online 2000->2099题解题报告
浙江工商大学 软件0601 redraiment

Email:redraiment@126.com
百度空间:http://hi.baidu.com/redraiment/

网页简介
问题描述: | 题目原文拷贝。
问题分析: | 英文题的翻译、题目的考点以及所涉及到的数据结构和算法。还有一些前置知识。
算法实现: | 针对题目，讲述如何提高程序效率等一些编程的技巧。还有一些题目的多种解法。
参考源码: | 是我通过的代码中效率最高，长度最短的代码。总之是我写出的代码中最优秀的。


Problem

编码建议

Programing
通过前面的问题分析，可以看出本题要实现两个数之间的交换功能

你可以选择任何一门你熟悉的语言编写。
这里我用的是C++。
因为C++为了提高开发效率，已经为我们准备好了很多常用的算法。
像我们现在要用的交换两个数的函数，也可以直接调用swap()函数。
ACM中，效率才是关键！


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:if判断语句的语法

Algorithm Analyse
要让三个数从小到大排，顺序就是：
  1. 比较1，2两个数。如果第一个数比第二数大，把这两个数交换，来保证前面两个数按升序排列。
  2. 比较2，3两个数。如果第二个数比第三数大，把这两个数交换，来保证后面两个数按升序排列。
  3. 经过上面两步，最大的数已经被移到最后。再重复一次第一步。保证三个数都是按升序来排列。
虽然你也可以用排序算法对它进行排序，但那就把问题复杂化了。做ACM的题目，就是要充分利用题目给出的条件(本题一明确指出输入的只有三个字符)。选择最优算法，而不是最通用的算法。


Problem

2000 ASCII码排序

Problem Description
输入三个字符后，按各字符的ASCII码从小到大的顺序输出这三个字符。

Input
输入数据有多组，每组占一行，有三个字符组成，之间无空格。

Output
对于每组输入数据，输出一行，字符中间用一个空格分开。

Sample Input
qwe
asd
zxc

Sample Output
e q w
a d s
c x z

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


problem set

问题描述 问题分析 算法实现 参考源码


Problem

编码建议

Programing
本题用到开平方函数:

#include <math.h>
double sqrt( double num );


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:库函数的调用

Algorithm Analyse
直接用勾股定理做。


Problem

2001 计算两点间的距离

Problem Description
输入两点坐标（X1,Y1）,（X2,Y2）,计算并输出两点间的距离。

Input
输入数据有多组，每组占一行，由4个实数组成，分别表示x1,y1,x2,y2,数据之间用空格隔开。

Output
对于每组输入数据，输出一行，结果保留两位小数。

Sample Input
0 0 0 1
0 1 1 0

Sample Output
1.00
1.41

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


Problem

编码建议

Programing
因为题目没有提示说怎样才算输入结束，所以我就规定是文件读到底为止(即EOF)。
这是ACM的默规。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:球体体积公式

Algorithm Analyse
球体的体积公式:V = 4пr3/3


Problem

2002 计算球体积

Problem Description
根据输入的半径值，计算球的体积。

Input
输入数据有多组，每组占一行，每行包括一个实数，表示球的半径。

Output
输出对应的球的体积，对于每组输入数据，输出一行，计算结果保留三位小数。

Sample Input
1
1.5

Sample Output
4.189
14.137

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


Problem

编码建议

Programing
本题用到实数求绝对值函数:

#include <math.h>
double fabs( double arg );

功能： 函数返回参数arg的绝对值。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:库函数的调用

Algorithm Analyse
直接调用库函数。


Problem

2003 求绝对值

Problem Description
求实数的绝对值。

Input
输入数据有多组，每组占一行，每行包含一个实数。

Output
对于每组输入数据，输出它的绝对值，要求每组数据输出一行，结果保留两位小数。

Sample Input
123
-234.00

Sample Output
123.00
234.00

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


Problem

编码建议

Programing
Empty


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:if嵌套语法

Algorithm Analyse

  1. 接受数据Score，直到读入失败
  2. 如果 Score 小于 0，为错误数据，输出“Score is error!”，返回第1步，否则进入第3步。
  3. 如果 Score 小于 60，输出“E”，返回第1步，否则进入第3步。
  4. 如果 Score 小于 70，输出“D”，返回第1步，否则进入第4步。
  5. 如果 Score 小于 80，输出“C”，返回第1步，否则进入第5步。
  6. 如果 Score 小于 90，输出“B”，返回第1步，否则进入第6步。
  7. 如果 Score 小于 101，输出“A”，返回第1步，否则进入第7步。
  8. Score为错误数据，输出“Score is error!”，返回第1步。


Problem

2004 成绩转换

Problem Description
输入一个百分制的成绩t，将其转换成对应的等级，具体转换规则如下：
90~100为A;
80~89为B;
70~79为C;
60~69为D;
0~59为E;

Input
输入数据有多组，每组占一行，由一个整数组成。

Output
对于每组输入数据，输出一行。如果输入数据不在0~100范围内，请输出一行：“Score is error!”。

Sample Input
56
67
100
123

Sample Output
E
D
A
Score is error!

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


Problem

编码建议

Programing
把判断闰年的算法写成一个宏：

#define lev(n) (n % 4 == 0 && (n % 100 != 0 || n % 400 == 0))
是闰年返回1，否则返回0。

再开一个二维数组来保存闰年和非闰年每个月的天数。
这样做可以减少编码的复杂度。
当然，对于这样的简单题能通过的就是好代码。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:基本历法知识

Algorithm Analyse
判断N是否为闰年的方法是：N能4整数但不能被100整除 或者 N能被400整除
算出第N年的每个月的天数后就从一月开始累加，不要忘了最后要加天数哦。^_^


Problem

2005 第几天？

Problem Description
给定一个日期，输出这个日期是该年的第几天。

Input
输入数据有多组，每组占一行，数据格式为YYYY/MM/DD组成，具体参见sample input ,另外，可以向你确保所有的输入数据是合法的。

Output
对于每组输入数据，输出一行，表示该日期是该年的第几天。

Sample Input
1985/1/20
2006/3/12

Sample Output
20
71

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


Problem

编码建议

Programing
循环用for实现就可以了。
至于那个判断条件，一般是if (t % 2 == 1)。
但也可以简化为 if (t % 2)

After Class
课外资料:在早期CPU处理的功能还不够强的时候，求X对于2^n的余数，可能不直接用%来运算。而是换成位运算。 X & (2^N - 1)。
比如求 N 余 8，写成 n & 7。
这样写可读性比较差。而且现在的机器性能提升了，一般的编译器也能自动转换这种优化。所以这种写法现在不推荐。仅做了解(当然如果你想炫耀一番自己的才华，那另当别论)。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:循环语句

Algorithm Analyse
循环+条件判断


Problem

2006 求奇数的乘积

Problem Description
给你n个整数，求他们中所有奇数的乘积。

Input
输入数据包含多个测试实例，每个测试实例占一行，每行的第一个数为n，表示本组数据一共有n个，接着是n个整数，你可以假设每组数据必定至少存在一个奇数。

Output
输出每组数中的所有奇数的乘积，对于测试实例，输出一行。

Sample Input
3 1 2 3
4 2 3 4 5

Sample Output
3
15

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:循环语句

Algorithm Analyse
简单的循环+判断。
按题目的意思数据类型用unsigned int型就可以了。
但这个问题有个容易遗漏的地方:输入的m、n有可能m > n!


Problem

2007 平方和与立方和

Problem Description
给定一段连续的整数，求出他们中所有偶数的平方和以及所有奇数的立方和。

Input
输入数据包含多组测试实例，每组测试实例包含一行，由两个整数m和n组成。

Output
对于每组输入数据，输出一行，应包括两个整数x和y，分别表示该段连续的整数中所有偶数的平方和以及所有奇数的立方和。
你可以认为32位整数足以保存结果。

Sample Input
1 3
2 5

Sample Output
4 28
20 152

Author
lcy

Source
C语言程序设计练习（一）

Recommend
JGShining


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:if嵌套语法

Algorithm Analyse
算法与2004题雷同，但要注意这里上以0作为结束符，而不是EOF


Problem

2008 数值统计

Problem Description
统计给定的n个数中，负数、零和正数的个数。

Input
输入数据有多组，每组占一行，每行的第一个数是整数n（n<100），表示需要统计的数值的个数，然后是n个实数；如果n=0，则表示输入结束，该行不做处理。

Output
对于每组输入数据，输出一行a,b和c，分别表示给定的数据中负数、零和正数的个数。

Sample Input
6 0 1 2 3 -1 0
5 1 2 3 4 0.5
0

Sample Output
1 2 3
0 0 5

Author
lcy

Source
C语言程序设计练习（二）

Recommend
JGShining


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:循环语法

Algorithm Analyse
循环


Problem

2009 求数列的和

Problem Description
数列的定义如下：
数列的第一项为n，以后各项为前一项的平方根，求数列的前m项的和。

Input
输入数据有多组，每组占一行，由两个整数n（n<10000）和m(m<1000)组成，n和m的含义如前所述。

Output
对于每组输入数据，输出该数列的和，每个测试实例占一行，要求精度保留2位小数。

Sample Input
81 4
2 2

Sample Output
94.73
3.41

Author
lcy

Source
C语言程序设计练习（二）

Recommend
JGShining


Problem

编码建议

Programing
从前面的算法很容易写出判断数m是否为水仙花数的函数：
int sxh(int m)
{
    int sum = 0;
    int n = m;
    while (n)
    {
        sum += (n % 10)*(n % 10)*(n % 10);
        n /= 10;
    }
    return sum == m;
}
主函数直接调用就可以了。
int main(void)
{
    int n, m, c;

    while (scanf("%d%d", &m, &n))
    {
        for (c = 0; m <= n; m++)
        {
            if (sxh(m))
                printf(c++ ? " %d": "%d", m);
        }
        puts(c ? "\n" : "no\n");
    }

    return 0;
}
测试几组数据，都是对的。就这样提交。你完全可以通过本题。
但如果你有心，你会发现。其实从1->1000之间，总共也只有5个水仙花数:

1 153 370 371 407

我们重复计算的只是这4个数字而已。
因为本题的数据两仅100->999。但万一有一题数据两非常庞大。而结果有像这次一样如此少。我们又该怎么办呢？
像这样的题目，算法很简单就可以实现，但优化也许需要我们花点时间去做，我们可以采用一种快速的“作弊”的方法:直接打表提交！
在比赛的时候，也许没有太多时间让我们去研究一道题目的算法。这样我们在思考其他题目的时间也可以用电脑来自动生成结果。
然后用哈希的思想，对每个输入的数据对应输出结果就可以了。当然，这是最没技术含量，但也是绝路上最有效的一颗救命稻草！
我这里讲这么多只是想让大家了解，应付比赛的着数是很多的。切不要思维定式了。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
前置知识:条件判断语句的语法和循环语句语法

Algorithm Analyse
这里讨论给出一个整数n，如何判断它是否为水仙花数的算法。
而判断一组数只要在外面加层循环就可以了。
  1. sum ← 0(0 赋值给 sum)
  2. n ← m
  3. 判断n是否为0，不是则进入下一步，否则跳到第7步
  4. sum += (n % 10)3
  5. n /= 10
  6. 重复第3步
  7. m 等于 sum 则返回1，否则返回0
至于输出的问题，完全可以再加个变量c，初始为0，每输出一个水仙花数都自增一次c++。
然后在c > 0时就在数字前输出一个空格。
最后判断 c > 0就只输出一个回车，否则还要输出no。


Problem

2010 水仙花数

Problem Description
春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的：
“水仙花数”是指一个三位数，它的各位数字的立方和等于其本身，比如：153=1^3+5^3+3^3。
现在要求输出所有在m和n范围内的水仙花数。

Input
输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。

Output
对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于m,并且小于等于n，如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开;
如果给定的范围内不存在水仙花数，则输出no;
每个测试实例的输出占一行。

Sample Input
100 120
300 380

Sample Output
no
370 371

Author
lcy

Source
C语言程序设计练习（二）

Recommend
JGShining


Problem

编码建议

Programing
迭代方法容易实现，如下：
for (i = 1; i <= n; i++) s += ((i & 1) ? 1.0 : -1.0) / i;
像这样的简单题，初学者就可以用它来练练手，熟悉一下递归的写法(但本题来说，递归的效率比迭代差):

这里示范第一种递推公式:
首先也定义一个函数F(n): double f(int n){}
根据公式写出条件判断:

double f(int n)
{
    if (n == 0)
        return 0;
    else if (n % 2 == 1)
        return f(n - 1) + 1.0 / n;
    else
        return f(n - 1) - 1.0 / n;
}
我们还可以简化代码，使代码更简洁紧凑。
double f(int n)
{
    return n ? f(n - 1) + ((n & 1) ? 1.0 : -1.0) / n : 0;
}
另一种递推公式也同样能用这样的方法写出代码。要不你来试试？祝你好运！^_^


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
本题的算法依然是迭代。
初始sum=0， i从1开始到n，如果1是奇数，sum += 1.0 / i; 否则 sum -= 1.0 / i;
当然，迭代是可以换成递归的。本题的递归定义为:
┌ 0 (n = 0) f(n)┼ f(n-1)+1/n (n为奇数) └ f(n-1)-1/n (n为偶数)
当然，你也可以顺着递归，这就随你喜欢了。呵呵
┌ 0 (i > n) f(i)┼ f(n+1)+1/n (n为奇数) └ f(n+1)-1/n (n为偶数)


Problem

2011 多项式求和

Problem Description
多项式的描述如下：
1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ...
现在请你求出该多项式的前n项的和。

Input
输入数据由2行组成，首先是一个正整数m（m<100），表示测试实例的个数，第二行包含m个正整数，对于每一个整数(不妨设为n,n<1000），求该多项式的前n项的和。

Output
对于每个测试实例n，要求输出多项式前n项的和。每个测试实例的输出占一行，结果保留2位小数。

Sample Input
2
1 2

Sample Output
1.00
0.50

Author
lcy

Source
C语言程序设计练习（二）

Recommend
JGShining


Problem

编码建议

Programing
首先让我们来看看这些都是什么数。
#include <stdio.h> int main(void) { int i, c; for (c = 1, i = -39; i <51; i++) { printf("%-5d", i * i + i + 41); if (c++ % 10 == 0) putchar('\n'); } return 0; } 运行结果: 1523 1447 1373 1301 1231 1163 1097 1033 971 911 853 797 743 691 641 593 547 503 461 421 383 347 313 281 251 223 197 173 151 131 113 97 83 71 61 53 47 43 41 41 43 47 53 61 71 83 97 113 131 151 173 197 223 251 281 313 347 383 421 461 503 547 593 641 691 743 797 853 911 971 1033 1097 1163 1231 1301 1373 1447 1523 1601 1681 1763 1847 1933 2021 2111 2203 2297 2393 2491 2591
最大的数是2591，数据量非常小。所以判断素数的函数也不同这么花哨了。呵呵。
对刚才的代码稍作修改，就能得到其是否为素数的判断矩阵：
#include <stdio.h>

int isprime(int n)
{
    int i;

    if (n < 2) return 0;
    for (i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

int main(void)
{
    int i, c;
    for (c = 1, i = -39; i <51; i++)
    {
        printf("%-2d", isprime(i * i + i + 41));
        //printf("%-5d", i * i + i + 41);
        if (c++ % 10 == 0) putchar('\n');
    }
    return 0;
}
运行结果:
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
0 1 1 0 1 1 1 1 0 1
把结果保存入一个数组里，直接提交。^_^


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
大家还记得第2010题的算法吧？本题也一样:打表!


Problem

2012 素数判定

Problem Description
对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。

Input
输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。

Output
对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。

Sample Input
0 1
0 0

Sample Output
OK

Author
lcy

Source
C语言程序设计练习（二）

Recommend
JGShining


Problem

编码建议

Programing
迭代的方法很简单，直接按题目意思来就可以了。
for (s = n = 1; n < 30; n++) s = (s + 1) * 2;

Math
计算机的鼻祖本来就是数学家，自然优化程序的最终方法还是要回归到数学上。
本题很容易得到它的递推方程:
f(1) = 1; f(n) = [f(n-1) + 1] × 2;
于是我们得到:
f(n) + 2 = 2 × [f(n-1) + 2]
f(1) + 2 = 3

=>

f(n) + 2 = 3 × 2n-1

=>

f(n) = 3 × 2n-1 - 2
对于这种推断题还有另外一种递推方法，虽然对于本题来说很麻烦。但有时候它是无可替代的。
f(1) = 1;
f(n) = 2f(n-1) + 2 = f(n-1) + 2f(n-2) + 4;

=>

f(n) + f(n-1) + 4 = 2 × [f(n-1) + f(n+2) + 4];

设 g(n) = f(n) + f(n-1) + 4;

则 g(n) = 2 × g(n-1);
   g(2) = f(2) + f(1) + 4 = 9;

∴g(n) = 9 × 2n-2  (n > 1)

∴f(n)   + f(n-1) = 9 × 2n-2 - 4	①
  f(n-1) + f(n-2) = 9 × 2n-3 - 4	②
  ┋
  f(3)   + f(2)   = 9 × 2 - 4
  f(2)   + f(1)   = 9 - 4

把①式减去②式得
  f(n)   = 9 × 2n-3 + f(n-2)
  f(n-2) = 9 × 2n-5 + f(n-4)
  ┋
这时候，我们需要分类讨论了:
  1. n为奇数
      f(n)   = 9 × 2n-3 + f(n-2)
  f(n-2) = 9 × 2n-5 + f(n-4)
  ┋
  f(5)   = 9 × 22 + f(3)
  f(3)   = 9 + f(1)
  f(1)   = 1

从下往上迭代，得:
  f(n) = 9 × (2n-3 + 2n-5 + ... + 22 + 1) + 1
=>
  f(n) = 9 × (1 - 4(n-1)/2) ÷ (1 - 4) + 1
=>
  f(n) = 3 × 2n - 1 - 2
  2. n为偶数
      f(n)   = 9 × 2n-3 + f(n-2)
  f(n-2) = 9 × 2n-5 + f(n-4)
  ┋
  f(4)   = 9 × 21 + f(2)
  f(2)   = 4

从下往上迭代，得:
  f(n) = 9 × (2n-3 + 2n-5 + ... + 21) + 4
=>
  f(n) = 9 × 2 × (1 - 4(n-2)/2) ÷ (1 - 4) + 4
=>
  f(n) = 3 × 2n - 1 - 2
世上的事往往如此，巧合的事情经常发生。不得不感叹大自然的美妙~
现在我们就得到了这道题目的公式了: f(n) = 3 × 2n - 1 - 2


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
本题可以直接用循环迭代过关。但是，如果你对算法有兴趣，你想知道另一种更神奇的算法吗？^_^


Problem

2013 蟠桃记

Problem Description
喜欢西游记的同学肯定都知道悟空偷吃蟠桃的故事，你们一定都觉得这猴子太闹腾了，其实你们是有所不知：悟空是在研究一个数学问题！
什么问题？他研究的问题是蟠桃一共有多少个！
不过，到最后，他还是没能解决这个难题，呵呵^-^
当时的情况是这样的：
第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个呢？

Input
输入数据有多组，每组占一行，包含一个正整数n（1<n<30），表示只剩下一个桃子的时候是在第n天发生的。

Output
对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试实例占一行。

Sample Input
2
4

Sample Output
4
22

Author
lcy

Source
C语言程序设计练习（二）

Recommend
JGShining


Problem

编码建议

Programing
我的代码采用的是第一种方法。因为对于本题来说，它的效率是O(N)。
算法不难，可以直接看代码

这里稍微讨论一下第二种方法。
对于排序，我们可以直接调用库函数qsort();

语法:

#include <stdlib.h>
void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );

功能： 对buf 指向的数据(包含num 项,每项的大小为size)进行快速排序。如果函数compare 的第一个参数小于第二个参数，返回负值；如果等于返回零值；如果大于返回正值。函数对buf 指向的数据按升序排序。

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

int cmp(const double *a, const double *b)
{
    return *a > *b ? 1 : *a < *b ? -1 : 0;
}

int main(void)
{
    int n, i;
    double x, y[100];

    while (scanf("%d", &n) != EOF)
    {
        for (i = 0 ; i < n ; i++)
            scanf("%lf", y + i);
        qsort(y, n, sizeof(double), cmp);
        for (x = 0, i = 1 ; i < n - 1 ; i++)
            x += y[i];
        printf("%.2f\n", x / (n - 2));
    }

    return 0;
}
你可能有疑问，为什么cmp函数不直接用return *a - *b;
这也就是我不打算用这种方法的原因了(虽然上面的代码可以Accpted)，这就是这段代码的不稳定因素。
我们来做个实验：
#include <math.h>
#include <stdio.h>

int main(void)
{
    int i;
    double x;

    x = 0.123456;
    printf("%lf\n", x);
    for (i = 0 ; x - floor(x); i++)
        x *= 10;
    printf("%d\n", i);

    return 0;
}
上面的代码的作用就是确定X小数点后有几位。
我相信所有人都知道它有6位小数。但它的运行结果却是17(因编译器而异)。
你可以自己复制代码去验证一下。
我们在循环体里插入printf("%lf\n", floor(x));看看它的变化是怎样的。

运行结果:
1.000000
12.000000
123.000000
1234.000000
12345.000000
123455.000000
1234559.000000
12345599.000000
123455999.000000
1234559999.000000
12345599999.000000
123455999999.000000
1234559999999.000000
12345599999999.000000
123455999999999.000000
1234559999999999.000000
12345599999999998.000000

这就是double型数据的精度问题。这是我们无法人为地控制的。所以建议尽量避免double的高精度运算。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
要实现的算法是:求整个数组的和、在数组中找最值。
找最值，可以先把第一个元素赋给max、min变量，做一次遍历，一一比较，把最大值存入max，最小值存入min。
也可以直接对数组进行排序，然后从第二个加到倒数第二个，这样就可以了，省去减两个最值。


Problem

2014 青年歌手大奖赛_评委会打分

Problem Description
青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。

Input
输入数据有多组，每组占一行，每行的第一个数是n(2<n<100)，表示评委的人数，然后是n个评委的打分。

Output
对于每组输入数据，输出选手的得分，结果保留2位小数，每组输出占一行。

Sample Input
3 99 98 97
4 100 99 98 97

Sample Output
98.00
98.50

Author
lcy

Source
C语言程序设计练习（三）

Recommend
lcy


Problem

编码建议

Programing
从题目中可以看出，当这一组的第一个数是X时，下一组的第一个数就是X+2*m
而从X开始连续m个偶数的和就是:
{X + [X + 2×(m - 1)]} × m / 2 = (X + m - 1) × m;
所以平均数就是X + m - 1


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
解决这个问题，关键是要解决给出一个偶数X，求出从它开始连续的m个偶数的和
而这个问题只要用等差数列求和公式就可以了。


Problem

2015 偶数求和

Problem Description
有一个长度为n(n<=100)的数列，该数列定义为从2开始的递增有序偶数，现在要求你按照顺序每m个数求出一个平均值，如果最后不足m个，则以实际数量求平均值。编程输出该平均值序列

Input
输入数据有多组，每组占一行，包含两个正整数n和m，n和m的含义如上所述。

Output
对于每组输入数据，输出一个平均值序列，每组输出占一行。

Sample Input
3 2
4 2

Sample Output
3 6
3 7

Author
lcy

Source
C语言程序设计练习（三）

Recommend
lcy


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
因为这题涉及交换，所以在寻找最小值的时候不需要记录它的值，只要记录下它的下标就可以。


Problem

2016 数据的交换输出

Problem Description
输入n(n<100)个数，找出其中最小的数，将它与最前面的数交换后输出这些数。

Input
输入数据有多组，每组占一行，每行的开始是一个整数n，表示这个测试实例的数值的个数，跟着就是n个整数。n=0表示输入的结束，不做处理。

Output
对于每组输入数据，输出交换后的数列，每组输出占一行。

Sample Input
4 2 1 3 4
5 5 4 3 2 1
0

Sample Output
1 2 3 4
1 4 3 2 5

Author
lcy

Source
C语言程序设计练习（三）

Recommend
lcy


Problem

编码建议

Programing
判断是否为数字，直接调用库函数isdigit();

语法:

#include <ctype.h>
int isdigit( int ch );

功能：如果参数是0到9之间的数字字符，函数返回非零值，否则返回零值.


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
因为本题只要求输出每一行数字的个数。所以不需要把那些字符记录下来。
因此不需要开个字符数组去记录。而且如果你想开也不知道该开多大，因为题目中没有提示一行最多有几个。
而判断行末就判断是否为'\n'就可以。


Problem

2017 字符串统计

Problem Description
对于给定的一个字符串，统计其中数字字符出现的次数。

Input
输入数据有多行，第一行是一个整数n，表示测试实例的个数，后面跟着n行，每行包括一个由字母和数字组成的字符串。

Output
对于每个测试实例，输出该串中数值的个数，每个输出占一行。

Sample Input
2
asdfasdf123123asdfasdf
asdf111111111asdfasdfasdf

Sample Output
6
9

Author
lcy

Source
C语言程序设计练习（三）

Recommend
lcy


Problem

编码建议

Programing
知道了递推的规律，就可以写出方程了:
f(n) = f(n-1) + f(n-3); (n > 3)
f(n) = n; (n <= 3)
因为这是重复计算的过程。你可以把结果都保存在数组里。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。
简单的递推题

Algorithm Analyse
递推题我很喜欢，它们写出来的代码都很简单。但关键看你能不能找到规律。
本题中，第n年的牛的来源有2中:
  • 第n-1年的牛
  • 第n-3年的牛所生的小牛
而递推的出口是第1年为1头，第2年为2头，第3年为3头。


Problem

2018 母牛的故事

Problem Description
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

Input
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

Output
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

Sample Input
2
4
5
0

Sample Output
2
4
6

Author
lcy

Source
C语言程序设计练习（三）

Recommend
lcy


Problem

编码建议

Programing
很轻松就可以算法描述里的伪代码换成自己熟悉的语言。
而本题的要求更简单，只要做一趟插入排序就可以了！试试看，祝你好运！


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
本题目其实就是让你实现一次插入排序。
插入排序的工作机理与很多人打牌时，整理手中牌时的做法差不多。在开始摸牌时，我们的左手是空的，牌面朝下放在桌上。
接这，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的每一张牌从右到左地进行比较。
无论在什么时候，左手中的牌都是排好序的，而这些牌原先都是桌上那副牌里最顶上的有一些牌。

下面是插入排序的伪代码：

INSERTION-SORT(A) 1 for j←2 to length[A] 2 do key←A[j] 3 /*Insert A[j]into the sorted sequence A[1..j-1].*/ 4 i←j - 1 5 while i>0 and A[j]>key 6 do A[i+1]←A[i] 7 i←i - 1 8 A[i+1]←key


Problem

2019 数列有序!

Problem Description
有n(n<=100)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请将该数插入到序列中，并使新的序列仍然有序。

Input
输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。

Output
对于每个测试实例，输出插入新的元素后的数列。

Sample Input
3 3
1 2 4
0 0

Sample Output
1 2 3 4

Author
lcy

Source
C语言程序设计练习（三）

Recommend
lcy


Problem

编码建议

Programing
你可以自己写一个判断大小的函数int cmp(a, b)
如果a > b返回大于0的值，a = b 返回0，a < b 返回小于0的值
ANSI C里的qsort()就是这样做的。用一个比较函数来提高排序函数的通用性。
这里的比较规则就是return abs(*b) - abs(*a);


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
这题的考点就是排序。
对初学者来说，比较熟悉的排序是“冒泡排序”和“选择排序”。
在排升序的时候，元素比较用'<'，降序用'>'。
对于整数等基本数据类型，这样的比较符号很容易理解。但换了其他比较规则，你是不是还能很好地理解呢？呵呵。
就像本题的规则：比较数的绝对值的大小，在这里-3 > 1，所以就不能直接用'>'，而是要自己制定一套大小规则。
刚开始可能不习惯看到 -3 > 1这样的规则，熟悉后就好了。


Problem

2020 绝对值排序

Problem Description
输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。

Input
输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。

Output
对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。

Sample Input
3 3 -4 2
4 0 1 2 -3
0

Sample Output
-4 3 2
-3 2 1 0

Author
lcy

Source
C语言程序设计练习（三）

Recommend
lcy


Problem

编码建议

Programing
求某一面额的张数，用的方法是整除求余法。
比如325块钱需要几张100块。就是325 / 100 = 3 … 25即三张100，余下25元。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
这道题可以简化为给定面额，求需要的人民币的张数。
用的方法是贪心。这不难理解，用的人民币的面值越大，当然张数就越少。


Problem

2021 发工资咯：）

Problem Description
作为杭电的老师，最盼望的日子就是每月的8号了，因为这一天是发工资的日子，养家糊口就靠它了，呵呵
但是对于学校财务处的工作人员来说，这一天则是很忙碌的一天，财务处的小胡老师最近就在考虑一个问题：如果每个老师的工资额都知道，最少需要准备多少张人民币，才能在给每位老师发工资的时候都不用老师找零呢？
这里假设老师的工资都是正整数，单位元，人民币一共有100元、50元、10元、5元、2元和1元六种。

Input
输入数据包含多个测试实例，每个测试实例的第一行是一个整数n（n<100），表示老师的人数，然后是n个老师的工资。 n=0表示输入的结束，不做处理。

Output
对于每个测试实例输出一个整数x,表示至少需要准备的人民币张数。每个输出占一行。

Sample Input
3
1 2 3
0

Sample Output
4

Author
lcy

Source
C语言程序设计练习（四）

Recommend
lcy


Problem

编码建议

Programing
虽然这题算法简单，但是会有一个陷阱！
我们知道，有符号long型能表示的范围是-2147483648 ~ 2147483647。你会发现。负数的范围其实比正数大。
所以，如果你直接用long型，然后用abs来取绝对值，就可能造成数据溢出。你可以自己试一下输出abs(-2147483648)的值。
解决方法是可以用double型来替换它。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
这题没什么技巧可言，只是从以前的在一维数组里找最值扩大到二维数组而已。


Problem

2022 海选女主角

Problem Description
potato老师虽然很喜欢教书，但是迫于生活压力，不得不想办法在业余时间挣点外快以养家糊口。
“做什么比较挣钱呢？筛沙子没力气，看大门又不够帅...”potato老师很是无奈。
“张艺谋比你还难看，现在多有钱呀，听说还要导演奥运开幕式呢！你为什么不去娱乐圈发展呢？”lwg在一旁出主意。
嗯，也是，为了生存，就委屈点到娱乐圈混混吧，马上就拍一部激光电影《杭电记忆——回来我的爱》。
说干就干，马上海选女主角（和老谋子学的，此举可以吸引媒体的眼球，呵呵），并且特别规定，演员必须具有ac的基本功，否则直接out!
由于策划师风之鱼（大师级水王）宣传到位，来应聘的MM很多，当然包括nit的蛋糕妹妹等呼声很高的美女，就连zjut的jqw都男扮女装来应聘（还好被安全顾问hdu_Bin-Laden认出，给轰走了），看来娱乐圈比acm还吸引人哪...
面试那天，刚好来了m*n个MM，站成一个m*n的队列，副导演Fe(OH)2为每个MM打了分数，分数都是32位有符号整数。
一开始我很纳闷：分数怎么还有负的？Fe(OH)2解释说，根据选拔规则，头发染成黄色、化妆太浓、穿的太少等等都要扣分数的，扣的多了就可能是负分了，当然，如果发现话语中夹有日语，就直接给-2147483648分了。
分数送上来了，是我做决定的时候了，我的一个选拔原则是，要选一个面试分数绝对值（必须还是32位整数）最大的MM。
特别说明：如果不幸选中一个负分的MM,也没关系，因为我觉得，如果不能吸引你，那要想法恶心你。

Input
输入数据有多组，每组的第一行是两个整数m和n，表示应聘MM的总共的行列数，然后是m行整数，每行有n个，m和n的定义见题目的描述。

Output
对于每组输入数据，输出三个整数x,y和s，分别表示选中的MM的行号、列号和分数。
note:行号和列号从一开始，如果有多个MM的分数绝对值一样，那么输出排在最前面的一个（即行号最小的那个，如果行号相同则取列号最小的那个）。

Sample Input
2 3
1 4 -3
-7 3 0

Sample Output
2 1 -7

Author
lcy

Source
C语言程序设计练习（四）

Recommend
lcy


Problem

编码建议

Programing
如果你有更好更简单的方法，欢迎和我们一起分享。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
只是简单的循环+条件判断。


Problem

2023 求平均成绩

Problem Description
假设一个班有n(n<=50)个学生，每人考m(m<=5)门课，求每个学生的平均成绩和每门课的平均成绩，并输出各科成绩均大于等于平均成绩的学生数量。

Input
输入数据有多个测试实例，每个测试实例的第一行包括两个整数n和m，分别表示学生数和课程数。然后是n行数据，每行包括m个整数（即：考试分数）。

Output
对于每个测试实例，输出3行数据，第一行包含n个数据，表示n个学生的平均成绩，结果保留两位小数；第二行包含m个数据，表示m门课的平均成绩，结果保留两位小数；第三行是一个整数，表示该班级中各科成绩均大于等于平均成绩的学生数量。
每个测试实例后面跟一个空行。

Sample Input
2 2
5 10
10 20

Sample Output
7.50 15.00
7.50 15.00
1

Author
lcy

Source
C语言程序设计练习（四）

Recommend
lcy


Problem

编码建议

Programing
多用库函数，勤用库函数。

isalpha
语法:

#include <ctype.h>
int isalpha( int ch );

功能：如果参数是字母字符，函数返回非零值，否则返回零值。

isalnum
语法:

#include <ctype.h>
int isalnum( int ch );

功能：如果参数是数字或字母字符，函数返回非零值，否则返回零值。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
直接按题目的描述来做就可以了。
先判断是不是以下划线或字母开头，然后依次判断后面的字符是不是都为数字或字母。


Problem

2024 C语言合法标识符

Problem Description
输入一个字符串，判断其是否是C的合法标识符。

Input
输入数据包含多个测试实例，数据的第一行是一个整数n,表示测试实例的个数，然后是n行输入数据，每行是一个长度不超过50的字符串。

Output
对于每组输入数据，输出一行。如果输入数据是C的合法标识符，则输出"yes"，否则，输出“no”。

Sample Input
3
12ajf
fi8x_a
ff ai_2

Sample Output
no
yes
no

Author
lcy

Source
C语言程序设计练习（四）

Recommend
lcy


Problem

编码建议

Programing
找到最大值后，只要用putchar()逐个输出，然后判断输出的是不是最大值，是就再输出一个(max)，就是这么简单！


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
依然是找最大值^_^


Problem

2025 查找最大元素

Problem Description
对于输入的每个字符串，查找其中的最大字母，在该字母后面插入字符串“(max)”。

Input
输入数据包括多个测试实例，每个实例由一行长度不超过100的字符串组成，字符串仅由大小写字母构成。

Output
对于每个测试实例输出一行字符串，输出的结果是插入字符串“(max)”后的结果，如果存在多个最大的字母，就在每一个最大字母后面都插入"(max)"。

Sample Input
abcdefgfedcba
xxxxx

Sample Output
abcdefg(max)fedcba
x(max)x(max)x(max)x(max)x(max)

Author
lcy

Source
C语言程序设计练习（四）

Recommend
lcy


Problem

编码建议

Programing
算法知道了，其实实现起来更简单，让保存字符串的数组第一个为空格，而读数据时从第二个开始保存。
这样实现起来可以很简洁。具体的请参见源码。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
问题的关键在于如何判断为单词的首字母。
方法也不难，只要你判断当前字符为字母，而前一个为空格就可以了。
为了简单处理整个字符串的第一个字符。你可以让保存前一个字符的变量初始为空格。
这样就可以把判断规则统一起来了，不用特殊处理字符串的第一个字符。


Problem

2026 首字母变大写

Problem Description
输入一个英文句子，将每个单词的第一个字母改成大写字母。

Input
输入数据包含多个测试实例，每个测试实例是一个长度不超过100的英文句子，占一行。

Output
请输出按照要求改写后的英文句子。

Sample Input
i like acm
i want to get an accepted

Sample Output
I Like Acm
I Want To Get An Accepted

Author
lcy

Source
C语言程序设计练习（四）

Recommend
lcy


Problem

编码建议

Programing
也许字母会有大小写之分，记得用tolower()或toupper()换成统一的格式就可以了。

tolower
语法:

#include <ctype.h> int tolower( int ch );

功能：函数字符ch的小写形式。

toupper
语法:

#include <ctype.h> int toupper( int ch );

功能：函数字符ch的大写形式。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
这一题，只要懂得switch语法就可以了。 当然，用if嵌套也没问题。^_^


Problem

2027 统计元音

Problem Description
统计每个元音字母在字符串中出现的次数。

Input
输入数据首先包括一个整数n，表示测试实例的个数，然后是n行长度不超过100的字符串。

Output
对于每个测试实例输出5行，格式如下：
a:num1
e:num2
i:num3
o:num4
u:num5
多个测试实例之间由一个空行隔开。

请特别注意：最后一块输出后面没有空行：）

Sample Input
2
aeiou
my name is ignatius

Sample Output
a:1
e:1
i:1
o:1
u:1

a:2
e:1
i:3
o:0
u:1

Author
lcy

Source
C语言程序设计练习（四）

Recommend
lcy


Problem

编码建议

Programing
我这里用GCD递归定理：对任意非负数a 和 任意正整数b,
gcd(a, b) = gcd(b, a mod b)
这个就是欧几里德算法了。

Math
GCD递归定理的证明。

有很多人喜欢打破沙锅问到底。
曾经很多人也问过我gcd算法的原理，这里给你们回答:

下面提到的 a|b 就是表示a能被b整除。
首先我们来看一下两条定理，都很好理解的。

  1. d|a 并且 d|b 蕴含着 d|(ax + by) ①
  2. a|b 且 b|a 蕴含着 a = ±b ②
从上述②式就可以看出，只要证明gcd(a, b) 与 gcd(b, a mod b)可以互相整除，就能证明它们相等。
先来证明gcd(a, b) | gcd(b, a mod b)。
设d = gcd(a, b) => 1. d|a 2. d|b ∵(a mod b) = a - q×b; (q = 「a/b」) 即(a mod b)是a与b的线性组合。 由①式得: d | (a - q×b) <==> d | (a mod b) 由①式得: d | gcd(b, a mod b) <==> gcd(a, b) | gcd(b, a mod b) ③
证明gcd(b, a mod b) | gcd(a, b)。
设d = gcd(b, a mod b) => 1. d|b 2. d|(a mod b) ∵a = (a mod b) + q×b; (q = 「a/b」) 即 a 是b与(a mod b)的线性组合。 由①式得: d | a ∵d | b 由①式得: d | gcd(a, b) <==> gcd(b, (a mod b)) | gcd(a, b) ④
运用定理②，在根据③④就可以完成GCD定理的证明。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
最小公倍数lcm(x, y) = x * y / gcd(x, y) (其中gcd()求最大公约数)
所以这题的关键的关键是求最大公约数。


Problem

2028 Lowest Common Multiple Plus

Problem Description
求n个数的最小公倍数。

Input
输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。

Output
为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。

Sample Input
2 4 6
3 2 5 7

Sample Output
12
70

Author
lcy

Source
C语言程序设计练习（五）

Recommend
lcy


Problem

编码建议

Programing
代码很容易写:
#include <stdio.h>
#include <string.h>

int main(void)
{
    int n, len, i;
    char s[1024];

    scanf("%d%*c", &n);

    while (n--)
    {
        gets(s);
        len = strlen(s);
        for (i = 0; i <= len / 2; i++)
        {
            if (s[i] != s[len - 1 - i])
                break;
        }
        puts(s[i] != s[len - 1 - i] ? "no" : "yes");
    }

    return 0;
}
对于这题还有更方便的。
库函数strrev()可以倒置字符串。
呵呵，详见参考代码。


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
得到字符串长度len
i从0循环到len / 2;
比较string[i] 与 string[len - i - 1] 是否相同;


Problem

2029 Palindromes_easy version

Problem Description
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。请写一个程序判断读入的字符串是否是“回文”。

Input
输入包含多个测试实例，输入数据的第一行是一个正整数n,表示测试实例的个数，后面紧跟着是n个字符串。

Output
如果一个字符串是回文串，则输出"yes",否则输出"no".

Sample Input
4
level
abcde
noon
haha

Sample Output
yes
no
yes
no

Author
lcy

Source
C语言程序设计练习（五）

Recommend
lcy


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
汉字占双字节，高位的字节里都是 < 0,所以只要统计小于0的字符的个数。


Problem

2030 汉字统计

Problem Description
统计给定文本文件中汉字的个数。

Input
输入文件首先包含一个整数n，表示测试实例的个数，然后是n段文本。

Output
对于每一段文本，输出其中的汉字的个数，每个测试实例的输出占一行。

[Hint:]从汉字机内码的特点考虑~

Sample Input
2
WaHaHa! WaHaHa! 今年过节不说话要说只说普通话WaHaHa! WaHaHa!
马上就要期末考试了Are you ready?

Sample Output
14
9

Author
lcy

Source
C语言程序设计练习（五）

Recommend
lcy


Problem

编码建议

Programing
从上面的算法可以看出，数制转换需要逆序输出，就需要用到栈。所以我们直接用递归调用了。^_^


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
【数制换算的一般方法】
  1. 把r进数转换成十进制数，只要把r进制数写成r的各次幂的和的形式。然后按十进制计算结果。(这里r是大于1的自然数)
    例如: (205.21)8 = 2 × 82 + 0 × 81 + 5 × 80 + 2 × 8-1 + 1 × 8-2
  2. 把十进制换成r进制，可以把十进制化成r的各次幂(各次幂的系数小于r而大于或等于0的整数)的和，从最高次幂起各次幂的系数就是依次的r进制从左到右各个数位上的数字。
    1. 当十进制数是整数时，采用“r除取余”法。即用数r除十进整数。取它的每次余数。
      例如:把(746)10化为一个八进制的数。
      8|746 ---- 8|93 --- 2 --- 8|11 --- 5 --- 8|1 --- 3 -- 0 --- 1
      得到(746)10 = (1352)8
    2. 当十进制是小数时，采用“r乘取整”法，即用数r乘十进制小数，每乘一次取一次整数，直至小数部分变成零为止。
      例如:把(0.8125)10化为二进制。
      0.|8125 ×| 2 ------- 1.|6250 ×| 2 ------- 1.|2500 ×| 2 ------- 0.|5000 ×| 2 ------- 1.|0000
      得到(0.8125)10 = (0.1101)2
    3. 把r1进制数转换成r2进制数，一般可以先把r1进制数转换成十进制数，再从十进制数转换成r2进制数。


Problem

2031 进制转换

Problem Description
输入一个十进制数N，将它转换成R进制数输出。

Input
输入数据包含多个测试实例，每个测试实例包含两个整数N(32位整数)和R（2<=R<=16, R<>10）。

Output
为每个测试实例输出转换后的数，每个输出占一行。如果R大于10，则对应的数字规则参考16进制（比如，10用A表示，等等）。

Sample Input
7 2
23 12
-4 3

Sample Output
111
1B
-11

Author
lcy

Source
C语言程序设计练习（五）

Recommend
lcy


Problem

编码建议

Programing
因为f(i, j) = f(i-1, j) + f(i-1, j-1)，所以我们在编程的时候，完全可以只开一个一维数组。
从i倒退到1，执行A[j] += A[j-1];这样就得到第i行的结果了~


Problem

问题分析

Problem Analyse
本题是为C语言初学者提供的。

Algorithm Analyse
把杨辉三角压缩进数组中，就会发现它的规律:
f(i, i) = f(i, 1) = 1 (i > 0) f(i, j) = f(i-1, j) + f(i-1, j-1) (j < i)
或者 f(i, j) = Cji


Problem

2032 杨辉三角

Problem Description
还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Input
输入数据包含多个测试实例，每个测试实例的输入只包含一个正整数n（1<=n<=30），表示将要输出的杨辉三角的层数。

Output
对应于每一个输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开，每一个杨辉三角后面加一个空行。

Sample Input
2 3

Sample Output
1
1 1

1
1 1
1 2 1

Author
lcy

Source
C语言程序设计练习（五）

Recommend
lcy


Problem

编码建议

Programing
对每一位加完求60的余数就可以了。不要忘了进位哦。^_^


Problem

问题分析

Problem Analyse
其实这是一道数值进制问题。

Algorithm Analyse
我们平时用的是十进制，规则是逢10进1，而时间是六十进制，就是逢60进1位。
本题就是让你做一个60进制的加法运算。


Problem

2033 人见人爱A+B

Problem Description
HDOJ上面已经有10来道A+B的题目了，相信这些题目曾经是大家的最爱，希望今天的这个A+B能给大家带来好运，也希望这个题目能唤起大家对ACM曾经的热爱。
这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。

Input
输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。题目保证所有的数据合法。

Output
对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0~59），每个输出占一行，并且所有的部分都可以用32位整数表示。

Sample Input
2
1 2 3 4 5 6
34 45 56 12 23 34

Sample Output
5 7 9
47 9 30

Author
lcy

Source
ACM程序设计期末考试（2006/06/07）

Recommend
lcy


Problem

编码建议

Programing
以下所有代码均能AC。

你可以直接用C语言去模拟一个集合，然后每读入一个数字，做一次遍历，如果找到就删除。最后才排一次序输出。
虽然效率很低，时间复杂度有O(m*n)，但对付这一题已经绰绰有余了。也可以0MS 0K AC掉。

Code:

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

int cmp(const int *a, const int *b)
{
    return *a - *b;
}

int main(void)
{
    int n, m, i, j;
    int s[101];

    while (scanf("%d%d", &n, &m), m+n)
    {
        for (i = 0; i < n; i++)
            scanf("%d", s + i);
        for (i = 0; i < m; i++)
        {
            scanf("%d", s + n);
            for (j = 0; s[j] != s[n]; j++);
            if (j != n) s[j] = s[--n];
        }
        qsort(s, n, sizeof(int), cmp);
        for (i = 0; i < n; i++)
            printf("%d ", s[i]);
        printf(n ? "\n" : "NULL\n");
    }

    return 0;
}
如果你讨厌用线性的查找方式，也可以修改一下。配合使用库函数的二分找和快速排序，来实现。
但对付这题来说，有点杀鸡用牛刀的感觉，呵呵。
Code:
#include <stdio.h>
#include <stdlib.h>

int cmp(const int *a, const int *b)
{
    return *a - *b;
}

int main(void)
{
    int a;
    int b;
    int i;
    int n;
    int *p;
    int s[128];

    while (scanf("%d%d", &a, &b), a || b)
    {
        for (i = 0 ; i < a ; i++)
            scanf("%d", s + i);

        qsort(s, a, sizeof(int), cmp);

        for (i = 0 ; i < b ; i++)
        {
            scanf("%d", &n);
            p = bsearch(&n, s, a, sizeof(int), cmp);
            if (p)
            {
                a--;
                *p = s[a];
                qsort(s, a, sizeof(int), cmp);
            }
        }

        if (a)
        {
            for (i = 0 ; i < a ; i++)
                printf("%d ", s[i]);
            putchar('\n');
        }
        else
            puts("NULL");
    }

    return 0;
}
其实我们可以用归并排序的思想来做。效率从O(m*n) -> O((m+n)log2(m+n))
#include <stdio.h>
#include <stdlib.h>

int cmp(const int *a, const int *b)
{
    return *a - *b;
}

int main(void)
{
    int n, m, i, j, c;
    int s[128];
    int t[128];

    while (scanf("%d%d", &n, &m), m+n)
    {
        for (i = 0; i < n; i++)
            scanf("%d", s + i);
        for (i = 0; i < m; i++)
            scanf("%d", t + i);
        qsort(s, n, sizeof(int), cmp);
        qsort(t, m, sizeof(int), cmp);
        for (c = i = j = 0; i < n && j < m;)
        {
            if (s[i] < t[j])
                printf("%d ", s[i++], c++);
            else if (s[i] > t[j])
                j++;
            else
            {
                i++;
                j++;
            }
        }
        for (; i < n;) printf("%d ", s[i++], c++);
        printf(c ? "\n" : "NULL\n");
    }

    return 0;
}
其实这些集合的操作都包含在C++的set类库里了。
这时候用C++编码真是提速不少。详请参见参考代码。


Problem

问题分析

Problem Analyse
集合论

Algorithm Analyse
集合的减法 A-B的意义是:在集合A中去掉所有与集合B中相同的元素，剩下的内容就是结果。


Problem

2034 人见人爱A-B

Problem Description
参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）

呵呵，很简单吧？

Input
每组输入数据占1行,每行数据的开始是2个整数n(0<n<=100)和m(0<m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束，不做处理。

Output
针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.

Sample Input
3 3 1 2 3 1 4 7
3 7 2 5 8 2 3 4 5 6 7 8
0 0

Sample Output
2 3
NULL

Author
lcy

Source
ACM程序设计期末考试（2006/06/07）

Recommend
lcy


Problem

编码建议

Programing
迭代的算法很简单。
Code:
#include <stdio.h>

int main(void)
{
    int a;
    int b;
    int i;
    int sum;

    while (scanf("%d%d", &a, &b), a || b)
    {
        sum = a;

        for (i = 1 ; i < b ; i++)
            sum = (sum * a) % 1000;

        printf("%d\n", sum % 1000);
    }

    return 0;
}
递归程序其实就是用了分而治之(Divide.and.Conquere)的策略。
X4可以用X2自乘的关系，可以大量地降低乘法数目。
连乘n次要n-1个乘法，而分治只要2log2n个乘法。


Problem

问题分析

Problem Analyse
数值自乘

Algorithm Analyse
mn就是把m连乘n次，虽然效率低，但应付本题也可以0MS 0K AC了
如果你也想得到一个更有效率的算法，可以看看下面公式，有灵感吗？
    1	n = 0
mn = 	(mk)2	n = 2k
    m·m2k	n = 2k + 1


Problem

2035 人见人爱A^B

Problem Description
求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”

Input
输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。

Output
对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

Sample Input
2 3
12 6
6789 10000
0 0

Sample Output
8
984
1

Author
lcy

Source
ACM程序设计期末考试（2006/06/07）

Recommend
lcy


Problem

编码建议

Programing
算法知道了就很轻松了，编程的时候只要保存第1个点的坐标就可以了。其他的就不浪费空间了。^_^


Problem

问题分析

Problem Analyse
求多边形面积

Algorithm Analyse
可以利用多边形求面积公式：
S = 0.5 * ( (x0*y1-x1*y0) + (x1*y2-x2*y1) + ... + (xn*y0-x0*yn) )
其中点(x0, y0), (x1, y1), ... , (xn, yn)为多边形上按逆时针顺序的顶点。

简要证明：
1.我们先简单地从三个点入手(包括原点)。

面积S△OAB = SABCD - S△OAD - S△OBC

  ·SABCD = (y0 + y1) × (x0 - x1) ÷ 2
  ·S△OAD = x0 × y0 ÷ 2
  ·S△OBC = (-x1) × y1 ÷ 2

S△OAB 	= (x0 × y0 + x0 × y1 - x1 × y0 - x1 × y1 - x0 × y0 + x1 × y1) ÷ 2
    = (x0 × y1 - x1 × y0) ÷ 2
公式成立。同理你可以算出其他情况也能符合这个公式。
2.假设该公式对于n个顶点的多边形成立。即：
S = 0.5 * ( (x0*y1-x1*y0) + (x1*y2-x2*y1) + ... + (xn*y0-x0*yn) )

再加如第n+1点后，面积S' = S + S△A0AnAn+1

  ·S = 0.5 * ( (x0*y1-x1*y0) + (x1*y2-x2*y1) + ... + (xn*y0-x0*yn) )
  ·S△A0AnAn+1 = 0.5 * ( (X0*Yn-Xn*Y0) + (Xn*Yn+1-Xn+1*Yn) + (Xn+1*Y0-X0*Yn+1) )

∴S' = S = 0.5 * ( (X0*Y1-X1*Y0) + (X1*Y2-X2*Y1) + ... + (Xn*Yn+1-Xn+1*Yn) + (Xn+1*Y0-X0*Yn+1) )
综上所述，得到公式：S = 0.5 * ( (x0*y1-x1*y0) + (x1*y2-x2*y1) + ... + (xn*y0-x0*yn) )
得证！


Problem

2036 改革春风吹满

Problem Description
“ 改革春风吹满地,
不会AC没关系;
实在不行回老家，
还有一亩三分地。
谢谢!（乐队奏乐）”

话说部分学生心态极好，每天就知道游戏，这次考试如此简单的题目，也是云里雾里，而且，还竟然来这么几句打油诗。
好呀，老师的责任就是帮你解决问题，既然想种田，那就分你一块。
这块田位于浙江省温州市苍南县灵溪镇林家铺子村，多边形形状的一块地，原本是linle 的，现在就准备送给你了。不过，任何事情都没有那么简单，你必须首先告诉我这块地到底有多少面积，如果回答正确才能真正得到这块地。
发愁了吧？就是要让你知道，种地也是需要AC知识的！以后还是好好练吧...

Input
输入数据包含多个测试实例，每个测试实例占一行，每行的开始是一个整数n(3<=n<=100)，它表示多边形的边数（当然也是顶点数），然后是按照逆时针顺序给出的n个顶点的坐标（x1, y1, x2, y2... xn, yn）,为了简化问题，这里的所有坐标都用整数表示。
输入数据中所有的整数都在32位整数范围内，n=0表示数据的结束，不做处理。

Output
对于每个测试实例，请输出对应的多边形面积，结果精确到小数点后一位小数。
每个实例的输出占一行。

Sample Input
3 0 0 1 0 0 1
4 1 0 0 1 -1 0 0 -1
0

Sample Output
0.5
2.0

Author
lcy

Source
ACM程序设计期末考试（2006/06/07）

Recommend
lcy


Problem

问题分析

Problem Analyse
一维数组上的动态规划

Algorithm Analyse
说是动态规划，其实也有点贪心的思想。
一维数组里保存的的就是以当前节目作为开始，最多能完整地看多少个不同的节目。
很明显，播出时间最晚的节目只是能1。
我采取从后往前的规划方法。
这样，当循环到i时，能保证数组里 D[i+1] -> D[n-1] 保存的都是最优解。
所以让j 从 i+1 到 n-1 循环，找出看完第i个节目后最多还能看的节目数max。(不要忘了判断能否完整收看哦)
把max+1 保存到 D[i]里。如此下去直到结束。


Problem

2037 今年暑假不AC

Problem Description
“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

Input
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

Sample Output
5

Author
lcy

Source
ACM程序设计期末考试（2006/06/07）

Recommend
lcy


Problem

编码建议

Programing


Problem

问题分析

Problem Analyse

Algorithm Analyse


Problem

2038 test

Problem Description

Input

Output

Sample Input

Sample Output

Author

Source

Recommend


Problem

编码建议

Programing
读数据的时候，不要忘了三条边要用实数型，而不是整型。^_^


Problem

问题分析

Problem Analyse
基本数学知识

Algorithm Analyse
如果a, b, c三条边能组成三角形，则
a + b > c
a + c > b
b + c > a


Problem

2039 三角形

Problem Description
给定三条边，请你判断一下能不能组成一个三角形。

Input
输入数据第一行包含一个数M，接下有M行，每行一个实例，包含三个正数A,B,C。其中A,B,C <1000;

Output
对于每个测试实例，如果三条边长A,B,C能组成三角形的话，输出YES，否则NO。

Sample Input
2
1 2 3
2 2 2

Sample Output
NO
YES

Author
linle

Source
2005实验班短学期考试

Recommend
lcy


Problem

编码建议

Programing
有些人想用1->sqrt(n)来循环提高效率。其实一个对计算机来说，求一个实数开方时间远大于整数的计算。用sqrt()函数可能适得其反。


Problem

问题分析

Problem Analyse
C基本语法

Algorithm Analyse
得到数据n后，只要循环1->n/2，找出所有的因子累加就可以了。


Problem

2040 亲和数

Problem Description
古希腊数学家毕达哥拉斯在自然数研究中发现，220的所有真约数(即不是自身的约数)之和为：

1+2+4+5+10+11+20+22+44+55+110＝284。

而284的所有真约数为1、2、4、71、 142，加起来恰好为220。人们对这样的数感到很惊奇，并称之为亲和数。一般地讲，如果两个数中任何一个数都是另一个数的真约数之和，则这两个数就是亲和数。

你的任务就编写一个程序，判断给定的两个数是否是亲和数

Input
输入数据第一行包含一个数M，接下有M行，每行一个实例,包含两个整数A,B； 其中 0 <= A,B <= 600000 ;

Output
对于每个测试实例，如果A和B是亲和数的话输出YES，否则输出NO。

Sample Input
2
220 284
100 200

Sample Output
YES
NO

Author
linle

Source
2005实验班短学期考试

Recommend
lcy


Problem

编码建议

Programing
数值可能很大，用unsigned long 可能溢出。要用__int64(VC++)或long long(GCC)


Problem

问题分析

Problem Analyse
简单递推

Algorithm Analyse
由题目可知，每次只能走一级或两级。
因此从第一级走上第二级只能走一步，只有1种走法。
从第一级走上第三级，可以从第一级直接走两步，也可以从第二级走一步。有2种走法
走上第n级，可以从第n-1级走一步上来，也可以从第n-2级走两步上来。

即:
f(2) = 1
f(3) = 2
f(n) = f(n-1) + f(n-2) (n > 3)

是一个斐波那契函数。


Problem

2041 超级楼梯

Problem Description
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

Input
输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output
对于每个测试实例，请输出不同走法的数量

Sample Input
2
2
3

Sample Output
1
2

Author
lcy

Source
2005实验班短学期考试

Recommend
lcy


Problem

编码建议

Programing
迭代循环体:
for(s = 3; n--; s = (s - 1) * 2);
printf("%d\n", s);

Math
本题很容易得到它的递推方程:
f(0) = 3;
f(1) = 4;
f(n) = [f(n-1) - 1] × 2;
于是我们得到:
f(n) - 2 = 2 × [f(n-1) - 2];
f(0) - 2 = 3 - 2 = 1;

=>

f(n) - 2 = 2n;

=>

f(n) = 2n + 2;
和2013题一样，这一题也有麻烦的推法。仅做参考用。
f(0) = 3
f(1) = 4;
f(n) = 2f(n-1) - 2 = f(n-1) + 2f(n-2) - 4;

=>

f(n) + f(n-1) - 4 = 2 × [f(n-1) + f(n+2) - 4];

设 g(n) = f(n) + f(n-1) - 4;

则 g(n) = 2 × g(n-1);
   g(1) = f(1) + f(0) - 4 = 3;

∴g(n) = 3 × 2n-1  (n > 0)

∴f(n)   + f(n-1) = 3 × 2n-1 + 4	①
  f(n-1) + f(n-2) = 3 × 2n-2 + 4	②
  ┋
  f(2)   + f(1)   = 3 × 2 + 4
  f(1)   + f(0)   = 3 + 4

把①式减去②式得
  f(n)   = 3 × 2n-2 + f(n-2)
  f(n-2) = 3 × 2n-4 + f(n-4)
  ┋
这时候，我们需要分类讨论了:
  1. n为奇数
      f(n)   = 3 × 2n-2 + f(n-2)
  f(n-2) = 3 × 2n-4 + f(n-4)
  ┋
  f(5)   = 3 × 23 + f(3)
  f(3)   = 3 × 2 + f(1)
  f(1)   = 4

从下往上迭代，得:
  f(n) = 3 × (2n-2 + 2n-4 + ... + 23 + 2) + 4
=>
  f(n) = 3 × 2 × (1 - 4(n-1)/2) ÷ (1 - 4) + 4
=>
  f(n) = 2n + 2
  2. n为偶数
      f(n)   = 3 × 2n-2 + f(n-2)
  f(n-2) = 3 × 2n-4 + f(n-4)
  ┋
  f(4)   = 3 × 22 + f(2)
  f(2)   = 3 + f(0)
  f(0)   = 3

从下往上迭代，得:
  f(n) = 3 × (2n-2 + 2n-4 + ... + 22 + 1) + 3
=>
  f(n) = 3 × 1 × (1 - 4n/2) ÷ (1 - 4) + 3
=>
  f(n) = 2n + 2
又是如此得巧合，还得感叹大自然的美妙~
现在我们就得到了这道题目的公式了: f(n) = 2n + 2


Problem

问题分析

Problem Analyse
C语言基本语法

Algorithm Analyse
不知道你还记不记得2013题的解法？
本题用循环迭代能0MS 0K过。当然，也同样可以有更神奇的方法。^_^


Problem

2042 不容易系列之二

Problem Description
你活的不容易，我活的不容易，他活的也不容易。不过，如果你看了下面的故事，就会知道，有位老汉比你还不容易。

重庆市郊黄泥板村的徐老汉（大号徐东海，简称XDH）这两年辛辛苦苦养了不少羊，到了今年夏天，由于众所周知的高温干旱，实在没办法解决牲畜的饮水问题，就决定把这些羊都赶到集市去卖。从黄泥板村到交易地点要经过N个收费站，按说这收费站和徐老汉没什么关系，但是事实却令徐老汉欲哭无泪：

（镜头回放）

近景：老汉，一群羊
远景：公路，收费站

......

收费员（彬彬有礼+职业微笑）：“老同志，请交过路费！”

徐老汉（愕然，反应迟钝状）：“锅，锅，锅，锅-炉-费？我家不烧锅炉呀？”

收费员（职业微笑依然）：“老同志，我说的是过-路-费，就是你的羊要过这个路口必须交费，understand?”

徐老汉（近镜头10秒，嘴巴张开）：“我-我-我知道汽车过路要收费，这羊也要收费呀？”

收费员（居高临下+不解状）：“老同志，你怎么就不明白呢，那么我问你，汽车几个轮子？”

徐老汉（稍放松）：“这个我知道，今天在家里我孙子还问我这个问题，4个！”

收费员（生气，站起）：“嘿！老头，你还骂人不带脏字，既然知道汽车四个轮子，难道就不知道这羊有几条腿吗？！”

徐老汉（尴尬，依然不解状）：“也，也，也是4个呀，这有关系吗？”

收费员（生气，站起）：“怎么没关系！我们头说了，只要是4条腿的都要收费！”

......

(画外音)

由于徐老汉没钱，收费员就将他的羊拿走一半，看到老汉泪水涟涟，犹豫了一下，又还给老汉一只。巧合的是，后面每过一个收费站，都是拿走当时羊的一半，然后退还一只，等到老汉到达市场，就只剩下3只羊了。

你,当代有良知的青年，能帮忙算一下老汉最初有多少只羊吗？

Input
输入数据第一行是一个整数N，下面由N行组成，每行包含一个整数a(0<a<=30),表示收费站的数量。

Output
对于每个测试实例，请输出最初的羊的数量,每个测试实例的输出占一行。

Sample Input
2
1
2

Sample Output
4
6

Author
lcy

Source
2005实验班短学期考试

Recommend
lcy


Problem

编码建议

Programing
不要忽略了判断密码的长度哦。^_^


Problem

问题分析

Problem Analyse
基本编程语法

Algorithm Analyse
只要按照题目的意思做就可以了。没有想到什么特别精妙的算法。


Problem

2043 密码

Problem Description
网上流传一句话:"常在网上飘啊，哪能不挨刀啊～"。其实要想能安安心心地上网其实也不难，学点安全知识就可以。

首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件：

(1).密码长度大于等于8，且不要超过16。
(2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。

这四个字符类别分别为：
1.大写字母：A,B,C...Z;
2.小写字母：a,b,c...z;
3.数字：0,1,2...9;
4.特殊符号：~,!,@,#,$,%,^;

给你一个密码，你的任务就是判断它是不是一个安全的密码。

Input
输入数据第一行包含一个数M，接下有M行，每行一个密码（长度最大可能为50），密码仅包括上面的四类字符。

Output
对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。

Sample Input
3
a1b2c3d4
Linle@ACM
^~^@^@!%

Sample Output
NO
YES
NO

Author
linle

Source
2005实验班短学期考试

Recommend
lcy


Problem

编码建议

Programing
记得要用64位整数哦。


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
刚开始我看不懂这一题，因为我不清楚对于六边形的蜂房来说，哪一边算右边。
后来明白了，原来它所谓的右，是那张图的右边。
一只蜜蜂可以往下一格走，也可以往图的右边走。

比如:
蜜蜂在1格里，它可以往2、3两格里爬。
蜜蜂在6格里，它可以往7、8两格里爬。

所以在第n格里蜜蜂可以爬到第n+1, n+2格子里。
因此，这又是一个斐波那契数。


Problem

2044 一只小蜜蜂...

Problem Description
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

Input
输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。

Output
对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。

Sample Input
2
1 2
3 6

Sample Output
1
3

Author
lcy

Source
递推求解专题练习（For Beginner）

Recommend
lcy


Problem

编码建议

Programing
注意数据类型就可以了。


Problem

问题分析

Problem Analyse
递推问题

Algorithm Analyse
数组F[i]保存i个方格有多少种填涂方法。
n个方格可以由n-1个方格和n-2个方格填充得到。

比如，在一涂好的n-1个格子里最后再插入一个格子，就得到了n个格子了。
因为已经填好n-1的格子中，每两个格子的颜色都不相同。
所以只能插入一种颜色。而n-1个格子一共有F[n-1]种填涂方法。所以从n-1格扩充到n格共有F(n-1)种方法。

若前n-1不合法，而添加一个后变成合法，即前n-2个合法，而第n-1个与第1个相同。
这时候有两种填法。
所以
f[n] = f[n-1] + 2 * f[n-2];
f[1] = 3;
f[2] = 6;
f[3] = 6


Problem

2045 不容易系列之(3)——LELE的RPG难题

Problem Description
人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE的粉丝,即"可乐"）,经过多方打探，某资深Cole终于知道了原因，原来，LELE最近研究起了著名的RPG难题:

有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。

Output
对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input
1
2

Sample Output
3
6

Author
lcy

Source
递推求解专题练习（For Beginner）

Recommend
lcy


Problem

编码建议

Programing
用64位整型。


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
从图中也可以观察出来，第N张牌的排列可以又N-1张牌的排列再在末尾加上一张竖的牌。这样依然合法。
也可以在N-2张合法排列的牌后面加上两张横着放的牌(如果竖着放就和上面一种重复了)。
所以f(n) = f(n-1) + f(n-2)
即又是一个斐波那契数列。


Problem

2046 骨牌铺方格

Problem Description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如右图：

Input
输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

Output
对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

Sample Input
1
3
2

Sample Output
1
3
2

Author
lcy

Source
递推求解专题练习（For Beginner）

Recommend
lcy


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
这一题比起其他题稍微高级一点，它需要两路同时进行梯推。
我们每次都在原来合法的字符串的最后面再加一个字符，让它仍然是合法的字符串。
这就会出现最后一个字符是O和不是O两种情况，把末尾是O的字符串的个数保存在D[I][0]里，而不是O的保存在D[I][1]里。
在原来的字符串上再加个O，让它依然合法，则原来的字符串末尾必须不为O，即D[n][0] = D[n-1][1]
而在原来的字符串上再加非O，则它对前面字符串的末尾没有要求，而且它还有E、F两种。因此D[n][1] = 2 * (D[n-1][0] + D[n-1][1])
初始D[1][0] = 1; D[1][1] = 2;


Problem

2047 阿牛的EOF牛肉串

Problem Description
今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做EOF的队伍，由04级的阿牛、XC以及05级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了一想，阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由"E" "O" "F"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,阿牛同时禁止在串中出现O相邻的情况，他认为，"OO"看起来就像发怒的眼睛，效果不好。

你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？

PS: 阿牛还有一个小秘密，就是准备把这个刻有 EOF的牛肉干，作为神秘礼物献给杭电五十周年校庆，可以想象，当校长接过这块牛肉干的时候该有多高兴！这里，请允许我代表杭电的ACMer向阿牛表示感谢！

再次感谢！

Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0<n<40)。

Output
对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input
1
2

Sample Output
3
8

Author
lcy

Source
递推求解专题练习（For Beginner）

Recommend
lcy


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
神、上帝以及老天爷啊！就为了张Twins的签名照就这么大费周章的。唉~现在的年轻人啊。

N张票的所有排列可能自然是Ann = N!种排列方式
现在的问题就是N张票的错排方式有几种。
首先我们考虑，如果前面N-1个人拿的都不是自己的票，即前N-1个人满足错排，现在又来了一个人，他手里拿的是自己的票。
只要他把自己的票与其他N-1个人中的任意一个交换，就可以满足N个人的错排。这时有N-1种方法。

另外，我们考虑，如果前N-1个人不满足错排，而第N个人把自己的票与其中一个人交换后恰好满足错排。
这种情况发生在原先N-1人中，N-2个人满足错排，有且仅有一个人拿的是自己的票，而第N个人恰好与他做了交换，这时候就满足了错排。
因为前N-1个人中，每个人都有机会拿着自己的票。所以有N-1种交换的可能。

综上所述：f(n) = (i - 1) * [f(n - 1) + f(n - 2)]


Problem

2048 神、上帝以及老天爷

Problem Description
HDU 2006'10 ACM contest的颁奖晚会隆重开始了！
为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：

首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”

大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！

我的神、上帝以及老天爷呀，怎么会这样呢？

不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？

不会算？难道你也想以悲剧结尾？！

Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(1<n<=20),表示参加抽奖的人数。

Output
对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参照sample output。

Sample Input
1
2

Sample Output
50.00%

Author
lcy

Source
递推求解专题练习（For Beginner）

Recommend
lcy


Problem

编码建议

Programing
先求出组合数在乘以错排结果。不然做乘法运算可能会在中间过程中就造成数据溢出。
而且组合的规律告诉我们，这里做除法运算不会造成精度丢失情况。


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
依然是错排问题，方法见2048题。但这里还要从N个新郎中找出M个冤大头。HOHO~
方法就不用多讲了，就是求组合Cmn


Problem

2049 不容易系列之(4)——考新郎

Problem Description
国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:
首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.
最后,揭开盖头,如果找错了对象就要当众跪搓衣板...

看来做新郎也不是容易的事情...

假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。

Output
对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。

Sample Input
2
2 2
3 2

Sample Output
1
3

Author
lcy

Source
递推求解专题练习（For Beginner）

Recommend
lcy


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
我们不忙着解这道题。我们先来看一下N条相交的直线最多能把平面分割成几块。

很明显，当添加第n条直线时，为了使平面最多，则第n条直线要与前面n-1条直线都相交，切没有任何三条线交于一个点。
这样，第n条直线一共有n-1个交点。我们知道，增加n个焦点，则增加n+1个平面。
所以n条直线分割平面最大数是1 + 1 + 2 + 3 + ... + n = (n2 + n + 2) / 2

熟悉了线分割平面，现在，我们再来看看，每次增加的不是一条直线，而是两条相互平行的线，那又如何呢？

当第N次添加时，前面已经有2N-2条直线了，按我们上面讨论的知道，第N次添加时，第2N-1条直线和第2N条直线各能增加2(n-1)+1个平面。
所以第N次添加增加的面数是2[2(n-1) + 1] = 4n - 2 个。因此，总面数应该是1 + 4n(n+1)/2 - 2n = 2n2 + 1

现在我们再来看如果把每次加进来的平行边让它们一头相交，情况又如何呢？

我们看到，平面1、3已经合为一个面，既少了一个面。因此，每当一组平行线相交后，就会减少一个面。
因此，本题所要求的折线分割平面，自然就是上面求的的平行线分割平面数减去N。
即2n2 - n + 1


Problem

2050 折线分割平面

Problem Description
我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如右所示。

Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0<n<=10000),表示折线的数量。

Output
对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。

Sample Input
2
1
2

Sample Output
2
7

Author
lcy

Source
递推求解专题练习（For Beginner）

Recommend
lcy


Problem

问题分析

Problem Analyse
给你一个十进制的数，输出该数的二进制表示方式。

Algorithm Analyse
数制的转换知识参看2031。


Problem

2051 Bitset

Problem Description
Give you a number on base ten,you should output it on base two.(0 < n < 1000)

Input
For each case there is a postive number n on base ten, end of file.

Output
For each case output a number on base two.

Sample Input
1
2
3

Sample Output
1
10
11

Author
8600 && xhd

Source
校庆杯Warm Up

Recommend
linle


Problem

问题分析

Problem Analyse
给你一个矩形的宽和长，把它画出来。

简单的模拟题。

Algorithm Analyse
这题的简单之处在于周围的4个'+'不在范围之内。
所以像1 1这样的数据也不用另外考虑了。


Problem

2052 Picture

Problem Description
Give you the width and height of the rectangle,darw it.

Input
Input contains a number of test cases.For each case ,there are two numbers n and m (0 < n,m < 75)indicate the width and height of the rectangle.Iuput ends of EOF.

Output
For each case,you should draw a rectangle with the width and height giving in the input.
after each case, you should a blank line.

Sample Input
3 2

Sample Output
+---+
| |
| |
+---+

Author
xhd

Source
校庆杯Warm Up

Recommend
linle


Problem

问题分析

Problem Analyse
有一些灯排成一条直线。所有的灯在刚开始都是关闭的，在对灯进行一系列操作后:在第i次操作的时候，调整所有标号是i的倍数的灯的状态(原本打开的灯将它关闭，原本关闭的将它打开)。

Algorithm Analyse
我们举个简单的例子来看看它的规律:
比如n=16,则在第1、2、4、8、16次操作的时候，第16号灯都会被调整，因为16是1、2、4、8、16的倍数。
共有5次，因为开始是关闭的，所以最后将是亮着的。
你可能已经发现，其实求第n盏灯最后的状态，只是求它的因子个数的奇偶性(因为对同一盏等调整两次就恢复原状态)。
下面的代码就可以AC了。
#include <stdio.h>

int main(void)
{
    int i, c, n;
    while (scanf("%d", &n) != EOF)
    {
        for (i = 1, c= 0; i <= n; i++)
        {
            if (n % i == 0)
                c++;
        }
        printf("%d\n", c & 1);
    }

    return 0;
}
但你继续往下思考一下。是不是又发现了什么呢？
因子是不会只有1个的，比如16 = 1 * 16 = 2 * 8 = 4 * 4
所以，因为A = a × b，如果所有的因子a都不等于b，则因子的个数一定是偶数。
唯一使A的因子的个数为奇数的可能是存在A = a × b 且 a = b。即A是完全平方数。就像刚刚的16 = 4 × 4。
所以只要判断输入的数是否为完全平方数即可。


Problem

2053 Switch Game

Problem Description
There are many lamps in a line. All of them are off at first. A series of operations are carried out on these lamps. On the i-th operation, the lamps whose numbers are the multiple of i change the condition ( on to off and off to on ).

Input
Each test case contains only a number n ( 0< n<= 10^5) in a line.

Output
Output the condition of the n-th lamp after infinity operations ( 0 - off, 1 - on ).

Sample Input
1
5

Sample Output
1
0

Hint

Consider the second test case: The initial condition : 0 0 0 0 0 … After the first operation : 1 1 1 1 1 … After the second operation : 1 0 1 0 1 … After the third operation : 1 0 0 0 1 … After the fourth operation : 1 0 0 1 1 … After the fifth operation : 1 0 0 1 0 … The later operations cannot change the condition of the fifth lamp any more. So the answer is 0.

Author
LL

Source
校庆杯Warm Up

Recommend
linle


Problem

编码建议

Programing
比较前，先去掉前面多余的0，再去小数点后面多余的0(首先要保证有小数点)。
最后，如果小数点后面所有的数都去的掉了，还要同时去掉小数点。


Problem

问题分析

Problem Analyse
给你两个数A和B，如果A等于B就输出"YES"，否则输出"NO"。

字符处理

Algorithm Analyse
猜也能猜到，本题的数据不可能是简单到直接能保存进整型里。
它可能有10000位的长度，所以需要保存到字符串里。
比较的时候，需要注意的是：像0001.00与1是相同的。


Problem

2054 A == B ?

Problem Description
Give you two numbers A and B, if A is equal to B, you should print "YES", or print "NO".

Input
each test case contains two numbers A and B.

Output
for each case, if A is equal to B, you should print "YES", or print "NO".

Sample Input
1 2
2 2
3 3
4 3

Sample Output
NO
YES
YES
NO

Author
8600 && xhd

Source
校庆杯Warm Up

Recommend
linle


Problem

问题分析

Problem Analyse
我们定义f(A) = 1, f(a) = -1, f(B) = -2, ... f(Z) = -26;
给你一个字母x 以及一个数字y ，要求你输出 y + f(x)的值。

简单模拟。

Algorithm Analyse
直接按提议来。可以用哈希。也可以用数学公式。


Problem

2055 An easy problem

Problem Description
we define f(A) = 1, f(a) = -1, f(B) = 2, f(b) = -2, ... f(Z) = 26, f(z) = -26;
Give you a letter x and a number y , you should output the result of y+f(x).

Input
On the first line, contains a number T.then T lines follow, each line is a case.each case contains a letter and a number.

Output
for each case, you should the result of y+f(x) on a line.

Sample Input
6
R 1
P 2
G 3
r 1
p 2
g 3

Sample Output
19
18
10
-17
-14
-4

Author
8600

Source
校庆杯Warm Up

Recommend
linle


Problem

编码建议

Programing
如下图:给出的两点可能是A、C，也可能是B、D，所以我们自己要在开始时做个统一。


Problem

问题分析

Problem Analyse
给出两个矩形在对角线上的顶点的坐标，要求你计算两个矩形的公共部分的面积。

数学计算。

Algorithm Analyse
两个矩形摆放大致有下面几种(其他几种都可以由它们变形过来)。

其实，说的极端一点，两矩形摆放，也就两种摆法：相交与不相交。
这一题这样考虑反而更简单一点。
要求一个矩形的面积。如下图，我们先要知道边AD、BC的横坐标(X1, X2)，边AB、CD的纵坐标(Y1, Y2)。
然后按公式S = (X2 - X1) * (Y2 - Y1)
因此问题的关键是求这四个参数。

两个矩形相交的图形一定是矩形(这个容易证明，这里不阐述)。如下图，我们只要求出相交的矩形的那四个参数就可以了。

X1' = max(X1, X3)
Y1' = max(Y1, Y3)
X2' = min(X2, X4)
Y2' = min(Y2, Y4)

而当X1 > X2 且 Y1 > y2，则原来的两个矩形相离，所以面积为0；


Problem

2056 Rectangles

Problem Description
Given two rectangles and the coordinates of two points on the diagonals of each rectangle,you have to calculate the area of the intersected part of two rectangles. its sides are parallel to OX and OY .

Input
Input The first line of input is 8 positive numbers which indicate the coordinates of four points that must be on each diagonal.The 8 numbers are x1,y1,x2,y2,x3,y3,x4,y4.That means the two points on the first rectangle are(x1,y1),(x2,y2);the other two points on the second rectangle are (x3,y3),(x4,y4).

Output
Output For each case output the area of their intersected part in a single line.，　accurate up to 2 decimal places.

Sample Input
1.00 1.00 3.00 3.00 2.00 2.00 4.00 4.00
5.00 5.00 13.00 13.00 4.00 4.00 12.50 12.50

Sample Output
1.00
56.25

Author
seeyou

Source
校庆杯Warm Up

Recommend
linle


Problem

编码建议

Programing
判断是否为负数，可以直接判断是否<0，也可以求二进制最高位上是不是为1。
CODE：(a+b)&((__int64)1<<63)


Problem

问题分析

Problem Analyse
在HDOJ上已经有很多道A+B的题目了，现在有来了道新的。
给你两个16进制数，你的任务就是计算它们的和，然后以16进制输出。简单吗？把它AC掉！

C编程基础知识

Algorithm Analyse
本题的数据量不大，用64位整数不会溢出。
用%I64X就可以对数据读入输出进行操作。但问题在于直接用%I64X，是不能输出负数的，所以我们碰到负数要自己转成正数，在前面加‘-’。


Problem

2057 A + B Again

Problem Description
There must be many A + B problems in our HDOJ , now a new one is coming.
Give you two hexadecimal integers , your task is to calculate the sum of them,and print it in hexadecimal too.
Easy ? AC it !

Input
The input contains several test cases, please process to the end of the file.
Each case consists of two hexadecimal integers A and B in a line seperated by a blank.
The length of A and B is less than 15.

Output
For each test case,print the sum of A and B in hexadecimal in one line.

Sample Input
+A -A
+1A 12
1A -9
-1A -12
1A -AA

Sample Output
0
2C
11
-2C
-90

Author
linle

Source
校庆杯Warm Up

Recommend
linle


Problem

问题分析

Problem Analyse
给出一个数列1，2，3，......N，你所要做的就是算出和为M的所有连续的数列。

简单数学题。

Algorithm Analyse
我们都知道，在连续的整数序列里，1, 2, 3, ..., n-1, n, n+1, ...
∵2n = [(n-1) + (n+1)] = [(n-2) + (n+2)] = ... = [1 + (2n-1)]
∴(n-m) + (n-m+1) + ... + n-1 + n + n+1 + ... + (n+m-1) + (n+m) = (2m+1) × n
∵2m+1是奇数
∴如果X能被2m+1整除(即能被分割成2m+1份)，且n = X / (2m+1)
则X = (n-m) + (n-m+1) + ... + n-1 + n + n+1 + ... + (n+m-1) + (n+m)

同理，在整数序列中，又有这样的规律:
∵n + (n+1) = (n-1) + (n+2) = ... = 1 + 2n
∴(n-m) + (n-m+1) + ... + (n+m+1) = (m+1)(2n+1)
∴如果X能被(2n+1)整除，且X / (2m+2) = n
则X = (n-m) + (n-m+1) + ... + (n+m+1)

运算的时候，保证n-m大于0，n+m+1或n+m小于给定的上界即可。


Problem

2058 The sum problem

Problem Description
Given a sequence 1,2,3,......N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.

Input
Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.

Output
For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.

Sample Input
20 10
50 30
0 0

Sample Output
[1,4]
[10,10]

[4,8]
[6,9]
[9,11]
[30,30]

Author
8600

Source
校庆杯Warm Up

Recommend
linle


Problem

编码建议

Programing
其他站点充点都是要花时间的，惟独0站(起点)不需要，这要做好判断。


Problem

问题分析

Problem Analyse
一维数组的动态规划

Algorithm Analyse
与第2037题一样的算法。
我们把起点和终点，以及中间的n个充电站看做n+2个点。
这里长度为n+2的数组里保存的到达该站点所需时间的最优解。
自然，D[0](起点)的值就是0。
然后依次往下规划。
到了第i点后，就让j从0循环到i-1，依次代表从j站充满了电一直开到i站，这样得到到达i站所需要的最短时间。
最后比较到达第n+2站(终点)的时间与兔子所花的时间就可以了。


Problem

2059 龟兔赛跑

Problem Description
据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后，心中郁闷，发誓要报仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定的速度(VR m/s)一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。
最近正值HDU举办50周年校庆，社会各大名流齐聚下沙，兔子也趁此机会向乌龟发起挑战。虽然乌龟深知获胜希望不大，不过迫于舆论压力，只能接受挑战。
比赛是设在一条笔直的道路上，长度为L米，规则很简单，谁先到达终点谁就算获胜。
无奈乌龟自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有了不少积蓄。为了能够再赢兔子，乌龟不惜花下血本买了最先进的武器——“"小飞鸽"牌电动车。这辆车在有电的情况下能够以VT1 m/s的速度“飞驰”，可惜电池容量有限，每次充满电最多只能行驶C米的距离，以后就只能用脚来蹬了，乌龟用脚蹬时的速度为VT2 m/s。更过分的是，乌龟竟然在跑道上修建了很多很多（N个)的供电站，供自己给电动车充电。其中，每次充电需要花费T秒钟的时间。当然，乌龟经过一个充电站的时候可以选择去或不去充电。
比赛马上开始了，兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序，判断乌龟用最佳的方案进军时，能不能赢了一直以恒定速度奔跑的兔子。

Input
本题目包含多组测试，请处理到文件结束。每个测试包括四行：
第一行是一个整数L代表跑道的总长度
第二行包含三个整数N，C，T，分别表示充电站的个数，电动车冲满电以后能行驶的距离以及每次充电所需要的时间
第三行也是三个整数VR，VT1，VT2，分别表示兔子跑步的速度，乌龟开电动车的速度，乌龟脚蹬电动车的速度
第四行包含了N(N<=100)个整数p1,p2...pn,分别表示各个充电站离跑道起点的距离，其中0<p1<p2<... 其中每个数都在32位整型范围之内。

Output
当乌龟有可能赢的时候输出一行 “What a pity rabbit!"。否则输出一行"Good job,rabbit!";
题目数据保证不会出现乌龟和兔子同时到达的情况。

Sample Input
100
3 20 5
5 8 2
10 40 60
100
3 60 5
5 8 2
10 40 60

Sample Output
Good job,rabbit!
What a pity rabbit!

Author
linle

Source
校庆杯Warm Up

Recommend
linle


Problem

问题分析

Problem Analyse
背景:
当菲利普要放松一下自己的时候，他喜欢去玩QQ里的斯诺克游戏，虽然他还只是个小菜鸟。也许你还不知道这个游戏的规则，没关系，我会先为你介绍。 一共有21个球在台面上，其中包括15个红球和6个彩球:黄、绿、褐、蓝、粉、黑。选手需要用一个白球来使这些球滚进洞里，那些球所代表的值的和就是他的得分。 选手必须先把一个红球打进洞里，然后它得到红球相应的分值(1分)，然后他就有一次机会去选择打一个彩球。在红球还未全部打进洞里之前，打进去的彩球需要重新拿出来。 换句话说，也就是最后桌上将会只留下彩球。选手按下面的顺序来击球:黄(2分)、绿(3分)、褐(4分)、蓝(5分)、粉(6分)、黑(7分)。这时候把彩球打进洞里，它们不会被拿出来。 当桌面上没有球留下的时候，比赛结束。分数高的选手获胜。PS:红球不会重新拿出。我仅仅只阐述了一下规则，如果你希望了解更多的资料，请浏览:http://sports.tom.com/snooker/

例如，桌台上还有12个红球(如果还有红球留在台面上，表示所有的彩球一定也都留在台面上)。我假设菲利普能继续击球，他能得到的最大分数是： 12 * 1(一次性打掉12个红球) + 7 * 12(每打完一个红球就打黑球) + 2 + 3 + 4 + 5 + 6 + 7(没有红球剩下时，就打所有的彩球)。 现在，你的任务就是在菲利普告诉你现在台面上的情况(有多少个球还留在台面上)后判断一下他是否需要放弃这局比赛。如果他还有获胜的机会，就输出“Yes”，否则输出“No”。 (PS:如果他最大可能的得分加上现在的分数等于对手的分数，依然输出“Yes”)

简单数学计算

Algorithm Analyse
只要直接按题目的意思来就可以了。


Problem

2060 Snooker

Problem Description
background:
Philip likes to play the QQ game of Snooker when he wants a relax, though he was just a little vegetable-bird. Maybe you hadn't played that game yet, no matter, I'll introduce the rule for you first.
There are 21 object balls on board, including 15 red balls and 6 color balls: yellow, green, brown, blue, pink, black.
The player should use a white main ball to make the object balls roll into the hole, the sum of the ball's fixed value he made in the hole is the player's score. The player should firstly made a red ball into the hole, after that he gains red-ball's value(1 points), then he gets the chance to make a color ball, then alternately. The color ball should be took out until all the red-ball are in the hole. In other word, if there are only color balls left on board, the player should hit the object balls in this order: yellow(2 point), green(3 point), brown(4 point), blue(5 point), pink(6 point), black(7 point), after the ball being hit into the hole, they are not get out of the hole, after no ball left on board, the game ends, the player who has the higher score wins the game. PS: red object balls never get out of the hole.
I just illustrate the rules that maybe used, if you want to contact more details, visit http://sports.tom.com/snooker/ after the contest.

for example, if there are 12 red balls on board(if there are still red ball left on board, it can be sure that all the color balls must be on board either). So suppose Philp can continuesly hit the ball into the hole, he can get the maximun score is
12 * 1 (12 red-ball in one shoot) + 7 * 12(after hit a red ball, a black ball which was the most valuable ball should be the target) + 2 + 3 + 4 + 5 + 6 + 7(when no red ball left, make all the color ball in hole).
Now, your task is to judge whether Philip should make the decision to give up when telling you the condition on board(How many object balls still left not in the hole and the other player's score). If Philp still gets the chance to win, just print "Yes", otherwise print "No". (PS: if the max score he could get on board add his current score is equal to the opponent's current score, still output "Yes")

Input
The first line contains a numble N indicating the total conditions. Then followed by N lines, each line is made of three integers:
Ball_Left P_Score O_Score represeting the ball number left on board, Philp's current score, and the opponent's current score.
All the input value are in 32 bit integer value range.

Output
You should caculate the max score left Philp can gain, and judge whether he has the possiblity to win.

Sample Input
2
12 1 1
1 30 39

Sample Output
Yes
No

Author
zl

Source
校庆杯Warm Up

Recommend
linle


Problem

问题分析

Problem Analyse
背景:
新的学期即将到来，也正逢杭州电子科技大学50周年校庆。无论你的专业是什么，我唯一要告诉那么的是：“珍惜大学的生活，利用好时间。” 很多人认为大学的生活回是丰富多采。但事实是，大学生活也同样忙碌。如果你要掌握书上的知识，你的空闲时间必须花在自学和实践上， 尤其是实践。我认为，作为一位大学生，所有人都必须端正自己的学习态度。
“没有不劳而获的事情”，杭电也设立了奖学金，你能得到吗？它主要依据是学生获得的GPA(测评平均分)。 现在，我将告诉你它的规则，你的任务就是编程计算GPA。
假如有K门课程，第i门课的学分为Ci，你的成绩为为Si，则GPA为：
GPA = (C1 * S1 + C2 * S2 +……+Ci * Si……) / (C1 + C2 + ……+ Ci……) (1 <= i <= K, Ci != 0)
如果有一门课程成绩在0到60之间，则GPA将不存在。

简单数值计算

Algorithm Analyse
直接按题意来


Problem

2061 Treasure the new start, freshmen!

Problem Description
background:
A new semester comes , and the HDU also meets its 50th birthday. No matter what's your major, the only thing I want to tell you is:"Treasure the college life and seize the time." Most people thought that the college life should be colorful, less presure.But in actual, the college life is also busy and rough. If you want to master the knowledge learned from the book, a great deal of leisure time should be spend on individual study and practise, especially on the latter one. I think the every one of you should take the learning attitude just as you have in senior school.
"No pain, No Gain", HDU also has scholarship, who can win it? That's mainly rely on the GPA(grade-point average) of the student had got. Now, I gonna tell you the rule, and your task is to program to caculate the GPA.
If there are K(K > 0) courses, the i-th course has the credit Ci, your score Si, then the result GPA is
GPA = (C1 * S1 + C2 * S2 +……+Ci * Si……) / (C1 + C2 + ……+ Ci……) (1 <= i <= K, Ci != 0)
If there is a 0 <= Si < 60, The GPA is always not existed.

Input
The first number N indicate that there are N test cases(N <= 50). In each case, there is a number K (the total courses number), then K lines followed, each line would obey the format: Course-Name (Length <= 30) , Credits(<= 10), Score(<= 100).
Notice: There is no blank in the Course Name. All the Inputs are legal

Output
Output the GPA of each case as discribed above, if the GPA is not existed, ouput:"Sorry!", else just output the GPA value which is rounded to the 2 digits after the decimal point. There is a blank line between two test cases.

Sample Input
2
3
Algorithm 3 97
DataStruct 3 90
softwareProject 4 85
2
Database 4 59
English 4 81

Sample Output
90.10

Sorry!

Author
zl

Source
校庆杯Warm Up

Recommend
linle


Problem

编码建议

Programing
在调整数组的时候，只要做一趟插入排序就可以了。效率不错。
Rank	Author 		Exe. Time 	Exe. Memory 	Code Len. 	Language 		Date
1	redraiment 	31MS 		0K 		564B 		C 		2007-07-28 17:14:03


Problem

问题分析

Problem Analyse
考虑一个集合 An = { 1, 2, ..., n}。比如，A1={1}，A3={1,2,3}。我们称一个非空子集元素的排列为一个子集序列。 对所有的子序列按字典顺序排序。你的任务就是给出第m个子序列。

Algorithm Analyse
首先我们来看看An一共有多少个子集。
n=1时,只有{1}一个子集合

n=2时，就有:
{1}, {2},
{1, 2}, {2, 1}
4个子集合。

n=3时，有
{1}, {2}, {3},
{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2},
{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}

也许你发现规律了。An子集合的个数为:
C1n·A11 + C2n·A22 + ... + Cnn·Ann
这个公式是对的。但我们换个角度看。
n=3时，有
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{1, 3, 2}

{2}
{2, 1}
{2, 1, 3}
{2, 3}
{2, 3, 1}

{3}
{3, 1}
{3, 1, 2}
{3, 2}
{3, 2, 1}

不难发现，An可以按首数字分成n组，而每组里除了第一项，剩下的就是An-1的子集合了。
∴f(n) = n[f(n-1) + 1]
f(1) = 1

我们拿测试数据3 10来做个示范，解释一下怎么求解。
因为n=3，所以开始数组里1、2、3三个数。
我们知道，n=2时，有4种排列，所以上面n=3可以分成三组，每组5个(加上空集)。
因此第10个在第二组里。所以第一个是2，把2输出。原来的数组里删除2，变成1、3两个数。 然后10 - (2 - 1) * 5 = 5，即它在第2组的第5个。
减去首个空集合，5 - 1 = 4 ≠ 0，表示2后面还有数字。
因为A1 = 1是，所以再第2组里又可以分成两组，每组2个(加上空集)。
所以，4在第2组，剩下的数组中，第二个元素是3，所以输出3。再把数组里的3删除，剩下1一个数。
然后4 - (2 - 1) * 2 = 2，既它是第2组的第2个。
减去首个空集，2 - 1 = 1 ≠ 0，表示2后面还有数字。
按上面的方法继续下去，直到n = 0 或 后面为空集为止。
最后输出数组里的第1个元素，就得到2 3 1，就是解了。

从上面的计算可以看出来，本题目的关键是先求的An中每一组的个数g(n)
不难得出:g(n) = f(n) / n
∵f(n) = n[f(n-1) + 1]
∴g(n) = n[f(n-1) + 1] / n = f(n-1) + 1
∵f(n-1) = (n-1) * g(n-1)
∴g(n) = (n-1) * g(n-1) + 1


Problem

2062 Subset sequence

Problem Description
Consider the aggregate An= { 1, 2, …, n }. For example, A1={1}, A3={1,2,3}. A subset sequence is defined as a array of a non-empty subset. Sort all the subset sequece of An in lexicography order. Your task is to find the m-th one.

Input
The input contains several test cases. Each test case consists of two numbers n and m ( 0< n<= 20, 0< m<= the total number of the subset sequence of An ).

Output
For each test case, you should output the m-th subset sequence of An in one line.

Sample Input
1 1
2 1
2 2
2 3
2 4
3 10

Sample Output
1
1
1 2
2
2 1
2 3 1

Author
LL

Source
校庆杯Warm Up

Recommend
linle


Problem

编码建议

Programing
知道了前面的算法，编码倒是挺快的。

数据结构:
保存二分图用的是邻接表。
为方便存储和阅读，数组下标从1开始(0那个空间就空着不用)。
因此，第i个表头邻接的是第i个女生愿意与他做partner的男生号。

集合X、Y用一维数组表示。下标同样从1开始。
如果它们暂时没有点配对，则里面保存的是O，否则保存配对的点的下标。
初始状态X、Y都为0。

因为X是从1到n循环，所以只需要判断Y集合中的点是否被访问过。
判断是否被访问过用一个Bool型一维数组，true表示被访问过，false表示未被访问过。

中间记录增广路径用栈结构。因为增广路径的边数是奇数，根据握手定理，它的顶点数一定是偶数。
找到增广路径以后，每次从栈顶取出2个端点，就是现在相互配对的端点了。一直到栈取空为止。

算法实现:
实现匈牙利算法分为4个步骤:

  1. 初始化:
    集合X、Y清空
    图清空

  2. 输入:
    输入集合X、Y的大小size_x和size_y，以及所有的边

  3. 计算:
    i从1循环到size_x，深搜寻找Xi的增广路径
    每次寻找前要先清空栈，并且初始Visit数组为false
    在深搜的过程中，要注意，如果寻找增广路径失败，要记得把刚加入的那一个顶点从栈中删除
    如果增广路径查找成功，就开始读栈，对X、Y里相互配对的端点进行标记，直到栈为空

  4. 输出:
    统计X(Y)集合中有配对的端点个数，即最大匹配数。
    输出最大匹配数


Problem

问题分析

Problem Analyse
求二分图最大匹配

需要离散数学图论的知识。

Algorithm Analyse
做这一题的时候，也费了我大力气。以前都没涉及过二分图的算法，对这方面的知识可以说是零； 另一面网上的资料都很零散。没有比较系统比较完整地介绍一下的。我也是在百度里搜索了很多资料， 才了解并熟悉这个算法，最后能一次性通过，并且排名排在第一位，我真的是太兴奋了！ 为了方便后来者，也方便我自己以后查阅(与人方便，与己方便嘛)，我把搜集的资料整理一下，加上一点自己的心得， 把它们写下来。

二分图的基本概念
一个无向图G=<V, E>，如果存在两个集合X、Y，使得X∪Y=V， X∩Y=Φ，并且每一条边e={x，y}有x∈X，y∈Y， 则称G为一个二分图(bipartite graph)。常用<X, E, Y>来表示一个二分图。 若对X中任一x及Y中任一y恰有一边e∈E，使e = {x, y}, 则称G为完全二分图(complete bipartite graph)。 当|X| = m，|Y| = n时，完全二分图G记为Km,n。

二分图的性质：
定理：无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。
匹配：设G=<V, E>为二分图，如果M⊆E，并且M中没有任何两边有公共端点。M=Φ时称M为空匹配。
最大匹配:G的所有匹配中边数最多的匹配称为最大匹配。
完全匹配:若X(Y)中所有的顶点都是匹配M中的端点。则成M为完全匹配。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。
注意:最大匹配总是存在但未必唯一；X(Y)-完全匹配及G的完全匹配必定是最大的，但反之则不然；X(Y)-完全匹配未必存在。

下面引入几个术语：
设G=<V, E>为二分图，M为G的一个匹配。

  1. M中边的端点称为M-顶点，其它顶点称为非M-顶点。
  2. 增广路径:除了起点和终点两个顶点为非M-顶点，其他路径上所有的点都是M=顶点。而且它的边为匹配边、非匹配边交替出现。

    图1 [image] 图2

    如上图中图1，就是一个二分图的匹配:[X1, Y2]。图2就是在这个匹配的基础上的两个增广路径:X2→Y2→X1→Y1和X3→Y3。
    我们来验证一下:增广路径 X2→Y2→X1→Y1中，起止点X2、Y1为非M-顶点。而中间点Y2、X1都是M-顶点。
    边{X2, Y2}, {X1, Y1}为非匹配边，而边{Y2, X1}为匹配边，满足匹配边与非匹配边交替出现。
    同理X3→Y3路径也满足增广路径的要求。

    借助这幅图，来描述一下增广路径的性质。

    1. 有奇数条边。
    2. 起点在二分图的左半边，终点在右半边。
    3. 路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。）
    4. 整条路径上没有重复的点。
    5. 起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。
    6. 路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。
    7. 最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。
    ∵增广路径的长度是奇数，我们设为2k+1条
    又∵第一条是非匹配边 且 匹配边与非匹配边交替出现
    ∴非匹配边有K+1条，匹配边有K条。
    非匹配边比匹配边多了1条。
    此时，我们做取反操作(匹配边变成非匹配边，非匹配边变成匹配边)，则匹配边的个数就会在原来的基础上增加1条。
    求最大匹配的“匈牙利算法”就是这样做的。
    无论从哪个匹配开始(整个程序的初始状态是从空匹配开始)，每次操作都让匹配数增加1条，不断使它得到扩充，直到找不到增广路径。
    这样就得到了最大匹配了。

    对增广路径，还有一种递归的定义，可能不大准确，但揭示了一种寻找增广路径的一般方法:
    从集合X中的一个非M-顶点A出发，通过与A关联的边到达集合Y中的端点B， 如果B在M中没有任何边匹配，则B就是该增广路径的终点； 如果B已经与C点配对，则这条增广路径就是从A→B→C并加上“从C点出发的增广路径”。 并且这条增广路径中不能有重复的点出现。

    比如我们要从上图中找出一条从X3点出发的增广路径，我们需要做以下几步。

    1. 首先从X3出发，它能连接到的点只有点Y3，而Y3已经与X2配对，所以现在的增广路径是X3→Y3→X2在加上从点X2出发的增广路径。
    2. 点X2能连接到Y2，Y3，但Y3与前面的路径重复，而{X2, Y2}这条边也不在原来的匹配中，所以只能连接到Y2。所以现在的增广路径是X3→Y3→X2→Y2→X1在加上从点X1出发的增广路径。
    3. 点X1能连接到的点且不前面路径重复的点只有Y1。并且Y1在原先的匹配中不与其他所有点配对，属于非M-顶点。因此Y1是该增广路径的终点。所以最终的增广路径是X3→Y3→X2→Y2→X1→Y1。

    严格意义上讲，上面提到的从X2出发的增广路径X2→Y2→X1→Y1和从点X1出发的增广路径X1→Y1并不是真正意义上的增广路径，它们不符合第5个性质。它们的起点是已配对的点。 这里说它们是增广路径只是为了简化搜索过程，它们都只是中间返回值而已。

现在就进入我们的正题:用匈牙利算法求最大匹配。
匈牙利算法的基本模式是:

初始时最大匹配为空 while 找得到增广路径 do 把增广路径加入到最大匹配中去
比如我们寻找图1的最大匹配，过程可能如下:
  1. 初始最大匹配为空。
  2. 找到增广路径X1→Y2，把它取反，则匹配数增大到1，最大匹配变成[X1, Y2]。
  3. 找到增广路径X2→Y3，把它取反，则匹配数增大到2，最大匹配变成[X1, Y2]，[X2, Y3]。
  4. 找到增广路径X3→Y3→X2→Y2→X1→Y1，把它取反，则匹配数增大到3，最大匹配变成[X1, Y1]，[X2, Y2]，[X3, Y3]。
  5. 找不出增广路径，程序结束，得到最大匹配数为3。
这只是其中一种可能的过程，还有其他不同的过程，得到的增广路径也可能不同，但最后最大匹配数一定是相同的。

从上面的描述可以看出，搜索增广路径的方法是DFS，写一个递归的函数。当然也可以用BFS。

至此，理论基础部份讲完了。但是要完成匈牙利算法，还需要一个重要的定理：
如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。

有了这个定理，匈牙利算法就成形了。如下:

初始时最大匹配为空 for 二分图左半边的每个点i do 从点i出发寻找增广路径。如果找到，则把它取反(即增加了总了匹配数)。
如果二分图的左半边一共有n个点，那么最多找n条增广路径。 如果图中共有m条边，那么每找一条增广路径(DFS或BFS)时最多把所有边遍历一遍，所花时间也就是m。 所以总的时间大概就是O(n * m)。


Problem

2063 过山车

Problem Description
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？

Input
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。

Sample Input
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

Sample Output
3

Author
PrincessSnow

Source
RPG专场练习赛

Recommend
lcy


Problem

编码建议

Programing
得到递公式了，你可以开始解题了。但这一题还是有优化方法。

f(n) = 3 × f(n-1) + 2
f(1) = 2

=>

f(n) + 1 = 3 × [f(n-1) + 1]
f(1) + 1 = 2 + 1 = 3
=>
f(n) + 1 = 3n
=>
f(n) = 3n - 1


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
汉诺塔是我很喜欢玩的一个游戏。
如果规则没这么变态，允许直接从1跨越到3，那n个盘最少需要2n - 1次。
这个公式可以递推得到，很容易的，你可以试一下，这里就不阐述了。

而这一题同样可以用递推得到。我们先来看看下面一组图，了解一下如何把n个盘从1搬到3。

第1步:初始状态
第2步:把上面的n-1个盘移到第3号杆上
第3步:把第n个盘从1移到2
第4步:把前n-1个从3移到1，给第个盘让路
第5步:把第n个盘从2移到3
第6步:把前n-1个从移到3，完成移动

我们设f(n)为把n个盘从1移到3所需要的步数，当然也等于从3移到1的步数。
看什么的图就知道，要想把第n个盘从1移到3，需要想把前n-1个从1移动3，再从3->1最后再1->3。
而第n个盘要从1->2->3经历2步。
∴f(n) = 3 × f(n-1) + 2;
f(1) = 2;


Problem

2064 汉诺塔III

Problem Description
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？

Input
包含多组数据，每次输入一个N值(1<=N<=35)。

Output
对于每组数据，输出移动最小的次数。

Sample Input
1
3
12

Sample Output
2
26
531440

Author
Rabbit

Source
RPG专场练习赛

Recommend
lcy


Problem

编码建议

Programing
公式得到了:f(n) = 22n-2 + 2n-1
但就这样直接编程那是不可能实现的，因为n的范围1≤N<264
怎么的范围，是不能求出f(n)的。所以还得找其他规律。

因为题目只要求输出最后2位数，我们依次输出2的n的最后两位看看...
20 -> 1
21 -> 2
22 -> 4
23 -> 8
24 -> 16
25 -> 32
26 -> 64
27 -> 28
28 -> 56
29 -> 12
210 -> 24
211 -> 48
212 -> 96
213 -> 92
214 -> 84
215 -> 68
216 -> 36
217 -> 72
218 -> 44
219 -> 88
220 -> 76
221 -> 52
222 -> 4
到了222时，末尾2位又变成4，与22一样，这时候就进入了一个循环了(每20个一次循环)。
所以，结果只能是这22个中的一个。只有n=0 和 n=1是需要特殊考虑的。其他n就等于2(n-2) % 20 + 2的值了。


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
比起以前做过的递推题，这一题算比较麻烦的了(当然，原因是我没有想到好的方法，如果你有更方便的方法，欢迎提供大家一起学习)。

如果没有任何条件限制，A、B、C、D组成长度为n的字符串，其个数应该为:4n。

因为有了A、C需要出现偶数次的要求，就出现合法和不合法的不同分组。
在不合法的组里，又有
1.A出现奇数次、C出现偶数次；
2.C出现奇数次、A出现偶数次；
3.A出现奇数次、C出现奇数次；
三种情况。

我们用数组
f[n][0]保存长度为n，合法的字符串的个数。
f[n][1]保存长度为n，仅A出现奇数次的字符串的个数。
f[n][2]保存长度为n，仅C出现奇数次的字符串的个数。
f[n][3]保存长度为n，A、C出现奇数次的字符串的个数。

f[n][0]
长度为n-1的合法字符串在末尾加上一个B或者D，都可以变成长度为n的合法字符串。
长度为n-1的仅A出现奇数次的字符串再在末尾加上一个A，也可以变成合法字符串。
长度为n-1的仅C出现奇数次的字符串再在末尾加上一个C，也可以变成合法字符串。
所以，f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2];

f[n][1]
长度为n-1的合法字符串在末尾加上A，都可以变成长度为n的仅A出现奇数次的字符串。
长度为n-1的仅A出现奇数次的字符串再在末尾加上一个B或者D，也可以变成仅A出现奇数次的字符串。
长度为n-1的A、C出现奇数次的字符串再在末尾加上一个C，也可以变成仅A出现奇数次的字符串。
所以，f[n][1] = 2 × f[n-1][1] + f[n-1][0] + f[n-1][3];

f[n][2]
长度为n-1的合法字符串在末尾加上C，都可以变成长度为n的仅C出现奇数次的字符串。
长度为n-1的仅C出现奇数次的字符串再在末尾加上一个B或者D，也可以变成仅C出现奇数次的字符串。
长度为n-1的A、C出现奇数次的字符串再在末尾加上一个A，也可以变成仅C出现奇数次的字符串。
所以，f[n][2] = 2 × f[n-1][2] + f[n-1][0] + f[n-1][3];

f[n][3]
长度为n-1的A、C出现奇数次的字符串在末尾加上一B或者D，都可以变成长度为n的A、C出现奇数次的字符串。
长度为n-1的仅A出现奇数次的字符串再在末尾加上一个C，也可以变成A、C出现奇数次的字符串。
长度为n-1的仅C出现奇数次的字符串再在末尾加上一个A，也可以变成A、C出现奇数次的字符串。
所以，f[n][3] = 2 × f[n-1][3] + f[n-1][1] + f[n-1][2];

综上所述，我们得到:
f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2]; ①
f[n][1] = 2 × f[n-1][1] + f[n-1][0] + f[n-1][3]; ②
f[n][2] = 2 × f[n-1][2] + f[n-1][0] + f[n-1][3]; ③
f[n][3] = 2 × f[n-1][3] + f[n-1][1] + f[n-1][2]; ④

f[1][0] = 2
f[1][1] = 1
f[1][2] = 1
f[1][3] = 0

发现f[1][1]与f[1][2]初始状态相同，而且以后迭代方程也相同，所以f[n][1] = f[n][2]
又有f[n][0] + f[n][3] = f[n][1] + f[n][2]
∵f[n][0] + f[n][1] + f[n][2] + f[n][3] = 4n
∴f[n][0] + f[n][3] = f[n][1] + f[n][2] = 2 × 4n-1
∴f[n-1][1] + f[n-1][2] = 2 × 4n-2
∴f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2] = 2 × f[n-1][0] + 2 × 4n-2

我们得到:
f[n][0] = 2 × f[n-1][0] + 22n-3
f[n-1][0] = 2 × f[n-2][0] + 22n-5
┋
f[n-m][0] = 2 × f[n-m-1][0] + 22n-2m-3
┋
f[2][0] = 2 × f[1][0] + 21
f[1][0] = 2

开始一层层往下迭代:
f[n][0]
= 2 × f[n-1][0] + 22n-3
= 22 × f[n-2][0] + 22n-4 + 22n-3
┋
= 2m × f[n-m][0] + 22(n-m)-1+m-1 + ... + 22n-3
= 2n-1 × f[1][0] + 2n-1 + 2n +... + 22n-3
f[1][0] = 2;

∴f[n][0] = 2n + 2n-1 + 2n +... + 22n-3 = 22n-2 + 2n-1


Problem

2065 "红色病毒"问题

Problem Description
医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.

Input
每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束.

Output
对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.

Sample Input
4
1
4
20
11
3
14
24
6
0

Sample Output
Case 1: 2
Case 2: 72
Case 3: 32
Case 4: 0

Case 1: 56
Case 2: 72
Case 3: 56

Author
Rabbit

Source
RPG专场练习赛

Recommend
lcy


Problem

编码建议

Programing
最小优先级队列可以用STL里的make_heap()来。
下面是C++版的Dijkstra算法。
struct node
{
    int ord;
    int cost;
}v[1001];
for (i = len; i; i--)
{
    make_heap(v + 1, v + 1 + i);
    for (j = 2; j <= i; j++)
    {
        if (v[j].cost > v[1].cost + mp[v[1].ord][v[j].ord])
            v[j].cost = v[1].cost + mp[v[1].ord][v[j].ord];
    }
    swap(v[1], v[i]);
}
sort(v + 1, v + 1 + len, cmp);
但发现用STL，速度会比较慢，大概需要90几MS。我的参考代码里用的是数组。没用STL。


Problem

问题分析

Problem Analyse
单源最短路径

Algorithm Analyse
求单源最短路径的算法是Dijkstra算法。
它解决了有向图G=(V, E)上带权的单源最短路径问题。但要求所有边的权值非负。

Dijkstra算法中设置了一顶点集合S，从源点s到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短路径估计的顶点u∈V-S，并将u加入到S中，对u的所有出边进行松弛。在下面的 算法实现中，用到了顶点的最小优先级列队Q，排序关键字为顶点的d值。
下面是Dijkstra的伪码:

DIJKSTRA(G, w, s) 1 INITIALIZE-SINGLE-SOURCE(G, s) 2 S←Φ 3 Q←V[G] 4 while Q ≠ Φ 5 do u ← EXTRACT-MIN(Q) 6 S ← S∪{u} 7 for each vertex v ∈ Adj[u] 8 do RELAX(u, v, w)
下面用来演示一下它的执行过程。正确性这里就不证明了。

a | b | c
d | e | f
Dijkstra算法的执行过程。源点s为最坐端顶点。最短路径估计被标记在顶点内，阴影覆盖的边指出了前趋的值。 蓝色顶点在集合S中，而白色顶点在最小优先级队列Q=V-S中。 a)第4～8行while循环第一次迭代前的情形。阴影覆盖的顶点具有最小的d值，而且在第5行被选为顶点u。 b)至f)while循环在每一次连续迭代后的情形。每个图中阴影覆盖的顶点被选作下一次迭代第5行的顶点u。 f)图中的值为最终结果。

因为Dijkstra算法总是在V-S中选择“最轻”或“最近”的顶点插入集合S中，所有我们说它使用了贪心策略。


Problem

2066 一个人的旅行

Problem Description
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。

Output
输出草儿能去某个喜欢的城市的最短时间。

Sample Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

Sample Output
9

Author
Grass

Source
RPG专场练习赛

Recommend
lcy


Problem

编码建议

Programing
规律我们是找到了，但不用急着编程。
虽然它是用一个矩阵描述的，但我们大可不必开一个二维数组。我们只要开一个一维数组就可以了。
因为f(i, j) = f(i, j - 1) + f(i - 1, j);
而我们做完第i-1趟处理后，保存的是第i-1行上的数据。相当于已经有了f(i - 1, j)
所有只要在原来的基础，就是加上它左边的数就可以了。


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
我们假设小兔的棋盘是8×8的(当然你也可以假设是其他)。如下图:
箭头方向表示从该格子下一步能去的格子。因为不能穿越对角线，所有对角线上的格子只有进去的箭头，没有出来的箭头。

观察上图你就可以发现，其实这是一张关于对角线对称的图。所有我们只要求一个方向的值，然后乘以2即可。
我们就拿下三角来考虑。不难发现，所有在0列上的格子，路径数都是1(只能从上面过来)。
而其他格子则都是由上、左两个方向过来，即:f(i, j) = f(i - 1, j) + f(i, j - 1);
另外f(i, i) = f(i, j - 1);


Problem

2067 小兔的棋盘

Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!

Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。

Output
对于每个输入数据输出路径数，具体格式看Sample。

Sample Input
1
3
12
-1

Sample Output
1 1 2
2 3 10
3 12 416024

Author
Rabbit

Source
RPG专场练习赛

Recommend
lcy


Problem

编码建议

Programing
数据范围比较大，需要用double型数据。


Problem

问题分析

Problem Analyse
错排+排列组合

Algorithm Analyse
和2048、2049题一样，都属于错排题。
错排公式:f(n) = (i - 1) * [f(n-1) + f(n-2)]。
具体的推导请查看2048。
当然，本题目还涉及到组合，排错的i个人要从n个人中选出，并且要累加i从 0 -> n/2的所有错排个数。


Problem

2068 RPG的错排

Problem Description
今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜，第一次猜：R是公主，P是草儿，G是月野兔；第二次猜：R是草儿，P是月野兔，G是公主；第三次猜：R是草儿，P是公主，G是月野兔；......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动，做ACM的女生越来越多，我们的野骆驼想都知道她们，可现在有N多人，他要猜的次数可就多了，为了不为难野骆驼，女生们只要求他答对一半或以上就算过关，请问有多少组答案能使他顺利过关。

Input
输入的数据里有多个case,每个case包括一个n，代表有几个女生，（n<=25）, n = 0输入结束。

Output
给出有多少组答案能使他顺利过关。

Sample Input
1
2
0

Sample Output
1
1

Author
Rabbit

Source
RPG专场练习赛

Recommend
lcy


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
这道题目初学者可能比高手做得更快。
开始我还思考老半天，后来我想随便输出几个结果看看，发现速度很快。最后直接暴力通过，而且还是OMS OK。
最意外的，还是选择排名还在第一位，对此我只能无语...


Problem

2069 Coin Change

Problem Description
Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 cents.

Input
The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.

Output
For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

Sample Input
11
26

Sample Output
4
13

Author
Lily

Source
浙江工业大学网络选拔赛

Recommend
linle


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
公式都有了，还等什么？直接AC掉它！


Problem

2070 Fibbonacci Number

Problem Description
Your objective for this question is to develop a program which will generate a fibbonacci number. The fibbonacci function is defined as such:

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

Your program should be able to handle values of n in the range 0 to 50.

Input
Each test case consists of one integer n in a single line where 0≤n≤50. The input is terminated by -1.

Output
Print out the answer in a single line for each test case.

Sample Input
3
4
5
-1

Sample Output
2
3
5

Author
Lily

Source
浙江工业大学网络选拔赛

Recommend
linle


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
求一个数列的最大值，这我们还有什么好说的？
排第一的代码是用PASCAL写的，不晓得它怎么刷到28MS的。呵呵。


Problem

2071 Max Num

Problem Description
There are some students in a class, Can you help teacher find the highest student .

Input
There are some cases. The first line contains an integer t, indicate the cases; Each case have an integer n ( 1 ≤ n ≤ 100 ) , followed n students’ height.

Output
For each case output the highest height, the height to two decimal plases;

Sample Input
2
3 170.00 165.00 180.00
4 165.00 182.00 172.00 160.00

Sample Output
180.00
182.00

Author
Lily

Source
浙江工业大学网络选拔赛

Recommend
linle


Problem

编码建议

Programing
集合当然是用C++里的STL库咯！轻松过关。呵呵。


Problem

问题分析

Problem Analyse
字符串处理

Algorithm Analyse
这就是一个集合的问题。求单词那个集合里有几个元素。


Problem

2072 单词数

Problem Description
lily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。

Input
有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到#时表示输入结束。

Output
每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。

Sample Input
you are my friend
#

Sample Output
4

Author
Lily

Source
浙江工业大学网络选拔赛

Recommend
linle


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
直接来，一条一条的加上去。只要算对的，基本上都是0MS OK AC的。


Problem

2073 无限的路

Problem Description
甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画直线，于是他就在平面直角坐标系中画出如右的图形：

甜甜的好朋友蜜蜜发现上面的图还是有点规则的，于是他问甜甜：在你画的图中，我给你两个点，请你算一算连接两点的折线长度（即沿折线走的路线长度）吧。

Input
第一个数是正整数N（≤100）。代表数据的组数。
每组数据由四个非负整数组成x1，y1，x2，y2；所有的数都不会大于100。

Output
对于每组数据，输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后3位。

Sample Input
5
0 0 0 1
0 0 1 0
2 3 3 1
99 99 9 9
5 5 5 5

Sample Output
1.000
2.414
10.646
54985.047
0.000

Author
Lily

Source
浙江工业大学网络选拔赛

Recommend
linle


Problem

编码建议

Programing
最后的空格还是要求输出的，题目比较BT。


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
仔细观察一下那张图，你会发现，第i层框的长宽都是从i->n-i，只要对这个范围内的数组进行填充就可以了。


Problem

2074 叠筐

Problem Description
需要的时候，就把一个个大小差一圈的筐叠上去，使得从上往下看时，边筐花色交错。这个工作现在要让计算机来完成，得看你的了。

Input
输入是一个个的三元组，分别是，外筐尺寸n（n为满足0<n<80的奇整数），中心花色字符，外筐花色字符，后二者都为ASCII可见字符；

Output
输出叠在一起的筐图案，中心花色与外筐花色字符从内层起交错相叠，多筐相叠时，最外筐的角总是被打磨掉。叠筐与叠筐之间应有一行间隔。

Sample Input
11 B A
5 @ W

Sample Output
AAAAAAAAA
ABBBBBBBBBA
ABAAAAAAABA
ABABBBBBABA
ABABAAABABA
ABABABABABA
ABABAAABABA
ABABBBBBABA
ABAAAAAAABA
ABBBBBBBBBA
AAAAAAAAA

@@@
@WWW@
@W@W@
@WWW@
@@@

Author
qianneng

Source
浙江工业大学网络选拔赛

Recommend
linle


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
差不多是考你基本输入输出了。我也不明白他们为什么研究这个问题。


Problem

2075 A|B?

Problem Description
正整数A是否能被正整数B整除，不知道为什么xhd会研究这个问题，来帮帮他吧。

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有两个正整数A和B(A,B<10^9)。

Output
对于每组输入数据，输出"YES"表示可以被整除，"NO"表示不能被整除。

Sample Input
2
4 2
5 3

Sample Output
YES
NO

Author
xhd

Source
ACM程序设计期末考试_热身赛(感谢 xhd & 8600)

Recommend
lcy


Problem

问题分析

Problem Analyse
数学题

Algorithm Analyse
我们知道，时针走30°/小时，分针走6°/分钟。
所有
时针走:30°/h = 0.5°/m = (1/120)°/s
分针走: 6°/m = 0.1°/s
所有在h:m:s时，时针的角度为30*h + m/2 + s/120;分针的角度为:6*m + s/10;
所有它们的夹角为fabs(30*h + m/2 + s/120 - 6*m - s/10) = fabs(30*h - 11*m/2 - 11*s/120)
当然，这是在12小时制下(而不是24小时)。


Problem

2076 夹角有多大(题目已修改,注意读题)

Problem Description
时间过的好快，一个学期就这么的过去了，xhd在傻傻的看着表，出于对数据的渴望，突然他想知道这个表的时针和分针的夹角是多少。现在xhd知道的只有时间，请你帮他算出这个夹角。

注：夹角的范围[0，180]，时针和分针的转动是连续而不是离散的。

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有三个整数h(0 <= h < 24)，m(0 <= m < 60)，s(0 <= s < 60)分别表示时、分、秒。

Output
对于每组输入数据，输出夹角的大小的整数部分。

Sample Input
2
8 3 17
5 13 30

Sample Output
138
75

Author
xhd

Source
ACM程序设计期末考试_热身赛(感谢 xhd & 8600)

Recommend
lcy


Problem

问题分析

Problem Analyse
递推题

Algorithm Analyse
既然最大的那个盘可以放在最上面，那就不用想汉诺塔III一样吧前n-1个盘全从1搬到3了。
只要从1搬到2，然后把第n个盘从1搬到2再搬到3，然后把这n-1个从2搬到3。
所以，问题转换成n个盘搬一步需要几次。但前n-1个盘和汉诺塔III的的规则是一样的。
所以，需要先把前n-2从1搬到3，然后把第n-1个盘从1搬到2，再把前n-2个盘从3搬到2。就完成了！
以为把n个盘按汉诺塔从1搬到3需要3n - 1(推导见2064)。
所以把n-1个盘移动1步，需要f(n) = f(n-1) + 3n-1
而f(1) = 1
所以f(n) = 3n-1 + 3n-2 + ... + 3 + 1 = (3n - 1) / 2
所以按汉诺塔IV的规则来，搬n个盘需要m(n) = 2 * f(n-1) + 2 = 3n-1 + 1


Problem

2077 汉诺塔IV

Problem Description
还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有一个正整数n(1 <= n <= 20)，表示有n个盘子。

Output
对于每组输入数据，最少需要的摆放次数。

Sample Input
2
1
10

Sample Output
2
19684

Author
xhd

Source
ACM程序设计期末考试_热身赛(感谢 xhd & 8600)

Recommend
lcy


Problem

编码建议

Programing
简单的求一下数列中的最小值。没有什么技巧。


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
按题目的介绍，如果前一门复习的课程的难度为m，后一门为n。那他复习后一门的效率就为(m-n)*(m-n);
自然，这里的m越大，n越小，它的效率自然就越高！
而m最大值为初始状态100，因此，我们的任务就是求它这么多要复习的课程中，难度最小的一门。即最小的n。


Problem

2078 复习时间

Problem Description
为了能过个好年，xhd开始复习了，于是每天晚上背着书往教室跑。xhd复习有个习惯，在复习完一门课后，他总是挑一门更简单的课进行复习，而他复习这门课的效率为两门课的难度差的平方,而复习第一门课的效率为100和这门课的难度差的平方。xhd这学期选了n门课，但是一晚上他最多只能复习m门课，请问他一晚上复习的最高效率值是多少？

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40)，m(1 <= m <= n)。
接着有n行，每行有一个正整数a(1 <= a <= 100)，表示这门课的难度值。

Output
对于每组输入数据，输出一个整数，表示最高效率值。

Sample Input
2
2 2
52
25
12 5
89
64
6
43
56
72
92
23
20
22
37
31

Sample Output
5625
8836

Author
xhd

Source
ACM程序设计期末考试_热身赛(感谢 xhd & 8600)

Recommend
lcy


Problem

问题分析

Problem Analyse
简单的麻烦题

Algorithm Analyse
这一题又是杭电跟我们开的国际玩笑。开始我还以为是用什么母函数做呢。结果...却是用暴力0MS 0K 过的。
但却发现OMS OK AC的人加上我只有3个人。我开始有点迷漫了～题目做多了就会有这个后遗症:容易把题目想复杂。
看来我们拿到一道题目，要首先考虑它的规模。只要可以避免走很多弯路。


Problem

2079 选课时间(题目已修改,注意读题)

Problem Description
又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知道学n个学分共有多少组合。你来帮帮他吧。（xhd认为一样学分的课没区别）

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40)，k(1 <= k <= 8)。
接着有k行，每行有两个整数a(1 <= a <= 8),b(1 <= b <= 10)，表示学分为a的课有b门。

Output
对于每组输入数据，输出一个整数，表示学n个学分的组合数。

Sample Input
2
2 2
1 2
2 1
40 8
1 1
2 2
3 2
4 2
5 8
6 9
7 6
8 8

Sample Output
2
445

Author
xhd

Source
ACM程序设计期末考试_热身赛(感谢 xhd & 8600)

Recommend
lcy


Problem

编码建议

Programing
给出第一种方法的AC代码:
#include <math.h>
#include <stdio.h>
#define sqr(x) ((x)*(x))
int main(void)
{
    int n;
    double x[2], y[2];

    scanf("%d", &n);
    while (n-- && scanf("%lf%lf%lf%lf", x, y, x+1, y+1))
    {
        y[0] = asin(y[0]/sqrt(sqr(x[0])+sqr(y[0])))/acos(-1)*180;
        y[1] = asin(y[1]/sqrt(sqr(x[1])+sqr(y[1])))/acos(-1)*180;
        if (!y[0] && x[0] < 0) y[0] = 180;
        if (!y[1] && x[1] < 0) y[1] = 180;
        y[0] -= y[1];
        while (y[0] < 0) y[0] += 360;
        while (y[0] > 360) y[0] -= 360;
        while (y[0] > 180) y[0] = 360 - y[0];
        printf("%.2f\n", y[0]);
    }

    return 0;
}


Problem

问题分析

Problem Analyse
数学题

Algorithm Analyse
我们可以先用arcsin求出每个点的角度。(不用arctan是因为x可能等于0)
公式:asin(y/sqrt(sqr(x)+sqr(y)))/acos(-1)*180;
之所以加个acos(-1)即π是因为C语言里的asin结果是弧度制，但我们需要角度制。
这里，我们要处理平角的情况(即180°)if (!y && x < 0) y = 180;
接下来就要求两个角度的差了(小于0的一直加360，大于360的一直减360)。
最后还要判断结果是否大于180°
这里我们没有考虑钝角的情况。比如输入-1 -1 1 0，一个输出135，但却只输出了45。可只要依然能AC。
所有这是题目的测试数据太弱。但我们直接必须注意。

本题还有个更简单的方法，因为输入的两个点与原点构成一个三角形。
又因为:S△ = 0.5 * sinψ * A * B
其中ψ就是A, B的夹角了。
而两点与原点构成的三角形的面积为:fabs(x[0]*y[1]-x[1]*y[0]) / 2;(推导见2036)


Problem

2080 夹角有多大II

Problem Description
这次xhd面临的问题是这样的：在一个平面内有两个点，求两个点分别和原点的连线的夹角的大小。

注：夹角的范围[0，180]，两个点不会在圆心出现。

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有四个实数x1,y1,x2,y2分别表示两个点的坐标,这些实数的范围是[-10000,10000]。

Output
对于每组输入数据，输出夹角的大小精确到小数点后两位。

Sample Input
2
1 1 2 2
1 1 1 0

Sample Output
0.00
45.00

Author
xhd

Source
ACM程序设计期末考试_热身赛(感谢 xhd & 8600)

Recommend
lcy


Problem

问题分析

Problem Analyse
字符串处理

Algorithm Analyse
这个不用说了把。你可以按字符串处理，也可以按整数处理。
给出以下两段AC代码: Code1:
#include <stdio.h>

int main(void)
{
    int n;
    char s[12];
    scanf("%d", &n);
    while (n--&&scanf("%s", s))
        printf("6%s\n", s+6);
    return 0;
}
Code2:
#include <stdio.h>

int main(void)
{
    int n;
    __int64 x;
    scanf("%d", &n);
    while (n--&&scanf("%I64d", &x))
        printf("6%05I64u\n", x % 100000);
    return 0;
}


Problem

2081 手机短号

Problem Description
大家都知道，手机号是一个11位长的数字串，同时，作为学生，还可以申请加入校园网，如果加入成功，你将另外拥有一个短号。假设所有的短号都是是 6+手机号的后5位，比如号码为13512345678的手机，对应的短号就是645678。
现在，如果给你一个11位长的手机号码，你能找出对应的短号吗？

Input
输入数据的第一行是一个N(N <= 200)，表示有N个数据，接下来的N行每一行为一个11位的手机号码。

Output
输入数据的第一行是一个N(N <= 200)，表示有N个数据，接下来的N行每一行为一个11位的手机号码。

Sample Input
2
13512345678
13787654321

Sample Output
645678
654321

Author
不详

Source
2006/1/15 ACM程序设计期末考试

Recommend
lcy


Problem

编码建议

Programing
多项式的表示方法很多，本题不是稀疏的多项式，所有直接用一个一维数组就可以了。


Problem

问题分析

Problem analyse
经典的母函数题目

algorithm analyse
如果有一组序列:a0, a1, a2, a3, ...
存在一个多项式G(X) = a0 + a1X + a2X2 + a3X3 + ...
则成G(X)是序列:a0, a1, a2, a3, ...的母函数。

比如:
(1 + x)n = C0n + C1nX1 + ... + CnnXn
所以，(1 + x)n是序列C0n， C1n, ..., Cnn的母函数

用母函数解题，就是用多项式的指数来代表某一属性(质量、分数、体积...)，前面的系数为它的种数。
比如:
若有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？各有几种可能方案？
按上面讲的，我们把X的指数设为质量。所以:
1克能表示0克和1克两种，所有是:X0 + X1 = 1 + X1
2克能表示0克和2克两种，所有是:X0 + X2 = 1 + X2
3克能表示0克和3克两种，所有是:X0 + X3 = 1 + X3
4克能表示0克和4克两种，所有是:X0 + X4 = 1 + X4
几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示:
(1 + X1)(1 + X2)(1 + X3)(1 + X4)
=1 + X1 + X2 + 2X3 + 2X4 + 2X5 + 2X6 + 2X7 + X8 + X9 + X10
所以，能称出0->10克的重量。3->7都有两种表示方法，其他的都只有1种。

因此，本题就是求1->50的母函数的系数和。


Problem

2082 找单词

Problem Description
假设有x1个字母A， x2个字母B,..... x26个字母Z，同时假设字母A的价值为1，字母B的价值为2,..... 字母Z的价值为26。那么，对于给定的字母，可以找到多少价值<=50的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词ACM的价值是1+3+14=18，单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关，比如ACM与CMA认为是同一个单词）。

Input
输入首先是一个整数N，代表测试实例的个数。
然后包括N行数据，每行包括26个<=20的整数x1,x2,.....x26.

Output
对于每个测试实例，请输出能找到的总价值<=50的单词数,每个实例的输出占一行。

Sample Input
2
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9

Sample Output
7
379297

Author
不详

Source
2006/1/15 ACM程序设计期末考试

Recommend
lcy


Problem

编码建议

Programing
输入的顶点可能无序，所有先要排序。


Problem

问题分析

Problem Analyse
数学题

Algorithm Analyse
最短的当然是从中间n/2处开始咯。呵呵。


Problem

2083 简易版之最短距离

Problem Description
寒假的时候，ACBOY要去拜访很多朋友，恰巧他所有朋友的家都处在坐标平面的X轴上。ACBOY可以任意选择一个朋友的家开始访问，但是每次访问后他都必须回到出发点，然后才能去访问下一个朋友。
比如有4个朋友，对应的X轴坐标分别为1， 2， 3， 4。当ACBOY选择坐标为2的点做为出发点时，则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| = 4。
现在给出Ｎ个朋友的坐标，那么ACBOY应该怎么走才会花费时间最少呢？

Input
输入首先是一个正整数M，表示M个测试实例。每个实例的输入有2行，首先是一个正整数N（N <= 500)，表示有N个朋友，下一行是N个正整数，表示具体的坐标(所有数据均<=10000).

Output
对于每一个测试实例，请输出访问完所有朋友所花的最少时间，每个实例的输出占一行。

Sample Input
2
2
2 4
3
2 4 6

Sample Output
2
4

Author
不详

Source
2006/1/15 ACM程序设计期末考试

Recommend
lcy


Problem

编码建议

Programing
这是一个下三角矩阵，直接开二维数组太浪费空间了。可以开个一维数组压缩空间。


Problem

问题分析

Problem Analyse
二维数组上的动态规划

Algorithm Analyse
前面已经做过两道一维数组上的动态规划。
二维数组上的动态规划就是一个递归的过程了。
我们知道，在求解的过程中，很多元素的值都算了不止一次，所有我们可以开个数组把这些已经计算出来的中间值保存下来。
这就是编程的又一大原则:以空间换时间。
我们把原来的数塔保存入一个二维数组g[n][n]里
公式是:
f[i][j] = g[i][j] + max(f[i+1][j], f[i+1][j+1]) (i < n)
f[i][j] = g[i][j] (i = n)
最后我们输出f[0][0]就可以了。
下面给出动态规划的AC代码:
#include <stdio.h>
#include <string.h>

#define max(a,b) (a)>(b)?(a):(b)

int    f[120][120];
int    g[120][120];
int    n;

int fc(int i,int j)
{
    if(f[i][j]==-1)
        f[i][j]=i==n-1?g[i][j]:max(g[i][j]+fc(i+1,j),g[i][j]+fc(i+1,j+1));
    return f[i][j];
}

int main(void)
{
    int    c;
    int    i;
    int    j;

    scanf("%d", &c);
    while (c--)
    {
        memset(f,-1,sizeof(f));
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            for(j=0;j<=i;j++)
                scanf("%d",&g[i][j]);
        }
        printf("%d\n",fc(0,0));
    }
    return 0;
}
但其实这一题完全可以不用动态规划。
我们从最下层往上推，比如到了第i层，比较f(i, j)和f(i, j+1)，把较大值加到f(i-1, j)上。
事实证明，这样算的速度比动态规划要快。


Problem

2084 数塔

Problem Description
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?

Input
输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output
30

Author
不详

Source
2006/1/15 ACM程序设计期末考试

Recommend
lcy


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
公式都给我们了，还等什么？直接AC掉它！
公式:
g[i] = 3 * g[i - 1] + 2 * d[i - 1];
d[i] = g[i - 1] + d[i - 1];


Problem

2085 核反应堆

Problem Description
某核反应堆有两类事件发生：
高能质点碰击核子时，质点被吸收，放出3个高能质点和1个低能质点；
低能质点碰击核子时，质点被吸收，放出2个高能质点和1个低能质点。
假定开始的时候（0微秒）只有一个高能质点射入核反应堆，每一微秒引起一个事件发生(对于一个事件，当前存在的所有质点都会撞击核子)，试确定n微秒时高能质点和低能质点的数目。

Input
输入含有一些整数n(0≤n≤33)，以微秒为单位，若n为-1表示处理结束。

Output
分别输出n微秒时刻高能质点和低能质点的数量，高能质点与低能质点数量之间以逗号空格分隔。每个输出占一行。

Sample Input
5 2
-1

Sample Output
571, 209
11, 4

提示 可以使用long long int对付GNU C++，使用__int64对付VC6

Author
不详

Source
2006/1/15 ACM程序设计期末考试

Recommend
lcy


Problem

问题分析

Problem Analyse
公式推导

Algorithm Analyse
Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, .... n). 用A5做示范，就能猜测出公式来。证明方法可以采用数学归纳法。这里证明从略。
A5 = (A4 + A6) / 2 - C5

A4 = (A3 + A5) / 2 - C4 = A3 / 2 + A4 / 4 + A6 / 4 - C5 / 2 - C4
=>A4 = 2A3/3 + A6/3 - 2C5/3 - 4C4/3

A3 = (A2 + A4) / 2 - C3 = A2 / 2 + A3 / 3 + A6 / 6 - C5 / 3 - 2C4 / 3 - C3
=>A3 = 3A2/4 + A6/4 - C5/2 - C4 - 3C3/2

A2 = (A1 + A3) / 2 - C2 = A1 / 2 + 3A2 / 8 + A6 / 8 - C5 / 4 - C4 / 2 - 3C3 / 4 - C2
=>A2 = 4A1/5 + A6/5 - 2C5/5 - 4C4/5 - 6C3/5 - 8C2/5

A1 = (A0 + A2) / 2 - C1 = A0 / 2 + 2A1 / 5 + A6 / 10 - C5 / 5 - 2C4 / 5 - 3C3 / 5 - 4C2 / 5 - C1
=>A1 = 5A0/6 + A6/6 - C5/3 - 2C4/3 - C3 - 4C2/3 - 5C1/3

算到这里，我想你已经总结出公式了:
A1 = (n * A0 + An+1 - 2 * Cn - 4 * Cn-1 - ... - 2 * i * Cn-i+1 - 2 * n * C1) / (n + 1)


Problem

2086 A1 = ?

Problem Description
有如下方程：Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, .... n).
若给出A0, An+1, 和 C1, C2, .....Cn.
请编程计算A1 = ?

Input
输入包括多个测试实例。
对于每个实例，首先是一个正整数n,(n <= 3000); 然后是2个数a0, an+1.接下来的n行每行有一个数ci(i = 1, ....n);输入以文件结束符结束。

Output
对于每个测试实例，用一行输出所求得的a1(保留2位小数).

Sample Input
1
50.00
25.00
10.00
2
50.00
25.00
10.00
20.00

Sample Output
27.50
15.00

Author
不详

Source
2006/1/15 ACM程序设计期末考试

Recommend
lcy


Problem

编码建议

Programing
直接调用库函数strstr()。
strstr
语法:

#include <string.h>
char *strstr( const char *str1, const char *str2 );

功能：函数返回一个指针，它指向字符串str2 首次出现于字符串str1中的位置，如果没有找到，返回NULL。


Problem

问题分析

Problem Analyse
字符串处理

Algorithm Analyse
这一题就是在字符串里查找字符串。


Problem

2087 剪花布条

Problem Description
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

Input
输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。

Output
输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。

Sample Input
abcde a3
aaaaaa aa
#

Sample Output
0
3

Author
qianneng

Source
冬练三九之二

Recommend
lcy


Problem

问题分析

Problem Analyse
小鲍勃喜欢玩他的方盒子。他把那些盒子叠成不同高度的栈。他对他的姐姐艾丽丝说：“看，我砌成了一堵墙！” “你只有把所有的栈调整成相同的高度，那样才算是一堵真正的墙。”她回应道。 经过短暂的思考，鲍勃觉得她是对的。为了使栈能一样高，他只好一个一个地搬盒子。 但是鲍勃很懒，他想搬最小的次数来达到目的。你能帮助他吗？

简单题

Algorithm Analyse
只要求个平均值就可以了。再算出大于平均值的数是多少。


Problem

2088 Box of Bricks

Problem Description
Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. “Look, I've built a wall!”, he tells his older sister Alice. “Nah, you should make all stacks the same height. Then you would have a real wall.”, she retorts. After a little consideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?

Input
The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume 1≤n≤50 and 1≤hi≤100.

The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.

The input is terminated by a set starting with n = 0. This set should not be processed.

Output
For each set, print the minimum number of bricks that have to be moved in order to make all the stacks the same height.
Output a blank line between each set.

Sample Input
6
5 2 4 1 7 5
0

Sample Output
5

Author
qianneng

Source
冬练三九之二

Recommend
lcy


Problem

编码建议

Programing
直接静态申请，可能开不出1000000这么大的数组，用动态申请一个。


Problem

问题分析

Problem Analyse
数学题

Algorithm Analyse
一旦碰到62或者4，就进位。
比如，循环到了1234，就加1，到了123400，就加100到123500，碰到62000加1000到63000，依次类推即可。


Problem

2089 不要62

Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input
1 100
0 0

Sample Output
80

Author
qianneng

Source
迎接新学期——超级Easy版热身赛

Recommend
lcy


Problem

编码建议

Programing
所谓的四舍五入，直接保留一位输出就可以了。


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
直接按题意做。


Problem

2090 算菜价

Problem Description
妈妈每天都要出去买菜，但是回来后，兜里的钱也懒得数一数，到底花了多少钱真是一笔糊涂帐。现在好了，作为好儿子（女儿）的你可以给她用程序算一下了，呵呵。

Input
输入含有一些数据组，每组数据包括菜种（字串），数量（计量单位不论，一律为double型数）和单价（double型数，表示人民币元数），因此，每组数据的菜价就是数量乘上单价啊。菜种、数量和单价之间都有空格隔开的。

Output
支付菜价的时候，由于最小支付单位是角，所以总是在支付的时候采用四舍五入的方法把分头去掉。最后，请输出一个精度为角的菜价总量。

Sample Input
青菜 1 2
萝卜 2 1.5
鸡腿 2 4.2

Sample Output
13.4

Author
qianneng

Source
迎接新学期——超级Easy版热身赛

Recommend
lcy


Problem

编码建议

Programing
这一题的确没什么算法可言，但编程技巧倒是有的。
很多人可能不知道'*'在格式化输入输出中的作用。

在scanf()中，用%*#，就代表读入一个#的数据，但不处理。比如:
scanf("%c%*c%c", &a, &b);
输入ABC，此时，变量a='A', c='C'。而中间的'B'，只是读入，没有做任何处理。

在printf()中，%*#用来设定场宽。
我们平时用%2d一类的转义字符来代表输出整形d时场宽为2个字符，但这种方法设置场宽只能是常数，不能在程序运行时其变化。
而用'*'，就做到了可变场宽的作用。比如:
printf("%*d", 4, a);
表示输出整形数据a，场宽为4个字符。

用'*'的这一特性，可以很轻松搞定这一题。


Problem

问题分析

Problem Analyse
字符串处理

Algorithm Analyse
Empty


Problem

2091 空心三角形

Problem Description
把一个字符三角形掏空，就能节省材料成本，减轻重量，但关键是为了追求另一种视觉效果。在设计的过程中，需要给出各种花纹的材料和大小尺寸的三角形样板，通过电脑临时做出来，以便看看效果。

Input
每行包含一个字符和一个整数n(0<n<41)，不同的字符表示不同的花纹，整数n表示等腰三角形的高。显然其底边长为2n-1。如果遇到@字符，则表示所做出来的样板三角形已经够了。

Output
每个样板三角形之间应空上一行，三角形的中间为空。显然行末没有多余的空格。

Sample Input
X 2
A 7
@

Sample Output
X
XXX

A
A A
A A
A A
A A
A A
AAAAAAAAAAAAA

Author
qianneng

Source
迎接新学期——超级Easy版热身赛

Recommend
lcy


Problem

问题分析

Problem Analyse
数学题

Algorithm Analyse

∵x + y = n
∴y = n - x
∵xy = m
∴(n - x) * x = m
∴x2 - nx + m = 0
∵m是整数，且xy = m
∴x、y都是整数。
∴要判断是否有整数解，就要判断方程:x2 - nx + m = 0的△是否为完全平方数。


Problem

2092 整数解

Problem Description
有二个整数，它们加起来等于某个整数，乘起来又等于另一个整数，它们到底是真还是假，也就是这种整数到底存不存在，实在有点吃不准，你能快速回答吗？看来只能通过编程。
例如：
x + y = 9，x * y = 15 ? 找不到这样的整数x和y
1+4=5，1*4=4，所以，加起来等于5，乘起来等于4的二个整数为1和4
7+(-8)=-1，7*（-8）=-56，所以，加起来等于-1，乘起来等于-56的二个整数为7和-8

Input
输入数据为成对出现的整数n，m（-10000<n,m<10000），它们分别表示整数的和与积，如果两者都为0，则输入结束。

Output
只需要对于每个n和m，输出“Yes”或者“No”，明确有还是没有这种整数就行了。

Sample Input
9 15
5 4
1 -56
0 0

Sample Output
No
Yes
Yes

Author
qianneng

Source
迎接新学期——超级Easy版热身赛

Recommend
lcy


Problem

编码建议

Programing
因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。
这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()!

sscanf
语法:

#include int sscanf( const char *buffer, const char *format, ... );

函数sscanf()和scanf()类似, 只是输入从buffer(缓冲区)中读取.
比如:sscanf("1 2 3", "%d%d%d", &a, &b, &c);
则a = 1, b = 2, c = 3;

只要输入表格内容后，用格式化输入"%d(%d)"，然后判断输入结果，如果是2，表示带有括号，如果是1，则没有括号。
排序直接用快速排序就可以了。规则已经说的很清楚了。


Problem

问题分析

Problem Analyse
编程技巧题

Algorithm Analyse
规则很简单，没什么好讲的。主要考察你编程的技巧性。


Problem

2093 考试排名

Problem Description
C++编程考试使用的实时提交系统，具有即时获得成绩排名的特点。它的功能是怎么实现的呢？
我们做好了题目的解答，提交之后，要么“AC”，要么错误，不管怎样错法，总是给你记上一笔，表明你曾经有过一次错误提交，因而当你一旦提交该题“AC”后，就要与你算一算帐了，总共该题错误提交了几回。虽然你在题数上，大步地跃上了一个台阶，但是在耗时上要摊上你共花去的时间。特别是，曾经有过的错误提交，每次都要摊上一定的单位时间分。这样一来，你在做出的题数上，可能领先别人很多，但是，在做出同样题数的人群中，你可能会在耗时上处于排名的劣势。
例如：某次考试一共8题（A，B，C，D，E，F，G，H），每个人做的题都在对应的题号下有个数量标记，负数表示该学生在该题上有过的错误提交次数，但到现在还没有AC，正数表示AC所耗的时间，如果正数a跟上一对括号，里面有个整数b，那就表示该学生提交该题AC了，耗去了时间a，同时，曾经错误提交了b次，因此对于下述输入数据：

若每次错误提交的罚分为20分，则其排名从高到低应该是这样的：
Josephus 5 376
John 4 284
Alice 4 352
Smith 3 167
Bob 2 325
Bush 0 0

Input
输入数据的第一行是考试题数n（1≤n≤12）以及单位罚分数m（10≤m≤20），每行数据描述一个学生的用户名（不多于10个字符的字串）以及对所有n道题的答题现状，其描述采用问题描述中的数量标记的格式，见上面的表格，提交次数总是小于100，AC所耗时间总是小于1000。

Output
将这些学生的考试现状，输出一个实时排名。实时排名显然先按AC题数的多少排，多的在前，再按时间分的多少排，少的在前，如果凑巧前两者都相等，则按名字的字典序排，小的在前。每个学生占一行，输出名字（10个字符宽），做出的题数（2个字符宽，右对齐）和时间分（4个字符宽，右对齐）。名字、题数和时间分相互之间有一个空格。

Sample Input

8 20
Smith		-1	-16	8	0	0	120	39	0
John		116	-2	11	0	0	82	55(1)	0
Josephus		72(3)	126	10	-3	0	47	21(2)	-2
Bush	  	0	-1	-8	0	0	0	0	0
Alice		-2	67(2)	13	-1	0	133	79(1)	-1
Bob		0	0	57(5)	0	0	168	-7	0

Sample Output

Josephus    5  376
John        4  284
Alice       4  352
Smith       3  167
Bob         2  325
Bush        0    0

Author
qianneng

Source
迎接新学期——超级Easy版热身赛

Recommend
lcy


Problem

编码建议

Programing
这里名字映射直接用C++的STL库map，和set。


Problem

问题分析

Problem Analyse
拓扑排序

Algorithm Analyse
但输入A 战胜 B时，就让B指向A。
最后，指向空的就说明没有人战胜过他。如果这样的人只存在一个，那他就是冠军了。


Problem

2094 产生冠军

Problem Description
有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

Input
输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。

Output
对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。

Sample Input
3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

Sample Output
Yes
No

Author
qianneng

Source
迎接新学期——超级Easy版热身赛

Recommend
lcy


Problem

编码建议

Programing
映射直接用STL里的map。


Problem

问题分析

Problem Analyse
在新年聚会上，所有人都会收到一份特殊的礼物。选择轮到你领取自己的礼物了。在桌子上有一大堆礼物，其中只有一个是你的。 每个礼物上都标有一个号码。而你的礼物的号码是与其他所有礼物都不相同的。你可以假定只有一个数字只出现一次。 例如，现在有5个礼物，他们分别标号伪1，2，3，2，1。所以，你的礼物就是标号为3的那个。因为3只出现了1次。

集合论

Algorithm Analyse
用哈希记录所有出现过的数字的个数，最后出现一次的就是结果。


Problem

2095 find your present (2)

Problem Description
In the new year party, everybody will get a "special present".Now it's your turn to get your special present, a lot of presents now putting on the desk, and only one of them will be yours.Each present has a card number on it, and your present's card number will be the one that different from all the others, and you can assume that only one number appear odd times.For example, there are 5 present, and their card numbers are 1, 2, 3, 2, 1.so your present will be the one with the card number of 3, because 3 is the number that different from all the others.

Input
The input file will consist of several cases. Each case will be presented by an integer n (1<=n<1000000, and n is odd) at first. Following that, n positive integers will be given in a line, all integers will smaller than 2^31. These numbers indicate the card numbers of the presents.n = 0 ends the input.

Output
For each case, output an integer in a line, which is the card number of your present.

Sample Input
5
1 1 3 2 2
3
1 2 1
0

Sample Output
3
2

Author
8600

Source
HDU2007spring校赛__热身(1)

Recommend
8600


Problem

问题分析

Problem Analyse
简单题

Algorithm Analyse
Empty


Problem

2096 小明A+B

Problem Description
小明今年3岁了, 现在他已经能够认识100以内的非负整数, 并且能够进行100以内的非负整数的加法计算.
对于大于等于100的整数, 小明仅保留该数的最后两位进行计算, 如果计算结果大于等于100, 那么小明也仅保留计算结果的最后两位.

例如, 对于小明来说:
1) 1234和34是相等的
2) 35+80=15

给定非负整数A和B, 你的任务是代表小明计算出A+B的值.

Input
输入数据的第一行为一个正整数T, 表示测试数据的组数. 然后是T组测试数据. 每组测试数据包含两个非负整数A和B(A和B均在int型可表示的范围内).

Output
对于每组测试数据, 输出小明A+B的结果.

Sample Input
2
35 80
15 1152

Sample Output
15
67

Author
不详

Source
HDU2007spring校赛

Recommend
lcy


Problem

问题分析

Problem Analyse
进制转换

Algorithm Analyse
进制转换相关知识请参阅2031题。


Problem

2097 Sky数

Problem Description
Sky从小喜欢奇特的东西，而且天生对数字特别敏感，一次偶然的机会，他发现了一个有趣的四位数2992，这个数，它的十进制数表示，其四位数字之和为2+9+9+2=22，它的十六进制数BB0，其四位数字之和也为22，同时它的十二进制数表示1894，其四位数字之和也为22，啊哈，真是巧啊。Sky非常喜欢这种四位数，由于他的发现，所以这里我们命名其为Sky数。但是要判断这样的数还是有点麻烦啊，那么现在请你帮忙来判断任何一个十进制的四位数，是不是Sky数吧。

Input
输入含有一些四位正整数，如果为0，则输入结束。

Output
若n为Sky数，则输出“#n is a Sky Number.”，否则输出“#n is not a Sky Number.”。每个结果占一行。注意：#n表示所读入的n值。

Sample Input
2992
1234
0

Sample Output
2992 is a Sky Number.
1234 is not a Sky Number.

Author
不详

Source
2007省赛集训队练习赛（2）

Recommend
lcy


Problem

编码建议

Programing
求质数的文章: [原创]求质数(C语言描述) 【问题描述】：
试编写一个程序，找出2->N之间的所有质数。希望用尽可能快的方法实现。
【问题分析】：
这个问题可以有两种解法：一种是用“筛子法”，另一种是从2->N检查，找出质数。
先来简单介绍一下“筛法”，求2~20的质数，它的做法是先把2~20这些数一字排开：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
先取出数组中最小的数，是2，则判断2是质数，把后面2的倍数全部删掉。
2 | 3 5 7 9 11 13 15 17 19
接下来的最小数是3，取出，再删掉3的倍数
2 3 | 5 7 11 13 17 19
一直这样下去，直到结束。
筛法求质数的问题时，非质数的数据有很多是重复的。例如，如果有一个数3×7×17×23，那么在删除3的倍数时会删到它，删7、17、23时同样也会删到它。有一种“线性筛法”，可以安排删除的次序，使得每一个非质数都只被删除一次。从而提高效率。因为“筛法”不是我要介绍的重点，所以就不介绍了。
现在我来介绍第二种方法。用这种方法，最先想到的就是让从2~N逐一检查。如果是就显示出来，如果不是，就检查下一个。这是正确的做法，但效率却不高。当然，2是质数，那么2的倍数就不是质数，如果令i从2到N，就很冤枉地测试了4、6、8……这些数？所以第一点改建就是只测试2与所有的奇数就足够了。同理，3是质数，但6、9、12……这些3的倍数却不是，因此，如果能够把2与3的倍数跳过去而不测试，任意连续的6个数中，就只会测试2个而已。以6n,6n+1,6n+2,6n+3,6n+4,6n+5为例，6n,6n+2,6n+4是偶数，又6n+3是3的倍数，所以如果2与3的倍数都不理会，只要测试的数就只留下6n+1和6n+5而已了，因而工作量只是前面想法的2/6=1/3，应该用这个方法编程。
还有个问题，就是如果判断一个数i是否为素数。按素数的定义，也就是只有1与本身可以整除，所以可以用2~i-1去除i，如果都除不尽，i就是素数。观点对，但却与上一点一样的笨拙。当i>2时，有哪一个数可以被i-1除尽的？没有，为什么？如果i不是质数，那么i=a×b，此地a与b既不是i又不是1；正因为a>1，a至少为2，因此b最多也是i/2而已，去除i的数用不着是2~i-1，而用2~i/2就可以了。不但如此，因为i=a×b，a与b不能大于sqrt(i),为什么呢？如果a>sqrt(i),b>sqrt(i),于是a×b>sqrt(i)*sqrt(i)=i，因此就都不能整除i了。如果i不是质数，它的因子最大就是sqrt(i)；换言之，用2~sqrt(i)去检验就行了。
但是，用2~sqrt(i)去检验也是浪费。就像前面一样，2除不尽，2的倍数也除不尽；同理，3除不尽，3的倍数也除不尽……最理想的方法就是用质数去除i。
但问题是这些素数从何而来？这比较简单，可以准备一个数组prime[]，用来存放找到的素数，一开始它里面有2、3、5。检查的时候，就用prime[]中小于sqrt(i)的数去除i即可，如果都除不尽，i就是素数，把它放如prime[]中，因此prime[]中的素数会越来越多，直到满足个数为止！
不妨用这段说明来编写这个程序，但是程序设计的时候会有两个小问题：
1.如果只检查6n+1和6n+5？不难发现，它们的距离是4、2、4、2……所以，可以先定义一个变量gab=4，然后gab=6-gab;
2.比较是不能用sqrt(i)，因为它不精确。举个例子，i=121，在数学上，sqrt(i)自然是11，但计算机里的结果可能是10.9999999，于是去除的数就是2、3、5、7，而不含11，因此121就变成质数了。解决这个问题的方法很简单，不要用开方，用平方即可。例如，如果p*p<=i，则就用p去除i。而且它的效率比开方高。
【程序清单】：
#include <stdio.h>

int creat_prime(int prime[],int n,int total)
{
        register        int        i;
        register        int        j;
        register        int        gab=2;
        register        int        count;
        for(i=7;i<=n;i+=gab)
        {
                count=1;
                gab=6-gab;
                for(j=0;prime[j]*prime[j]<=i;j++)
                {
                        if(i%prime[j]==0)
                        {
                                count=0;
                                break;
                        }
                }
                if(count)
                {
                        prime[total]=i;
                        total++;
                }
        }

        return total;
}

int main(void)
{
        int        prime[30000]={2,3,5};
        int        total=3;        //找到素数的个数
        int        i;
        int        n=200000;        //要查找的范围(>=6)

        total=creat_prime(prime,n,total);
        for(i=0;i<total;i++)
        {
                printf("%d ",prime[i]);
                if(i && !(i%10))
                        putchar('\n');
        }
        putchar('\n');
}

如果你有VC++或其他C编译器，可以去运行一下。
你会发现，会有很多时间去输出。我给个小提示，
假设你编译生成的可执行文件是prime.exe，目录在D:\
那你在命令行下进如D:\然后输入命令 prime >1.txt
这样就可以把结果保存到1.txt。
你会发现在int越界的前提下，它几乎都是瞬间完成的！

当然这段程序还是有可以改进的地方，如果你有更好的建议，请联系我。
redraiment@126.com


Problem

问题分析

Problem Analyse
数论

Algorithm Analyse
先生成1->10000之间的素数表。然后直接判断。
关于生成素数的算法，请参阅我的空间http://hi.baidu.com/redraiment/里的文章《求质数》。


Problem

2098 分拆素数和

Problem Description
把一个偶数拆成两个不同素数的和，有几种拆法呢？

Input
输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。

Output
对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。

Sample Input
30
26
0

Sample Output
3
2

Author
不详

Source
2007省赛集训队练习赛（2）

Recommend
lcy


Problem

2099 整除的尾数

Problem Description
一个整数，只知道前几位，不知道末二位，被另一个整数除尽了，那么该数的末二位该是什么呢？

Input
输入数据有若干组，每组数据包含二个整数a，b（0<a<10000, 10<b<100），若遇到0 0则处理结束。

Output
对应每组数据，将满足条件的所有尾数在一行内输出，格式见样本输出。同组数据的输出，其每个尾数之间空一格，行末没有空格。

Sample Input
200 40
1992 95
0 0

Sample Output
00 40 80
15

Author
不详

Source
2007省赛集训队练习赛（2）

Recommend
lcy


Easy CHM - http://www.eTextWizard.com

您现在使用的CHM文件由Easy CHM的未注册版本制作.
注册版本不会在CHM里自动添加此页面

Easy CHM 软件 软件出品: 国华软件 中国北京 |  | 截屏图片
 | 文件大小: 1392k - 1.39MB | 软件类型: 共享软件 购买注册: 这里
关键词: make chm, create chm, chm制作工具, chm电子书制作工具,chm帮助文件制作工具

描述:

Easy CHM是国华软件推出的一款强大的CHM电子书或CHM帮助文件的快速制作工具。使用EasyCHM只需要三个步骤就可以完成CHM的制作：1、用户指定一个目录，EasyCHM会自动导入全部目录及文件；2、设置CHM编译选项；3、开始制作。EasyCHM非常适合个人和单位制作高压缩比的带有全文检索及高亮显示搜索结果的网页集锦、CHM帮助文件、产品说明、公司介绍、CHM电子书等等。

主要功能：

  • 全自动的目录及文件导入（可以包括子目录）；
  • 自动生成上下文相关的帮助文件直接供程序员使用；
  • 支持导入任意的文件类型；
  • 自动生成CHM的目录列表并自动生成所有目录项；
  • 为CHM的目录列表自动添加多级编号；
  • 批量更换CHM目录各项的图标；
  • 支持批量查找替换多级目录各项的标题文字内容；
  • 允许用户指定从文本文件的第N行自动截取标题；
  • 易用的目录编辑器；
  • 丰富实用的CHM制作选项帮助用户制作更加个性化的专业CHM电子书或CHM帮助文件。
  • 内嵌CHM反编译工具。
  • 用户可以保存和打开工程文件。

EasyCHM未注册版本的主要限制：

  1. EasyCHM的未注册版本可以制作带任意层级目录的CHM，但是每个CHM的工具栏上都会自动添加一个ABOUT按钮，以提醒用户注册。注册版本不会添加ABOUT按钮。
  2. EasyCHM的未注册版本无法保存CHM的通用工程文件，如*.HHP、*.HHC、*.HHK等，未注册版本的EasyCHM会自动删除*.HHP、*.HHC、*.HHK这几个文件。

注册版本无任何限制。
如果EasyCHM可以为您的工作和学习提供帮助，请注册购买，感谢您给予软件作者的支持。
联系方式:
国华软件站点一: http://www.etextwizard.com
国华软件站点二: http://www.zipghost.com
技术支持信箱: webmaster@etextwizard.com
购买方式:
在线购买:（可提供发票，支持很多种支付方式，包括邮政汇款）
单用户企业版 299元 人民币 ：通过“共享软件注册中心”购买

单用户家庭版 99元 人民币： 通过“共享软件注册中心”购买
直接向作者注册（共3种方式）：
1、招商银行划款:
开户行： 招商银行北京分行双榆树支行
帐 号： 001015570093
户 名： 冯国华
2、中国农业银行金穗卡转帐（注意是卡号）：
金穗卡卡号： 95599 8001 42061 34216
收 款 人： 冯国华
3、中国工商银行牡丹灵通卡转帐：

开户城市：北京
牡丹灵通卡卡号：9558 8202 0000 3186295 （注意是卡号9558820200003186295）
收 款 人： 冯国华

注意事项：
直接向作者注册的用户请在汇出足额的注册费后以EMAIL形式通知作者，同时请尽量提供

  • 汇款日期

  • 汇出城市

  • 汇出行

  • 汇款人姓名

  • 用于接收注册码的信箱（请确保可以接收邮件，最好多提供）

  • 您希望的注册用户名

  • 要注册的软件及套数

您提供的资料详细些会比较方便确认。
作者在确认支付已完成后将会马上发出注册码。
用户在收到注册信后请尽量给软件作者发个类似“已收到注册码”的确认信 - 感谢您的配合！
下载地址:

系统需求: Win98,WinME,WinXP,Windows2000
安装支持: 支持安装及卸载