diff options
| -rw-r--r-- | euler112.c | 56 | ||||
| -rw-r--r-- | euler345.c | 67 | ||||
| -rw-r--r-- | euler346.c | 50 | ||||
| -rw-r--r-- | euler347.c | 88 |
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); +} |