Page 4 of 4
Posted: Mon Jan 07, 2008 5:29 am
Is this the right formula f(n)=2*f(n-1) where f(1)=1?

Posted: Thu Feb 21, 2008 1:00 am
Sedefcho wrote:Oh, sorry for that stupid remark of mine.
I see now, 10 is just the number of test cases to follow.

By the way I also have a BigInt custom class but currently
it does support division. And so I can not use it.

I mean that as the formula is :

Code: Select all

``````F(N) = ( N * (N-1) * (N*N-5*N+18) / 24 ) + 1
``````
we should be able to divide by 24 once we generate the BigInt
value

Code: Select all

``N * (N-1) * (N*N-5*N+18) ``

Should I necessarily implement division in my BigInt or is
that some tricky workaround letting me get away without
doing division of 24 at the end of the computation ?

What do you think about that ?
thx for giving me the formula. I got AC.
I also have something for you.

this code is +,-,*,/ for super big number.
in div_string(), if u want to know remainder, u can returns s_remainder.

Code: Select all

``````inline int compare_string(string s1, string s2)
{
if(s1.length()<s2.length())
return -1;
else if(s1.length()>s2.length())
return 1;
else
{
for(int i=0; i<s1.length(); ++i)
{
if(s1[i]<s2[i])
return -1;
else if(s1[i]>s2[i])
return 1;
}
}

return 0;
}

inline string sub_string(string s1, string s2)
{
int i;
string s;
bool positive=true;

if(compare_string(s1,s2)<0)
{
positive=false;
s1.swap(s2);
}

s2.insert(0,s1.length()-s2.length(),'0');

//s1 - s2
for(i=s1.length()-1; i>=0; --i)
if(s1[i]>=s2[i])
s.insert(0,1,s1[i]-s2[i]+'0');
else
{
s.insert(0,1,s1[i]-s2[i]+10+'0');
s1[i-1]-=1;
}

//trim
for(i=0; s[i]=='0'; ++i);
s=s.substr(i);

if(!s.length())
s="0";

//negative
if(!positive)
s.insert(0,1,'-');

return s;
}

inline string add_string(string s1, string s2)
{
int c=0,d;
string s;
int i,j;

for(i=s1.length()-1, j=s2.length()-1;
(s1.length()>=s2.length())?j>=0:i>=0; --i, --j)
{
d=(s1[i]-'0')+(s2[j]-'0')+c;
if(d>=10)
s.insert(0,1,(d-10)+'0');
else
s.insert(0,1,d+'0');
c=d/10;
}
if(s1.length()>s2.length())
{
while(i>=0)
{
d=(s1[i]-'0')+c;
if(d>=10)
s.insert(0,1,(d-10)+'0');
else
s.insert(0,1,d+'0');
c=d/10;
--i;
}
if(c>0)
s.insert(0,1,c+'0');
}
else if(s1.length()<s2.length())
{
while(j>=0)
{
d=(s2[j]-'0')+c;
if(d>=10)
s.insert(0,1,(d-10)+'0');
else
s.insert(0,1,d+'0');
c=d/10;
--j;
}
if(c>0)
s.insert(0,1,c+'0');
}
else
{
if(c>0)
s.insert(0,1,c+'0');
}

return s;
}

inline string mul_string(string s1, string s2)
{
int i,j;
int c=0,d;
string s;
vector<string> vs;

vs.clear();
for(j=s2.length()-1; j>=0; --j)
{
for(i=s1.length()-1; i>=0; --i)
{
d=(s2[j]-'0')*(s1[i]-'0')+c;
c=d/10;
d%=10;
s.insert(0,1,d+'0');
}

if(c>0)
{
s.insert(0,1,c+'0');
c=0;
}

for(i=0; i<s2.length()-1-j; ++i)
s.append("0");

vs.push_back(s);
s.clear();
}

s=vs[0];

for(i=1; i<vs.size(); ++i)

return s;
}

inline string div_string(string s1, string s2)
{
string s,s_dividend,s_remainder;
int i,j,d;

if(!compare_string(s2,"0"))
cout<<"divisor is 0!!"<<endl;
else if(!compare_string(s2,"1"))
{
s=s1;
s_remainder="0";
}
else if(!compare_string(s1,s2))
{
s="1";
s_remainder="0";
}
else if(compare_string(s1,s2)<0)
{
s="0";
s_remainder=s1;
}
else
{
for(i=0; i<s1.length();)
{
s_dividend.append(1,s1[i]);

//trim
for(j=0; s_dividend[j]=='0'; ++j);
s_dividend=s_dividend.substr(j);

if(!s_dividend.length())
s_dividend="0";

if(compare_string(s_dividend,s2)<0)
{
s.append("0");
s_remainder=s_dividend;
}
else if(!compare_string(s_dividend,s2))
{
s.append("1");
s_remainder="0";
s_dividend.clear();
}
else
{
d=0;
while(compare_string(s_dividend,s2)>=0)
{
s_dividend=sub_string(s_dividend,s2);
++d;
}
s.append(1,d+'0');
s_remainder=s_dividend;
}
++i;
}

//trim
for(i=0; s[i]=='0'; ++i);
s=s.substr(i);

if(!s.length())
s="0";

for(i=0; s_remainder[i]=='0'; ++i);
s_remainder=s_remainder.substr(i);

if(!s_remainder.length())
s_remainder="0";

return s;
}
}
``````

