- All Contests
- ProjectEuler+
- Project Euler #173: Using up to one million tiles how many different "hollow" square laminae can be formed?
- Discussions
Project Euler #173: Using up to one million tiles how many different "hollow" square laminae can be formed?
Project Euler #173: Using up to one million tiles how many different "hollow" square laminae can be formed?
+ 3 comments I got 100/100 point.
My Solution: we need calculate how many pair (a, b) with: a^2 - b^2 <= n
=> (a - b)(a + b) <= n
Let: a = b + k (with b > 0; k> 0; and k is even, means: k % 2 == 0)
=> k(2b + k) <= n
=> b <= (n/k - k)/2
The result is sum of all b.
We need 1 FOR-loop: from 1 to sqrt(n):
long caculate(n, k) { return (long) ((double) n / k - k) / 2; } // Main: sum = 0; for (int k = 2; k < sqrt(n); k += 2) { b = calculate(n, k); if (b > 0) sum += b; } return sum;
n,k,b.. is Long, not Integer!
GOOD LUCK!!
+ 0 comments I was able to make it working using the below algorithm. private static long findNums(long totalTiles){ int maxLvel = (int)Math.sqrt(totalTiles-1)/2; long count = 0; for(int i = 1;i<=maxLvel;i++){ //Finds number of laminates of the same level. For a a given hole size h and a level l (2*(l+h/2))^2 <= tiles + h^2 count += (long) ((totalTiles/(4*i))-i); } return count; }
+ 0 comments Is there no way to find out the input of each test case?
+ 0 comments PLEASE IF SOMEONE COULD HELP ME WITH THE BELOW CODE::: double d=Math.sqrt((double)n); int y=(int)d; for(int g=(int)d;g>=3;g--) { int p=g*g; if(g%2==0) { int v=2; int fl=v*v; while(fl
+ 0 comments Hi, I have solved the problem but i face a timeout/algorithm complexity issue. I have solved it using a nested forloop. Basically for a^2-b^2 = N where b is the inner square(non tile laminae).In order for the tiles to arrange themselves in such a way where there is always a non tile laminae, b should exist as an integer. here is the logic:
for m in range(4,t+1,4):
x = (m/4)+1 for i in range(int(x),2,-1): if(i*i>m and math.sqrt(i*i-m).is_integer()): c += 1 elif(i*i<=m): break
Can someone suggest how i can improve my code.
Sort 16 Discussions, By:
Please Login in order to post a comment