Euler Projesi 224. Soru

Hemen Hemen Dik Üçgenler II

Kenar uzunlukları tam sayılar olan bir üçgen için $a \le b \le c$ olsun. Eğer $a^2+b^2=c^2-1$ eşitliği sağlanıyorsa bu üçgene hemen hemen geniş açılı denir.

Çevre $\le 75000000$ şartını sağlayan kaç adet hemen hemen geniş açılı üçgen vardır?
Cevap: 4137330

Java:

 private static final int N=75000000;
    private static class Node
    { 
        Node alloc(int, Node){...}
        void free(Node){...}
        int d;
        Node next;
    }

    public static void main( String[] args )
    {
        int cnt = 0;
        Node[] B = new Node[N/2+2];
        B[1] = Node.alloc(1, null);
        for ( int i=1; i<B.length; ++i ) {
            long I = (long)i*i+1;
            for ( Node node=B[i]; node != null; node=node.next ) {
                int L = node.d;
                long K = I/L;
                if ( i+L < B.length ) {
                    B[i+L] = Node.alloc( L, B[i+L] );
                }
                if ( i+K < B.length ) {
                    B[i+(int)K] = Node.alloc( (int)K, B[i+(int)K] );
                }
                if ( (K-L)%2==0 && K-L>=2*i && K+i <= N ) {
                    cnt += 1;
                }
            }
            Node.free( B[i] );
        }
        System.out.println( "Result: "+cnt );
    }

C++:

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <ctime>
#include <cmath>
#include <set>
#include <map>

using namespace std;

struct triple {
  int x,y,z;  
  triple():x(0),y(0),z(0){}
  triple(int ix, int iy, int iz):x(ix),y(iy),z(iz){
    if (y>z) swap(y,z);
    if (x>y) swap(x,y);
    if (y>z) swap(y,z);
  }
  triple(const triple &i):x(i.x),y(i.y),z(i.z){}
};

bool operator==(const triple &i1, const triple &i2) {
  return i1.x==i2.x && i1.y==i2.y && i1.z==i2.z;
}

bool operator<(const triple &i1, const triple &i2) {
  return (i1.x<i2.x) || (i1.x==i2.x && i1.y<i2.y) || (i1.x==i2.x && i1.y==i2.y && i1.z<i2.z);
}

const long long int N=6124;
const long long int NN=75000000;
set<triple> ss;

void checkadd(long long int a, long long int b, long long int c, long long int d){

  if (b*b+c*c!=d*d-1 || a!=1){
    cout<<"ERROR:"<<a<<","<<b<<","<<c<<","<<d<<endl;
    system("PAUSE");
  }/* else cout<<a<<","<<b<<","<<c<<","<<d<<endl;*/

  b=abs(b); c=abs(c); d=abs(d);
  if (b==0 || c==0 || d==0 || b+c+d>NN || d+b<=c || d+c<=b || b+c<=d) return;

  triple t(b,c,d);
  ss.insert(t);
}