### Re: 10213 need answers to test cases

Posted: Wed May 07, 2008 4:47 am
Martin Macko wrote:
898989 wrote:

Code: Select all

``````0
1
5
7
10
100
10000
124
21533
456
79888
1048576
2147483647
``````
My AC's output:

Code: Select all

``````1
1
16
57
256
3926176
416416762492501
9388878
8955419035380574
1778051731
1697001927971339669
50371620921287095091201
886151993063477126682488902248300547``````
Thanks for your test data, I got AC last.

### Re: 10213 - How many pieces of land?

Posted: Sun Sep 21, 2008 12:48 am
I got AC using the Combinatorics equation but i don't understand why does it works.

F(n) = 1+ number of lines + number of intersections

What's the idea behind it? How is that sumation directly involved with the areas produced?

Thanks.

### Re: 10213 - How many pieces of land?

Posted: Wed May 11, 2011 12:10 pm
Here is my code. But I don't understand why I am getting WA. I have matched many test cases, but the outputs were same.

Code: Select all

``````#include <stdio.h>
#include <math.h>
int main()
{
int t,i;
long long n,m;
scanf("%d",&t);
for (i = 0; i < t; i++)
{
scanf("%lld",&n);
m=(n*(n-1)*(n*n-5*n+18)/24)+1;
printf("%lld\n",m);
}

return 0;

}

``````

### 100213

Posted: Sat May 14, 2011 12:06 pm
I have got WA in this code. But the output is not different I think.

Code: Select all

``````#include <stdio.h>
#include <math.h>
int main()
{
int t,i;
long long n,m;
scanf("%d",&t);
for (i = 0; i < t; i++)
{
scanf("%lld",&n);
m=(n*(n-1)*(n*n-5*n+18)/24)+1;
printf("%lld\n",m);
}``````

### Re: 10213 - How many pieces of land?

Posted: Mon Jul 22, 2013 3:46 pm
Any one help? I've tried all tests here but still WA
My code: (Updated)

Code: Select all

``````{\$mode objfpc}
uses math;
type
bignum=record
size: longint;
a: array[0..1000] of qword;
end;
var
base: longint=1000000000;
ans: array[0..4] of longint=(1,1,2,4,8);
t,tt,n: longint;
one: bignum;

operator :=(x: qword): bignum;
begin
fillchar(result.a,sizeof(result.a),0); result.size:=0;
repeat
inc(result.size); result.a[result.size]:=x mod base; x:=x div base;
until x=0;
end;

operator +(x,y: bignum): bignum;
var
i: longint;
tmp: qword;
begin
result.size:=max(x.size,y.size); tmp:=0;
for i:=1 to result.size do
begin
inc(tmp,x.a[i]+y.a[i]); result.a[i]:=tmp mod base; tmp:=tmp div base;
end;
if tmp>0 then
begin
inc(result.size); result.a[result.size]:=tmp;
end;
end;

operator *(x: bignum; y: qword): bignum;
var
i: longint;
tmp: qword;
begin
result.size:=x.size; tmp:=0;
for i:=1 to x.size do
begin
inc(tmp,x.a[i]*y); result.a[i]:=tmp mod base; tmp:=tmp div base;
end;
if tmp>0 then
begin
inc(result.size); result.a[result.size]:=tmp;
end;
end;

function c(n,k: longint): bignum;
var
i,j: longint;
a: array[0..5] of longint;
begin
for i:=1 to k do a[i]:=n-k+i;
for i:=k downto 1 do
for j:=k downto 1 do
if a[j] mod i=0 then
begin
a[j]:=a[j] div i; break;
end;
result:=a[1];
for i:=2 to k do result:=result*a[i];
end;

var
s,tmp: ansistring;
i: longint;
begin
s:='';
for i:=1 to x.size do
begin
str(x.a[i],tmp);
while (i<x.size) and (length(tmp)<9) do tmp:='0'+tmp;
s:=tmp+s;
end;
writeln(s);
end;

begin
//  assign(input,'chip.in'); reset(input); assign(output,''); rewrite(output);
for tt:=1 to t do
begin
if n<5 then writeln(ans[n]) else answer(c(n,2)+c(n,4)+one);
end;
//  close(input); close(output);
end.
``````

### Re: 10213 - How many pieces of land?

Posted: Thu Jul 25, 2013 12:06 am

Code: Select all

``````1
2115115464``````
AC output:

Code: Select all

``833921323402617589467244223246289043``

### Re: 10213 - How many pieces of land?

Posted: Thu Jul 25, 2013 8:57 am
Thank you very much, brianfry, I've detected a bug in my bignum code.
But still WA, anyway
I've updated my code, are there any other test cases?

### Re: 10213 - How many pieces of land?

Posted: Wed Jul 31, 2013 2:56 am
I checked some random input and didn't see any differences between your pascal code and my AC C code.