[讨论][开源]第十七期编程题目.

Sum of Factorials

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 1712 Accepted Submit: 496

--------------------------------------------------------------------------------

John von Neumann, b. Dec. 28, 1903, d. Feb. 8, 1957, was a Hungarian-American mathematician who made important contributions to the foundations of mathematics, logic, quantum physics, meteorology, science, computers, and game theory. He was noted for a phenomenal memory and the speed with which he absorbed ideas and solved problems. In 1925 he received a B.S. diploma in chemical engineering from Zurich Institute and in 1926 a Ph.D. in mathematics from the University of Budapest. His Ph.D. dissertation on set theory was an important contribution to the subject. At the age of 20, von Neumann proposed a new definition of ordinal numbers that was universally adopted. While still in his twenties, he made many contributions in both pure and applied mathematics that established him as a mathematician of unusual depth. His Mathematical Foundations of Quantum Mechanics (1932) built a solid framework for the new scientific discipline. During this time he also proved the mini-max theorem of GAME THEORY. He gradually expanded his work in game theory, and with coauthor Oskar Morgenstern he wrote Theory of Games and Economic Behavior (1944).

There are some numbers which can be expressed by the sum of factorials. For example 9, 9 = 1! + 2! + 3! Dr. von Neumann was very interested in such numbers. So, he gives you a number n, and wants you to tell him whether or not the number can be expressed by the sum of some factorials.

Well, it's just a piece of cake. For a given n, you'll check if there are some xi, and let n equal to SUM{xi!} (1 <= i <= t, t >= 1, xi >= 0, xi = xj iff. i = j). If the answer is yes, say "YES"; otherwise, print out "NO".

Input

You will get several non-negative integer n (n <= 1,000,000) from input. Each one is in a line by itself.

The input is terminated by a line with a negative integer.

Output

For each n, you should print exactly one word ("YES" or "NO") in a single line. No extra spaces are allowed.

Sample Input

9
-1

Sample Output

YES

http://acm.zju.edu.cn/show_problem.php?pid=2358

----------------解决方案--------------------------------------------------------

简单翻译一下.
John von Neumann, b. Dec. 28,1903,d. Feb. 8, 1957,美籍的匈牙利人，数学家，对
数学基础，逻辑，物理量子学，气象学，计算机和游戏理论做出过重大贡献。他因大型内存和专研观点和解题速度被人们注意。在1925年，他得到英国苏黎士学会化学文凭，在1926年得到Budapest大学数学博士文凭。他的博士论文在理论上对课题有重要贡献。在他20岁时，von Neumann开发了一种新的数字序列定义，被全世界采用。当他还在20几岁时，他对纯数学和应用数学做出来重要的贡献，建立了他作为一个数学家不同寻常的深度。他的量子力学数学基础（1932）建立一个新的科学训练体系。在这期间他也证明了游戏理论的迷你最大定理。他渐渐地扩展了他的游戏理论的工作，和合作者Oskar Morgenstern ，他写了游戏理论和经济现象（1944）.

有很多数能被表示成阶乘的和。例如 9,9=1!+2!+3! Neumann 对这个数很感兴趣。所以，
他给了你一个数字n，想让你告诉他是否这个数能被表示成阶乘的和。

当然，这只是小菜一叠。对于一个数n，你将检查是否有xi,使n等于SUM{xi!}(a<=i<=t,
t>=i,xi>=0,xi=xj,若i=j).如果答案是可以的，就说"YES";否则，输出"NO".

Input

你将从输入中得到一些非负整数n(n<=1,000,000)。每个数占一行。
输入一一行负整数终止。

Output

对于每个n,你应该在一行中输出一个准确的单词（"YES" 或 "NO"）。后面没有额外的空格。

Sample Input

9
-1

Sample Output

YES

----------------解决方案--------------------------------------------------------

--------------------------------------------------------------------------------

Prime Distance

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 689 Accepted Submit: 169

--------------------------------------------------------------------------------

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.

Your program is given 2 numbers: L and U (1 <= L < U <= 2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L <= C1 < C2 <= U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L <= D1 < D2 <= U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).

Input

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.

Output

For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.

Sample Input

2 17
14 17

Sample Output

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

http://acm.zju.edu.cn/show_problem.php?pid=1842

----------------解决方案--------------------------------------------------------
大意如下:
输入L,U
(1 <= L < U <= 2,147,483,647).
L,U的差不超过1,000,000
求L,U之间相差最近的相邻素数和相差最远的相邻素数，如果L,U之间只有一个的话则输出没有
----------------解决方案--------------------------------------------------------

1:
解法一:

解法二:

[此贴子已经被作者于2007-5-30 22:16:16编辑过]

----------------解决方案--------------------------------------------------------

Factorial

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 2864 Accepted Submit: 1141

--------------------------------------------------------------------------------
The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.
ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.

For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1<N2, then Z(N1) <= Z(N2). It is because we can never "lose" any trailing zero by multiplying by any positive number. We can only get new and new zeros. The function Z is very interesting, so we need a computer program that can determine its value efficiently.

Input

There is a single positive integer T on the first line of input. It stands for the number of numbers to follow. Then there is T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.

Output

For every number N, output a single line containing the single non-negative integer Z(N).

Sample Input

6
3
60
100
1024
23456
8735373

Sample Output

0
14
24
253
5861
2183837

做n!0的个数.

----------------解决方案--------------------------------------------------------
http://acm.zju.edu.cn/show_problem.php?pid=2022
上面的,有兴趣的自己提交一下.
----------------解决方案--------------------------------------------------------
大家可以用这个测试公共ID,请大家不要改.呵呵.
帐号:bchzhgACM
密码:nuciewth


----------------解决方案--------------------------------------------------------

昨天晚上想出来的的.感觉还是没有Eastsun的思路强.看来我DP还是没有学会

#include<stdio.h>
#include<stdlib.h>//for bsearch
int cmp(const void *n,const void *m)
{
return *(int *)n-*(int *)m;
}
long a[11];
long b[639];
void init()
{
int i,j,k,flag;
for(i=2,a[0]=a[1]=1;a[i-1]*i<=1000000;a[i]=a[i-1]*i,i++);
for(i=1,flag=0;i<520&&flag<639;i++)
{
b[flag]=0;
for(j=i,k=1;j;k++)
{
b[flag]+=(j%2)*a[k];
j/=2;
}
if(b[flag]!=b[flag-1]) flag++;
b[flag]=b[flag-1]+1;
flag++;
}
}
int main()
{
init();
int i;
long *k;
long n;
while(scanf("%ld",&n)&&n>=0)
{
k=(long *)bsearch(&n,b,639,sizeof(long),cmp);
if(!k) printf("NO\n");
else
printf("YES\n");

}
return 0;
}

继续研究一下Eastsun的思路

[此贴子已经被作者于2007-5-30 12:50:30编辑过]

----------------解决方案--------------------------------------------------------
怎么没人做丫,把第三题也贴出来吧,第二题偶就不贴出来了,留给其他人,呵呵:

----------------解决方案--------------------------------------------------------