int main(int argc, char *argv[])
{
  clock_t start,finish;
  double time;
  start = clock();    

  set<int> s;
  multimap< int,pair<int,int> > mm;
  for(int i=0;i<=N;i++){  
    if (i%100==0) cout<<i<<endl;
    for(int o=i;o<=N;o++){  
      if (2*i*i+2*o*o-1<=NN) s.insert(i*i+o*o);
    }
  }
  cout<<s.size()<<endl;

  for(int i=0;i<=N;i++){  
    if (i%100==0) cout<<i<<endl;
    for(int o=i;o<=N;o++){  
      if (2*i*i+2*o*o-1<=NN && s.find(i*i+o*o+1)!=s.end()) {
        mm.insert(pair<int,pair<int,int> >(i*i+o*o+1,pair<int,int>(i,o)));
      }
    }
  }
  cout<<mm.size()<<endl;
/*   
  int nr=0;
  for(multimap< int,pair<int,int> >::iterator it=m.begin();it!=m.end() && nr<5000;it++,nr++){
    cout<<it->first<<": "<<it->second.first<<","<<it->second.second<<endl;
  }
*/

  for(long long int m=-N;m<=N;m++) {
//  for(long long int m=0;m<=N;m++) {
    if (abs(m)%100==0) cout<<m<<" ("<<ss.size()<<")"<<endl;
//    int B=(NN+1)/2-m*m;
    long long int B=NN-m*m;
    if (B<0) B=0; else B=sqrt(B)+1;
    for(long long int n=-B;n<=B;n++) {
      multimap< int,pair<int,int> >::iterator it;
      pair<multimap< int,pair<int,int> >::iterator,multimap< int,pair<int,int> >::iterator> mp;
      mp=mm.equal_range(m*m+n*n);
      for(it=mp.first;it!=mp.second;it++){
        long long int p;      
        long long int q;      

        p=it->second.first;      
        q=it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          if (b>0 && c>0 && d>0 && b+c+d<=NN) {
            checkadd(a,b,c,d);
          }
        }
        q=it->second.first;      
        p=it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          checkadd(a,b,c,d);
        }

        p=-it->second.first;      
        q=it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          checkadd(a,b,c,d);
        }
        q=-it->second.first;      
        p=it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          checkadd(a,b,c,d);
        }

        p=it->second.first;      
        q=-it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          checkadd(a,b,c,d);
        }
        q=it->second.first;      
        p=-it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          checkadd(a,b,c,d);
        }

        p=-it->second.first;      
        q=-it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          checkadd(a,b,c,d);
        }
        q=-it->second.first;      
        p=-it->second.second;      
        if (p<q) {
          long long int a=m*m+n*n-p*p-q*q;
          long long int b=2*(m*p+n*q);
          long long int c=2*(n*p-m*q);
          long long int d=m*m+n*n+p*p+q*q;
          checkadd(a,b,c,d);
        }       

      }
    }
  }

  cout<<"Res.:"<<ss.size()<<endl;

  finish = clock();
  time = (double(finish)-double(start))/CLOCKS_PER_SEC;  
  cout<<"Time:"<<time<<endl;
  
  ofstream f("res.txt");
  f<<"Res.:"<<ss.size()<<endl;
  int nr=0;
  for(set<triple>::iterator it=ss.begin();it!=ss.end();it++){
    f<<++nr<<":"<<it->x<<","<<it->y<<","<<it->z<<" ("<<it->x+it->y+it->z<<")"<<endl;
  }
  f.close();

  system("PAUSE");
  return EXIT_SUCCESS;
}

Pascal:

program roxor;
uses minimaple;

type tri=array[1..3] of longint;

var t1,t2: array[1..50000000] of tri;
    taille1,taille2:longint;

