既然出简单出难都没有人做就出难点的吧，这是最近TJU比赛的题目中过的人数最多的四道中过的人数最少的两道，注意我就是这个意思，没有表达错误，不过毫不客气的说对初学者仍然颇有难度。
这是当时比赛的情况，下面两题分别为题目F和题目H，可以看到这两题是被提交次数最多的两题，但通过人数确不是最多，而通过率几乎是最低的两道。
http://acm.tju.edu.cn/toj/contest/stat71
http://acm.tju.edu.cn/toj/showp2845
Factorial
--------------------------------------------------------------------------------
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 53 Accepted Runs: 25
--------------------------------------------------------------------------------
Robby is a clever boy, he can do multiplication very quickly, even in base-2 (binary system), base-16 (hexadecimal system) or base-100000.
Now he wants to challenge your computer, the task is quite simple: Given a positive integer N, if we express the N ! (N ! = N * (N - 1) * (N - 2) * ... * 2 * 1) in base-B, how many ZEROs there will be at the end of the number. Can you make a wonderful program to beat him?
Input
Each test case contain one line with two numbers N and B. (1 ≤ N ≤ 10^9, 2 ≤ B ≤ 100000)
The input is terminated with N = B = 0.
Output
Output one line for each test case, indicating the number of ZEROs.
Sample Input
7 10
7 10000
7 2
0 0
Sample Output
1
0
4
Hint
7! = (5040)10, so there will be one zero at the end in base-10. But in base-10000, the number (5040)10 can be expressed in one non-zero digit, so the second answer is 0. In base-2, 7! = (1001110110000)2, so the third answer is 4.
Problem Setter: RoBa
翻译：给定N 和 B两个数. (其中1 ≤ N ≤ 10^9, 2 ≤ B ≤ 100000)
计算N阶乘在B进制下的尾数0的个数。(给定的N的形式总是视为10进制意义下的)
例如 5 10
5!=5*4*3*2*1=120在十进制下尾数0的个数为1
再如 7 2
7!=5040(十进制)=1001110110000(二进制)，所以在2进制意义下7!尾数0的个数为4
http://acm.tju.edu.cn/toj/showp2847
How Far Can We Go
--------------------------------------------------------------------------------
Time Limit: 10.0 Seconds Memory Limit: 65536K Special Judge
Total Runs: 61 Accepted Runs: 23
--------------------------------------------------------------------------------
Robby is a bad-tempered child, and he often quarrels or even fights with others. After the quarrelling, he often shouts to his opponent: "Go away from me, as far as possible! I never want to see you again!"
When he calms down, he finds that it is an interesting problem in fact: Given the position of all the cities, what's the maximum distance between any pairs of them?
Input
The first line of each test case contain an integer N (2 ≤ N ≤ 100000), indicating the number of cities. Then N lines followed, each line contains two numbers Xi and Yi, indicating there is a city at (Xi, Yi). (|Xi|, |Yi| ≤ 10^7)
The input is terminated with N = 0.
Output
Output one number in one line for each test case, indicating the maximum distance. Two digits after decimal point are preserved by rounding.
Sample Input
4
0.0 0.0
-1.0 -1.0
0.0 -1.0
-1.0 0.0
0
Sample Output
1.41
Problem Setter: RoBa
Note: Special judge problem, you may get "Wrong Answer" when output in wrong format.
翻译：求给定点集中的最远点对的距离。
例如
4 //表示点集中点的个数
0.0 0.0 //(0.0,0.0)
-1.0 -1.0
0.0 -1.0
-1.0 0.0
其中(0.0,0.0)到(-1.0,-1.0)和(0.0,-1.0)到(-1.0,0.0)的距离均为最远距离"根号2"，所以答案是1.41(四舍五入保留2位小数)
提示：最远点对的NlogN算法是首先求出凸包，然后沿着凸包O(N)的寻找所谓“对面点”，取其中距离最大的点对即可。
这题我自己也没做，我没写过凸包算法，手上也没几何库，希望看到解答，顺便让我收了您的凸包代码
[此贴子已经被作者于2007-6-16 0:25:42编辑过]
----------------解决方案--------------------------------------------------------
第一个问提不会是把所有的N对应的所有的B进制都输出吧`````
----------------解决方案--------------------------------------------------------
熬夜熬晕了,改了一堆bug终于把第一题写出来了,第二题好象简单些,下午在来写.
第一题:
#include <stdio.h>
#include <malloc.h>
int main(void)
{
int i,j,N,B,count,temp,success,array[100000],*ptr;
while(1){
count=0;
scanf("\n %d %d",&N,&B);
if(!(N||B))
return 0;
temp=B;
ptr=(int *)malloc(sizeof(int)*N);
for(i=0;i<N;i++)
ptr[i]=i+1;
i=0; j=2;
while(temp!=1)
{
if(temp%j)
j++;
else
{
array[i++]=j;
temp/=j;
}
}
array[i]=0;
while(1)
{
success=0;
for(i=0;array[i]&&j!=N;i++)
{
for(j=1;j<N;j++)
{
if(ptr[j]%array[i])
continue;
if(!array[i+1])
success=1;
ptr[j]/=array[i];
break;
}
}
if(success)
{count++;success=0;}
else
{printf("%d\n",count);break;}
}
}
}
----------------解决方案--------------------------------------------------------
睡不着,起来接着再编一个,第二题:
#include<stdio.h>
#include<malloc.h>
#include<math.h>
typedef struct{
double x,y,distance;
}CITY,*pCITY;
int main()
{
int nSize,i,j;
pCITY CityList;
double *array,temp;
while(1){
scanf("%d",&nSize);
if(!nSize)
return 0;
CityList=(pCITY)malloc(sizeof(CITY)*nSize);
array=(double *)malloc(sizeof(double)*(nSize-1));
for(i=0;i<nSize;i++)
scanf("%lf %lf",&CityList[i].x,&CityList[i].y);
for(i=0;i<nSize;i++)
for(j=0,CityList[i].distance=0;j<nSize;j++)
{
if(i==j)
continue;
temp=CityList[i].x * CityList[i].x + CityList[j].y *CityList[j].y;
if(temp>CityList[i].distance)
CityList[i].distance=temp;
}
for(i=1,temp=CityList[0].distance;i<nSize;i++)
{
if(temp<CityList[i].distance)
temp=CityList[i].distance;
}
temp=sqrt(temp);
printf("%lf",temp);
}
}
----------------解决方案--------------------------------------------------------
楼上的能过么?貌似时间复杂度是O(N^2)
----------------解决方案--------------------------------------------------------
第一题:
| Time:0:00.00 | Memory:604K |
#include<stdio.h>
int main(){
int n,b,p,k,c,t,min;
for(;scanf(\"%d%d\",&n,&b),n|b;){
p =2;
c =0;
min =100000000;
for(;;)
if(b%p||b==1){
if(!c){
p++;
continue;
}
t =0;
for(k=n;k/=p;t+=k);
t /=c;
if(min>t) min =t;
p++;
c=0;
if(b==1) break;
}
else{
c++;
b/=p;
}
printf(\"%d\n\",min);
}
return 0;
}
第二题:
TMMD,这题把我搞晕了,老是WA,后来把float改成double就AC了,ft!
还好,把第一拿下了
#include<stdio.h>
#include<math.h>
#include <algorithm>
#include <functional>
#define S(arr,a,b,c) ((arr[b].x-arr[a].x)*(arr[c].y-arr[b].y)-(arr[c].x-arr[b].x)*(arr[b].y-arr[a].y))
#define J(arr,a,b,c,d) ((arr[b].x-arr[a].x)*(arr[d].y-arr[c].y)-(arr[d].x-arr[c].x)*(arr[b].y-arr[a].y))
#define Q(x) ((x)*(x))
#define D(arr,a,b) (Q(arr[a].x-arr[b].x)+Q(arr[a].y-arr[b].y))
using namespace std;
struct Point{
double x,y;
};
struct myCmp:public binary_function<Point,Point,bool>{
bool operator()(const Point& p1,const Point& p2)const{
if(p1.x==p2.x) return p1.y<=p2.y;
else return p1.x<p2.x;
}
};
int main(){
int n;
while(scanf(\"%d\",&n),n){
Point *ps =new Point[n];
for(int i=0;i<n;i++) scanf(\"%lf%lf\",&ps[i].x,&ps[i].y);
sort(ps,ps+n,myCmp());
int *v =new int[2*n];
int p,q;
p =q =n;
for(int i=0;i<n;i++){
v[p] =v[q] =i;
while(p-n>=2&&S(ps,v[p],v[p-1],v[p-2])>=0){v[p-1] =v[p]; p--;}
while(n-q>=2&&S(ps,v[q+2],v[q+1],v[q])>=0){v[q+1] =v[q]; q++;}
p++;
q--;
}
Point *pps =new Point[n+2];
for(int i=q+1;i<p;i++) pps[i-q] =ps[v[i]];
pps[0] =pps[n];
int i=0,j=1;
while(J(pps,i,i+1,j,j+1)>0) j++;
double max =0;
while(i<=n){
double det =J(pps,i,i+1,j,j+1);
if(det<=0) i++;
else if(det>0) j =(j+1>n?j+1-n:j+1);
double tmp =D(pps,i,j);
if(tmp>max) max =tmp;
}
delete[] ps;
delete[] pps;
delete[] v;
printf(\"%.2lf\n\",sqrt(max));
}
return 0;
}
[此贴子已经被作者于2007-6-16 21:21:56编辑过]
----------------解决方案--------------------------------------------------------
第一题：
#include <stdio.h>
void main()
{
long int N, B, factorial;
int count;
while(1)
{
count = 0;
factorial = 1;
printf( "Please input the value of N:" );
scanf( "%d", &N );
printf( "Please input the value of B:" );
scanf( "%d", &B );
if( N == 0 && B == 0 )
return ;
else if( ( N < 1 || N > 1000000000 ) || ( B < 2 || B > 100000 ) )
{
printf( "Input error.Please try again!\n" );
continue;
}
else
{
if( N == 1 )
{
printf( "There is %d ZERO at the end of number!\n", count );
continue;
}
else
{
while( N >= 2 )
{
factorial *= N;
N--;
}
while( factorial % B == 0 )
{
count++;
factorial /= B;
}
printf( "There are %d ZEROs at the end of number!\n", count );
}
}
}
}
[此贴子已经被作者于2007-6-16 14:37:39编辑过]
----------------解决方案--------------------------------------------------------
----------------解决方案--------------------------------------------------------
#include<stdio.h>
int fac(int n)
{int f;
if(n==0)
f=1;
else
f=n*fac(n-1);
return f;
}
main()
{ int f,b[10],count=0,i=0,j=0,counte=0,n,m,t;
printf("input n"); scanf("%d",&n);
printf("input jin zhi"); scanf("%d",&m);
f=fac(n);
printf("%d\n",f);
while(f!=0&&f!=1)
{ b[i]=f%m;f=f/m;i++;count++;
}
b[i]=f;
for(i=0;i<=count;i++)
{ printf("%d",b[i]);
if(b[i]==0) counte++;
}
printf("\n%d",counte) ;
getch();
}
----------------解决方案--------------------------------------------------------
第一题：还是有太多BUG，好象没必要计算那么大进制吧，到后面基本上就都没有0存在。好象很没效。
#include"stdio.h"
void jinzhi(void)
{
int a,b,i,m=0;
unsigned long long N=1;
int nextdigit;
printf("Enter your number:");
scanf("%i",&a);
N=N*a;
for (i=1;i<a;++i)
N=N*(a-i);
printf("%li\n",N);
printf("shuru yao zhuan huan de jishu:0<b<16!");
scanf("%i",&b);
while(b<2||b>1000000){
printf("shuru The b<=2||b<=1000000:");
scanf("%i",&b);}
while(N%b==0&&N!=0){
m++;
N=N/b;}
printf("\n");
printf("%i",m);
}
int main(void)
{
void jinzhi(void);
jinzhi();
getch();
return 0;
}
----------------解决方案--------------------------------------------------------