Euler Projesi 247. Soru

Hiperbol Altındaki Kareler

$1\le x$ ve $0\le y \le 1/x$ ile sınırlanmış bölgeyi düşünün.

Eğrinin altına sığan en büyük kare $S_1$ olsun.
Kalan alana sığan en büyük kare $S_2$ olsun ve böylece devam etsin.
(Sol, Aşağı) çiftinde $S_n$ karesinin solunda kalan karelerin sayısı Sol ve aşağısında kalan karelerin sayısı Aşağı olmak üzere bu sıralı ikiliyi $S_n$'nin indeksi olarak tanımlayınız.

Şekilde sayılarla etiketlenmiş böylesi bazı kareleri görüyorsunuz.
$S_2$'nin solunda 1, altında 0 kare bulunduğundan dolayı indeksi (1,0)'dır.
$S_2$ ve $S_2$ karelerinin indekslerinin (1,1) olduğu görülebilir.
İndeksi (1,1) olan en büyük n değeri 50'dir.

İndeksi (3,3) olan en büyük n değeri kaçtır?

[Project Euler]
Cevap: 782252
Java import java.util.TreeSet; /** * Problem 247 * @author fra */ public class Problem247 { /** * Solves the problem for indexes (n,n) * @param n * @return */ public Object solve(Integer n) { this.n = n; int max = -1; add(new Square(0,0,1,0)); for (int i = 1; stillToCheck > 0; i++) { Square c = get(); if(c.left == n && c.below == n ){ max = i; } c.addNnext(); } return max; } //Target index value int n; /** * Sqaures to process */ TreeSet<square> yetToProcess = new TreeSet<square>(); /** * Squares left that might have indexes <= n */ int stillToCheck = 0; /** * Adds a new square to the list of the ones to check * @param c */ private final void add(Square c){ yetToProcess.add(c); if(c.below <= n && c.left <= n) ++stillToCheck; } /** * Returns the biggest square * @return */ private final Square get() { Square c = yetToProcess.pollFirst(); if (c.left <= n && c.below <= n) { --stillToCheck; } return c; } private class Square implements Comparable<square>{ int left; int below; double x; //down-left corner double y; double xNext; // right x double area; //area of the square public Square(int left, int below, double x, double y) { this.left = left; this.below = below; this.x = x; this.y = y; this.xNext = getSquareX(); this.area = (xNext - x) * (xNext - x); } private double getSquareX(){ double d = x - y; return 0.5 * (d + Math.sqrt(d*d + 4)); } public void addNnext(){ add(new Square(left+1, below , xNext, y)); add(new Square(left, below+1 , x, 1/xNext)); } /** * Sort descending by area * @param o * @return */ public int compareTo(Square o) { return Double.compare(o.area, area); } @Override public String toString() { return "(" + x + "," + y + "): " + area; } } public static final void main(String args[]){ int n = (args.length >0)? Integer.parseInt(args[0]) : 3; System.out.println("F(" + n + ")=" + new Problem247().solve(n)); } } Python import math, heapq def sq_size(x, y): return (math.sqrt((x-y)**2+4)-x-y)/2 heap = [] heapq.heappush(heap, (-sq_size(1, 0), 1, 0, 0, 0)) n = 0 c = 1 imax = 3 jmax = 3 while True: x = heapq.heappop(heap) n += 1 if x[3] < imax and x[4] < jmax: c += 1 elif x[3] == imax and x[4] == jmax: c -= 1 if c == 0: print(n) break d1 = -sq_size(x[1], x[2] - x[0]) d2 = -sq_size(x[1] - x[0], x[2]) heapq.heappush(heap, (d1, x[1], x[2] - x[0], x[3], x[4] + 1)) heapq.heappush(heap, (d2, x[1] - x[0], x[2], x[3] + 1, x[4])) C/C++ #include<stdio.h> #include<math.h> #include<queue> #define LIM 5000000 struct qdata { double r; double sx, sy; int l, b; friend bool operator < (qdata d1, qdata d2) { return d1.r<d2.r; } }; using namespace std; priority_queue<qdata> q; int ans; double f_get(double sx, double sy) { return (sqrt((sx+sy)*(sx+sy)-4.0*(sx*sy-1.0))-(sx+sy))/2.0; } int main() { int i; int cnt=0; qdata cur, nxt; nxt.sx=1.0; nxt.sy=0.0; nxt.l=0; nxt.b=0; nxt.r=f_get(nxt.sx, nxt.sy); if(nxt.b<=3 && nxt.l<=3) cnt++; q.push(nxt); for(i=1;cnt && q.size()<LIM;i++) { cur=q.top(); q.pop(); if(cur.b<=3 && cur.l<=3) cnt--; if(cur.b==3 && cur.l==3) ans=i; nxt.sx=cur.sx+cur.r; nxt.sy=cur.sy; nxt.l=cur.l+1; nxt.b=cur.b; nxt.r=f_get(nxt.sx, nxt.sy); if(nxt.b<=3 && nxt.l<=3) cnt++; q.push(nxt); nxt.sx=cur.sx; nxt.sy=cur.sy+cur.r; nxt.l=cur.l; nxt.b=cur.b+1; nxt.r=f_get(nxt.sx, nxt.sy); if(nxt.b<=3 && nxt.l<=3) cnt++; q.push(nxt); } if(cnt) printf("OVERFLOW!\n"); else printf("%d\n", ans); return 0; } LISP (defun calpoint (p) (let ((x0 (car p)) (y0 (cadr p)) dxy sq) (setf dxy (- x0 y0) sq (sqrt (+ (* dxy dxy) 4l0))) (list (/ (+ dxy sq) 2l0) (/ (- sq dxy) 2l0)))) (defvar pl nil) (defvar sl '((0 0 1l0 0l0))) (defvar lst33 nil) (defvar min33 0l0) (defun newpoint (lst) (let ((l (car lst)) (b (cadr lst)) (p (calpoint (cddr lst))) (p1 nil) (p2 nil) s d) (setf d (- (car p) (caddr lst)) s (* d d)) (when (>= s min33) (setf p1 (list l (1+ b) (caddr lst) (cadr p)) p2 (list (1+ l) b (car p) (cadddr lst))) (setf pl (cons (append lst (list s)) pl)) (if (= l b 3) (setf lst33 (cons (car pl) lst33)))) (if (and p1 p2) (list p1 p2) nil))) (defun ls (a b) (< (nth 4 a) (nth 4 b))) (defun gs (a b) (> (nth 4 a) (nth 4 b))) (let ((cnt 0)) (defun initcnt nil (setf cnt 0)) (defun addcount (l) (list (car l) (cadr l) (setf cnt (1+ cnt))))) (defun searchpoint (l) (do ((x l (cdr x)) (rslt nil)) ((not x) rslt) (setf rslt (append (newpoint (car x)) rslt)))) (do ((no 0 (1+ no)) (l sl sl)) ((not l) (print no)) (when (>= no 8) (sort lst33 #'ls) (setf min33 (nth 4 (car lst33)))) (setf sl (searchpoint l))) (sort pl #'gs) (defvar ans (mapcar #'addcount pl)) (print (remove-if-not #'(lambda (l) (= 3 (car l) (cadr l))) ans) )