function compte(max:longint):longint;
var i,a,b,c,lim,som:longint;
begin
   som:=1;
   taille1:=1;
   taille2:=0;
   t1[1][1]:=2;
   t1[1][2]:=2;
   t1[1][3]:=3;
   while taille1<>0 do
   begin
      lim:=taille1;
   taille1:=0;
      for i:=1 to lim do
      begin
      a:=t1[i][1];
   b:=t1[i][2];
   c:=t1[i][3];
   if a-2*b+2*c+2*a-b+2*c+2*a-2*b+3*c<=max then
   begin
     taille2:=taille2+1;
     t2[taille2][1]:=a-2*b+2*c;
     t2[taille2][2]:=2*a-b+2*c;
     t2[taille2][3]:=2*a-2*b+3*c;
     som:=som+1;
  end;
  if a+2*b+2*c+2*a+b+2*c+2*a+2*b+3*c<= max then
  begin
     taille2:=taille2+1;
     t2[taille2][1]:=a+2*b+2*c;
     t2[taille2][2]:=2*a+b+2*c;
     t2[taille2][3]:=2*a+2*b+3*c;
     som:=som+1;
  end;
  if a<>b then
  if -a+2*b+2*c-2*a+b+2*c-2*a+2*b+3*c<=max then
  begin
    taille2:=taille2+1;
    t2[taille2][1]:=-a+2*b+2*c;
    t2[taille2][2]:=-2*a+b+2*c;
    t2[taille2][3]:=-2*a+2*b+3*c;
    som:=som+1;
  end;
  end;
   lim:=taille2;
   taille2:=0;
      for i:=1 to lim do
      begin
      a:=t2[i][1];
   b:=t2[i][2];
   c:=t2[i][3];
   if a-2*b+2*c+2*a-b+2*c+2*a-2*b+3*c<=max then
   begin
     taille1:=taille1+1;
     t1[taille1][1]:=a-2*b+2*c;
     t1[taille1][2]:=2*a-b+2*c;
     t1[taille1][3]:=2*a-2*b+3*c;
     som:=som+1;
  end;
  if a+2*b+2*c+2*a+b+2*c+2*a+2*b+3*c<= max then
  begin
     taille1:=taille1+1;
     t1[taille1][1]:=a+2*b+2*c;
     t1[taille1][2]:=2*a+b+2*c;
     t1[taille1][3]:=2*a+2*b+3*c;
     som:=som+1;
  end;
  if a<>b then
  if -a+2*b+2*c-2*a+b+2*c-2*a+2*b+3*c<=max then
  begin
    taille1:=taille1+1;
    t1[taille1][1]:=-a+2*b+2*c;
    t1[taille1][2]:=-2*a+b+2*c;
    t1[taille1][3]:=-2*a+2*b+3*c;
    som:=som+1;
  end;
  end;
 end;
 compte:=som;
end;

begin
  writeln(compte(75000000));
end.

Delphi:

program Euler224;

{$APPTYPE CONSOLE}
{$MAXSTACKSIZE 536870912}

function calc(a, b, c, maxp: integer): integer;
  procedure go(a, b, c: integer);
  begin
    if a + b + c > maxp then exit;
    inc(result);
    go( a - 2*b + 2*c,  2*a - b + 2*c,  2*a - 2*b + 3*c);
    go( a + 2*b + 2*c,  2*a + b + 2*c,  2*a + 2*b + 3*c);
    if a <> b then go(-a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c);
  end;
begin
  result := 0;
  go(a, b, c);
end;

begin
  Writeln(calc(2, 2, 3, 75000000));
end.

Python:

def p224():
    def t1(a, b, c):
        return ( -2*a +b +2*c, -a +2*b +2*c, -2*a +2*b +3*c)
    def t2(a, b, c):
        return ( 2*a +b +2*c, a +2*b +2*c, 2*a +2*b +3*c)
    def t3(a, b, c):
        return ( a -2*b +2*c, 2*a -b +2*c, 2*a -2*b +3*c)

    max_p = 75000000
    added = {(2, 2, 3):None}
    triples_ok = 1
    while added:
        triple = added.popitem()[0]
        for new_triple in (t1(*triple), t2(*triple), t3(*triple)):
           if new_triple[0] + new_triple[1] + new_triple[2] <= max_p:
               if new_triple not in added:
                   added[new_triple] = None
                   triples_ok += 1
    print triples_ok

p224()

Maple:

> N:=(a,b,c)->[[a-2*b+2*c,2*a-b+2*c,2*a-2*b+3*c],[a+2*b+2*c,2*a+b+2*c,2*a+2*b+3*c],[-a+2*b+2*c,-2*a+b+2*c,-2*a+2*b+3*c]]:
> N2:=(a,b,c)->[[a-2*b+2*c,2*a-b+2*c,2*a-2*b+3*c],[a+2*b+2*c,2*a+b+2*c,2*a+2*b+3*c]]:
> 
> HowMany:=proc(a,b,c)
> if a+b+c>75000000 then return 0 fi;
> if a=b then return 1+add(HowMany(i[]),i in N2(a,b,c))
> else return 1+add(HowMany(i[]),i in N(a,b,c)) fi
> end:
> 
> t:=time(): HowMany(2,2,3); time()-t;

                               4137330
                                44.485