您所在位置：主题：help!tju1164超时1s
大蟹
[专家分：50] 发布于 2005-10-09 22:01:00
Peach - 猴子分桃
Time Limit:2s Memory Limit:65536k
Total Submit:1558 Accepted:150
--------------------------------------------------------------------------------
Problem
现在有一堆桃子，N只猴子要平均分这些桃子。第一只猴子来了，它等了很久，其他猴子都不来，于是它把桃子平均分成了N堆，最后余下一个桃子，它觉得自己分桃辛苦了，于是就把那个多余的桃子吃掉了，结果是，这只猴子吃掉了一个桃子，又从中拿走了N堆中的一堆。接着第二只猴子来了，它并不知道先前已经来过一只。它想，N只猴子怎么分N-1堆桃子呢？于是它把所有桃子合在一起，重新分成N堆，又剩下一只，它吃了剩的桃子，又拿了一堆桃子……以后几只猴子也是这么做的。问原来至少有多少桃子？最后至少剩多少桃子？
Input
本题有多组测试数据。每组数据包括一个整数N(3 <= N <= 1000)，代表猴子的个数。
Output
对于每组数据，输出一行两个数字：原来桃子的个数和剩下桃子的个数，两个数字之间用空格分开。
Sample Input
3
Sample Output
25 6
Source
1st Anniversary of TOJ Day1
我的程序:
program p1164;
const h=1000;
maxl=1001;
var ans1:array[1..maxl] of integer;
ans2:array[1..maxl] of integer;
i,j:integer;
n:integer;
procedure work;
var i,j:integer;
k1,k2:longint;
begin
fillchar(ans2,sizeof(ans2),0);
fillchar(ans1,sizeof(ans1),0);
ans2[maxl]:=1;
ans1[maxl]:=1;
for i:=1 to n do
begin
k1:=0;k2:=0;
for j:=maxl downto 1 do
begin
k1:=n*ans1[j]+k1;
k2:=(n-1)*ans2[j]+k2;
ans1[j]:=k1 mod h;
ans2[j]:=k2 mod h;
k1:=k1 div h;
k2:=k2 div h;
end;
end;
ans1[maxl]:=ans1[maxl]-n+1;
ans2[maxl]:=ans2[maxl]-n+1;
j:=maxl;
while ans1[j]<0 do begin dec(ans1[j-1]);ans1[j]:=ans1[j]+h;dec(j); end;
j:=1;
while ans1[j]=0 do inc(j);
write(ans1[j]);
for i:=j+1 to maxl do
write(ans1[i] div 100,ans1[i] div 10 mod 10,ans1[i] mod 10);
write(' ');
j:=maxl;
while ans2[j]<0 do begin dec(ans2[j-1]);ans2[j]:=ans2[j]+h;dec(j); end;
j:=1;
while ans2[j]=0 do inc(j);
write(ans2[j]);
for i:=j+1 to maxl do
write(ans2[i] div 100,ans2[i] div 10 mod 10,ans2[i] mod 10);
writeln;
end;
begin
repeat
read(n);
work;
until seekeof;
end.
在tju测试中时间3000ms,请各位大侠帮忙修改修改
Time Limit:2s Memory Limit:65536k
Total Submit:1558 Accepted:150
--------------------------------------------------------------------------------
Problem
现在有一堆桃子，N只猴子要平均分这些桃子。第一只猴子来了，它等了很久，其他猴子都不来，于是它把桃子平均分成了N堆，最后余下一个桃子，它觉得自己分桃辛苦了，于是就把那个多余的桃子吃掉了，结果是，这只猴子吃掉了一个桃子，又从中拿走了N堆中的一堆。接着第二只猴子来了，它并不知道先前已经来过一只。它想，N只猴子怎么分N-1堆桃子呢？于是它把所有桃子合在一起，重新分成N堆，又剩下一只，它吃了剩的桃子，又拿了一堆桃子……以后几只猴子也是这么做的。问原来至少有多少桃子？最后至少剩多少桃子？
Input
本题有多组测试数据。每组数据包括一个整数N(3 <= N <= 1000)，代表猴子的个数。
Output
对于每组数据，输出一行两个数字：原来桃子的个数和剩下桃子的个数，两个数字之间用空格分开。
Sample Input
3
Sample Output
25 6
Source
1st Anniversary of TOJ Day1
我的程序:
program p1164;
const h=1000;
maxl=1001;
var ans1:array[1..maxl] of integer;
ans2:array[1..maxl] of integer;
i,j:integer;
n:integer;
procedure work;
var i,j:integer;
k1,k2:longint;
begin
fillchar(ans2,sizeof(ans2),0);
fillchar(ans1,sizeof(ans1),0);
ans2[maxl]:=1;
ans1[maxl]:=1;
for i:=1 to n do
begin
k1:=0;k2:=0;
for j:=maxl downto 1 do
begin
k1:=n*ans1[j]+k1;
k2:=(n-1)*ans2[j]+k2;
ans1[j]:=k1 mod h;
ans2[j]:=k2 mod h;
k1:=k1 div h;
k2:=k2 div h;
end;
end;
ans1[maxl]:=ans1[maxl]-n+1;
ans2[maxl]:=ans2[maxl]-n+1;
j:=maxl;
while ans1[j]<0 do begin dec(ans1[j-1]);ans1[j]:=ans1[j]+h;dec(j); end;
j:=1;
while ans1[j]=0 do inc(j);
write(ans1[j]);
for i:=j+1 to maxl do
write(ans1[i] div 100,ans1[i] div 10 mod 10,ans1[i] mod 10);
write(' ');
j:=maxl;
while ans2[j]<0 do begin dec(ans2[j-1]);ans2[j]:=ans2[j]+h;dec(j); end;
j:=1;
while ans2[j]=0 do inc(j);
write(ans2[j]);
for i:=j+1 to maxl do
write(ans2[i] div 100,ans2[i] div 10 mod 10,ans2[i] mod 10);
writeln;
end;
begin
repeat
read(n);
work;
until seekeof;
end.
在tju测试中时间3000ms,请各位大侠帮忙修改修改
