summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIru Cai <mytbk920423@gmail.com>2018-06-11 16:46:43 +0800
committerIru Cai <mytbk920423@gmail.com>2018-06-11 16:46:43 +0800
commit9920a766c17402a58fc4457d2fc643cc7905e684 (patch)
treeb966224ecba3cefbd11a74ad1f996dd1e35ee115
parent7f25c6fc31b376ca1ed0f4c183ef4d232b6ee2b5 (diff)
downloadproject_euler-9920a766c17402a58fc4457d2fc643cc7905e684.tar.xz
112, 345-347
-rw-r--r--euler112.c56
-rw-r--r--euler345.c67
-rw-r--r--euler346.c50
-rw-r--r--euler347.c88
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);
+}