Labels

Project Euler #86: Cuboid route

Question
A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.
However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.
It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of M by M by M, for which the shortest route has integer length when M = 100. This is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions when M = 99 is 1975.
Find the least value of M such that the number of solutions first exceeds one million.

Answer : 1818

Hacker Rank Problem

Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.ArrayList;
import java.util.Scanner;

public class Solution {
    
    private static int getSquareRoot(long a) {
        long f = 0;
        int ret = 0;
        for(long i = 0; i < 16; i++) {
            ret <<= 1;
            long kari_f = (f + 1) << ((15 - i) * 2);
            if(a >= kari_f) {
                f = f + 2;
                a -= kari_f;
                ret++;
            }
            f <<= 1;
        }
        return ret;
    }
    
    private static int combinations(int a, int b_c) {
        if(2 * a < b_c) {
            return 0;
        }
        if(a >= b_c) {
            return b_c / 2;
        }
        return a - (b_c - 1) / 2;
    }
    
    private static int gcd(int a, int b) {
        while(a != 0) {
            int temp = a;
            a = b % a;
            b = temp;
        }
        return b;
    }
    
    private static long[] countAll(int limit) {
        long[] solutions = new long[limit + 1];
        for(int m = 1; m <= getSquareRoot(2 * limit); m++) {
            for(int n = 1; n < m; n++) {
                if((m % 2) != (n % 2) && gcd(m, n) == 1) {
                    int x = m * m - n * n;
                    int y = 2 * m * n;
                    for(int k = 1; k * x <= limit; k++) {
                        solutions[k * x] += combinations(k * x, k * y);
                    }
                    for(int k = 1; k * y <= limit; k++) {
                        solutions[k * y] += combinations(k * y, k * x);
                    }
                }
            }
        }
        return solutions;
    }
    
    public static void main(String[] args) {
        long[] solutions = countAll((int) Math.pow(10, 6));
        ArrayList<Long> total = new ArrayList<>();
        long sum = 0;
        for(long i : solutions) {
            sum += i;
            total.add(sum);
        }
        try(Scanner sc = new Scanner(System.in)) {
            int T = sc.nextInt();
            while(T-- > 0) {
                int N = sc.nextInt();
                System.out.println(total.get(N));
            }
        }
    }
}
Labels:

Comments

Post a Comment

Popular Posts