112, 345-347

4 files changed, 261 insertions, 0 deletions

diff --git a/euler112.c b/euler112.c
new file mode 100644
index 0000000..e2414bd
--- /dev/null
+++ b/euler112.c
@@ -0,0 +1,56 @@
+#include <stdio.h>
+#include <assert.h>
+
+int isbouncy(int a)
+{
+	int d[2];
+	int incr;
+	if (a < 100)
+		return 0;
+
+	d[0] = a % 10;
+	d[1] = (a / 10) % 10;
+	a /= 100;
+	if (d[1] > d[0])
+		incr = 1;
+	else if (d[1] < d[0])
+		incr = -1;
+	else
+		incr = 0;
+
+	while (a > 0) {
+		d[0] = d[1];
+		d[1] = a % 10;
+		if (incr == 1 && d[1] < d[0])
+			return 1;
+		if (incr == -1 && d[1] > d[0])
+			return 1;
+		if (incr == 0) {
+			if (d[1] > d[0])
+				incr = 1;
+			else if (d[1] < d[0])
+				incr = -1;
+		}
+		a /= 10;
+	}
+	return 0;
+}
+
+int main()
+{
+	assert(isbouncy(66420) == 0);
+	assert(isbouncy(134468) == 0);
+	assert(isbouncy(155349) == 1);
+
+	int nbouncy = 0;
+	for (int i = 100; i <= 0x7fffffff; i++) {
+		if (isbouncy(i))
+			nbouncy++;
+
+		if (nbouncy * 100 / 99 == i) {
+			printf("%d\n", i);
+			break;
+		}
+	}
+}
+
diff --git a/euler345.c b/euler345.c
new file mode 100644
index 0000000..b598981
--- /dev/null
+++ b/euler345.c
@@ -0,0 +1,67 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int mxsum(int **m, int n, int d, int visited[])
+{
+	int ans;
+	int sel = -1;
+	if (d == n)
+		return 0;
+
+	/* select the biggest of the line first */
+	for (int i = 0; i < n; i++) {
+		if (!visited[i]) {
+			if (sel == -1)
+				sel = i;
+			else if (m[d][i] > m[d][sel])
+				sel = i;
+		}
+	}
+	visited[sel] = 1;
+	ans = m[d][sel] + mxsum(m, n, d+1, visited);
+	visited[sel] = 0;
+
+	for (int i = 0; i < n; i++) {
+		if (visited[i] || i == sel)
+			continue;
+		visited[i] = 1;
+		int t = m[d][i];
+		/* estimate the maximum value of remaining numbers */
+		int re = 0;
+		for (int j = d+1; j < n; j++) {
+			int linemax = 0;
+			for (int k = 0; k < n; k++) {
+				if (!visited[k] && m[j][k] > linemax)
+					linemax = m[j][k];
+			}
+			re += linemax;
+		}
+		if (t + re > ans) {
+			t += mxsum(m, n, d+1, visited);
+		}
+		visited[i] = 0;
+		if (t > ans)
+			ans = t;
+	}
+	return ans;
+}
+
+int main()
+{
+	int n;
+	int **m;
+	int visited[15];
+
+	scanf("%d", &n);
+	m = (int**)malloc(sizeof(int*) * n);
+	memset(visited, 0, sizeof(visited));
+	for (int i = 0; i < n; i++) {
+		m[i] = (int*)malloc(sizeof(int) * n);
+		for (int j = 0; j < n; j++) {
+			scanf("%d", &m[i][j]);
+		}
+	}
+
+	printf("%d\n", mxsum(m, n, 0, visited));
+}
diff --git a/euler346.c b/euler346.c
new file mode 100644
index 0000000..dc10d65
--- /dev/null
+++ b/euler346.c
@@ -0,0 +1,50 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#define MAXN 1000000000000
+#define NRUMAX 10000000
+
+long long ru[NRUMAX];
+int nru = 0;
+
+int comp(const void *a, const void *b)
+{
+	long long x = *(long long*)a;
+	long long y = *(long long*)b;
+
+	if (x < y)
+		return -1;
+	else if (x > y)
+		return 1;
+	else 
+		return 0;
+}
+
+int main()
+{
+	long long sum_repunit = 1; /* 1 is a strong repunit */
+	for (int base = 2; base < 1000000; base++) {
+		long long repunit = 1 + base;
+		long long nb = base;
+		while (1) {
+			nb *= base;
+			repunit += nb;
+			if (repunit >= MAXN)
+				break;
+			assert(nru < NRUMAX);
+			ru[nru] = repunit;
+			nru++;
+		}
+	}
+
+	qsort(ru, nru, sizeof(long long), comp);
+
+	printf("Find %d strong repunits.\n", nru + 1);
+	for (int i = 0; i < nru; i++) {
+		if (i > 0 && ru[i] == ru[i-1])
+			continue;
+		sum_repunit += ru[i];
+	}
+	printf("Their sum is %lld\n", sum_repunit);
+}
diff --git a/euler347.c b/euler347.c
new file mode 100644
index 0000000..c1ab166
--- /dev/null
+++ b/euler347.c
@@ -0,0 +1,88 @@
+#include <stdio.h>
+#include <string.h>
+
+#define N 10000000
+//#define N 100
+
+int nprimes;
+int primes[N];
+int divisor[N+1];
+
+void find_primes()
+{
+	memset(divisor, 0, sizeof(divisor));
+	nprimes = 0;
+	for (int i = 2; i <= N/2; i++) {
+		if (divisor[i] == 0) {
+			primes[nprimes] = i;
+			nprimes++;
+		}
+		for (int j = 0; j < nprimes; j++) {
+			int t = i * primes[j];
+			if (t > N)
+				break;
+			divisor[t] = i;
+		}
+	}
+}
+
+int M(int p, int q, int n)
+{
+	int r = 0;
+	long long t1 = p;
+	while (t1 < n) {
+		long long t2 = t1 * q;
+		if (t2 > n)
+			break;
+		while (t2 * q <= n) {
+			t2 *= q;
+		}
+		if (t2 > r)
+			r = t2;
+		t1 *= p;
+	}
+	return r;
+}
+
+int ismpqn(int n)
+{
+	int npf = 0;
+	int pf[64];
+
+	if (divisor[n] == 0)
+		return 0;
+
+	int t = n;
+	while (divisor[t] != 0) {
+		int d = t / divisor[t];
+		pf[npf] = d;
+		npf++;
+		while (t % d == 0) {
+			t /= d;
+		}
+	}
+	if (t > 1) {
+		pf[npf] = t;
+		npf++;
+	}
+
+	if (npf != 2)
+		return 0;
+
+	/* TODO: Maybe it can be optimized, but it looks enough */
+	if (M(pf[0], pf[1], N) == n)
+		return 1;
+	else
+		return 0;
+}
+
+int main()
+{
+	long long s = 0;
+	find_primes();
+	for (int i = 1; i <= N; i++) {
+		if (ismpqn(i))
+			s += i;
+	}
+	printf("%lld\n", s);
+}