73,74,85,357

1 files changed, 32 insertions, 0 deletions

diff --git a/euler85.c b/euler85.c
new file mode 100644
index 0000000..97687bb
--- /dev/null
+++ b/euler85.c
@@ -0,0 +1,32 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+/* rectangle count for a m*n grid:
+ * for i = 1 to m
+ *   for j = 1 to n
+ *     (m-i+1)*(n-j+1)
+ * = [m(m+1)/2][n(n+1)/2]
+ */
+
+#define AREA 2000000
+
+int main()
+{
+	int m, n, bestm, bestn;
+	int nearest = AREA;
+	for (m = 1; m <= 2000; m++) {
+		int a1 = m*(m+1)/2;
+		for (n = 1; n <= 2000; n++) {
+			int area = a1*n*(n+1)/2;
+			if (area > AREA && area-AREA>nearest)
+				break;
+			if (abs(area-AREA) < nearest) {
+				nearest = abs(area-AREA);
+				bestm = m;
+				bestn = n;
+			}
+		}
+	}
+
+	printf("%d * %d = %d\n", bestm, bestn, bestm*bestn);
+}