10213 - How Many Pieces of Land ?

[Codemonkey2000]

Is this the right formula f(n)=2*f(n-1) where f(1)=1?

[deadangelx]

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);
  }
  
  //add leading zero
  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)
    s=add_string(s,vs[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;
  }
}

[WXuan]

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.

[Juanito]

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.

[masum93]

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;
	
}

[masum93]

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);
   }

[chipchip3412]

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;

procedure answer(x: bignum);
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);
  read(t); one:=1;
  for tt:=1 to t do
  begin
    read(n);
    if n<5 then writeln(ans[n]) else answer(c(n,2)+c(n,4)+one);
  end;
//  close(input); close(output);
end.

[brianfry713]

Code: Select all

1
2115115464

AC output:

Code: Select all

833921323402617589467244223246289043

[chipchip3412]

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?

[brianfry713]

I checked some random input and didn't see any differences between your pascal code and my AC C code.