summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rwxr-xr-xmat/euler/11/a.outbin12832 -> 12840 bytes
-rw-r--r--mat/euler/11/prog.c93
2 files changed, 72 insertions, 21 deletions
diff --git a/mat/euler/11/a.out b/mat/euler/11/a.out
index a8b4ee3..eaae4a0 100755
--- a/mat/euler/11/a.out
+++ b/mat/euler/11/a.out
Binary files differ
diff --git a/mat/euler/11/prog.c b/mat/euler/11/prog.c
index 06cc72f..e8d6999 100644
--- a/mat/euler/11/prog.c
+++ b/mat/euler/11/prog.c
@@ -1,8 +1,9 @@
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
+#include <string.h>
#define ZACETNA_VELIKOST 128
-int ulint_array_print (unsigned long int * b, size_t a, FILE * f) {
+int slint_array_print (signed long int * b, size_t a, FILE * f) {
fprintf(f, "{ ");
for (size_t j = 0; j < a; j++) // ob !zadnjem natisnemo še ", ".
fprintf(f, "%ld%s", b[j], (j == a-1) ? "" : ", ");
@@ -11,7 +12,7 @@ int ulint_array_print (unsigned long int * b, size_t a, FILE * f) {
}
int main (int argc, char ** argv) {
if (argc != 1+1) {
- fprintf(stderr, "uporaba: %s <stevilo po vrsti>\nprimer: %s 4 < stevilka.txt\nprogram v stdin pričakuje ASCII številke, ločene z LF po vrsticah in s presledkom po stolpcih. naj se stdin konča z LF! če številke pišete na roke, začnete računanje s Ctrl+D. ker iščemo tudi po diagonalah in stolpcih se celoten input shrani v dinamično pridobljen delovni spomin.\n", argv[0], argv[0]);
+ fprintf(stderr, "uporaba: %s <stevilo po vrsti>\nprimer: %s 4 < stevilka.txt\nprogram v stdin pričakuje ASCII številke, ločene z LF po vrsticah in s presledkom po stolpcih. naj se stdin konča z LF! če številke pišete na roke, začnete računanje s Ctrl+D.\n", argv[0], argv[0]);
return 1;
}
unsigned long int n = strtoll(argv[1], NULL, 10); // Number in a row
@@ -20,15 +21,19 @@ int main (int argc, char ** argv) {
fprintf(stderr, "napaka! pred EOF ni bilo v stdin podatkov!\n");
return 2;
}
+ long int zmnozek = 1; // ko množimo, uporabimo to za buffer
+ long long int nz = 0;
size_t i = 0; // Index za loope
+ size_t j = 0; // index za globlJe loope
+ size_t k = 0; // še ena spremenljivKa
size_t z = 0; // Zapisano VRSTIC!
size_t r = 0; // zapisano številk pri trenutni vRstici!
short int t = 0; // zapisano pri Trenutni številki, da lahko delamo strtoll
- size_t velikost_v = ZACETNA_VELIKOST;
size_t velikost_1 = ZACETNA_VELIKOST; // velikost ene vrstice
- size_t * dolzina_vrstice = malloc(sizeof(size_t) * velikost_v);
- long int ** v = malloc(sizeof(long int *)*velikost_v); // Vrstice ŠTEVILK!!!
- v[0] = malloc(sizeof(long int)*velikost_1);
+ size_t * dolzina_vrstice = malloc(sizeof(size_t)*(n+2)); // dodamo za maxInMin
+ long int ** v = malloc(sizeof(long int *)*n); // zadnjih n vrstic (za (-) |/\)
+ for (i = 0; i < n; i++) // lahko bi samo za [0], itak je realloc po vsakem \n
+ v[i] = malloc(sizeof(long int)*velikost_1);
size_t vel_ts = ZACETNA_VELIKOST;
char * trenutna_stevilka = malloc(sizeof(char) * vel_ts);
trenutna_stevilka[0] = '\0';
@@ -40,37 +45,83 @@ int main (int argc, char ** argv) {
}
trenutna_stevilka[t] = c;
trenutna_stevilka[++t] = '\0';
- fprintf(stderr, "debug: nastavil trenutna_stevilka ob znaku '%c' na \"%s\"\n", c, trenutna_stevilka);
}
if (c == ' ' || c == '\n') { // ločilo
if (velikost_1-3 <= r+3) { // off by one (:
velikost_1 = velikost_1 * 2;
- v[z] = realloc(v[z], velikost_1 * sizeof(long int));
+ v[z % n] = realloc(v[z], velikost_1 * sizeof(long int));
}
- v[z][r] = strtol(trenutna_stevilka, NULL, 10);
- fprintf(stderr, "debug: nastavil v[%ld][%ld] iz \"%s\" na %ld.\n", z, r, trenutna_stevilka, v[z][r]); // dobro bi bilo nastaviti [0] na \0 PO tem!
+ v[z % n][r] = strtol(trenutna_stevilka, NULL, 10);
trenutna_stevilka[0] = '\0';
r++;
+ if (r >= n) { // preskusimo za vodoravne faktorje
+ zmnozek = 1; // na prvem runnu za npr. n=4 bomo torej brali [0][1][2][3]
+ for (i = 0; i < n; i++) // na drugem pa bo r-1 = 1, zato [1][2][3][4]
+ zmnozek = zmnozek*(v[z % n][((r-1)-(n-1))+i]); // r-1 smo pravkar zapisali
+ if (zmnozek > nz) {
+ nz = zmnozek;
+ slint_array_print(v[z % n]+((r-1)-(n-1)), n, stdout);
+ fprintf(stdout, ": nove vodoravne z največjim zmnožkom %lld.\n", nz);
+ }
+ }
t = 0;
}
if (c == '\n') { // c je ločilo
- if (velikost_v-3 <= z+3) { // for good measure imamo šest vrstic več #OB1
- velikost_v = velikost_v * 2;
- v = realloc(v, sizeof(long int *)*velikost_v);
- dolzina_vrstice = realloc(dolzina_vrstice, sizeof(size_t) * velikost_v);
- }
- dolzina_vrstice[z] = r;
+ dolzina_vrstice[z % n] = r;
velikost_1 = ZACETNA_VELIKOST;
z++;
- v[z] = malloc(velikost_1 * sizeof(long int));
+ v[z % n] = realloc(v[z % n], velikost_1 * sizeof(long int));
+ if (z >= n) { // če smo že zapisali n vrstic, lahko iščemo |\/
+ dolzina_vrstice[n] = 0; // max
+ dolzina_vrstice[n+1] = 69694201337; // min
+ for (i = 0; i < n ; i++) // najprej dobimo max in min dolzino_vrstice.
+ if (dolzina_vrstice[i] > dolzina_vrstice[n])
+ dolzina_vrstice[n] = dolzina_vrstice[i];
+ if (dolzina_vrstice[i] < dolzina_vrstice[n+1])
+ dolzina_vrstice[n+1] = dolzina_vrstice[i];
+ zmnozek = 1;
+ for (i = 0; i < dolzina_vrstice[n+1]; i++) { // i-stolpec - preskušamo|
+ zmnozek = 1;
+ for (j = 0; j < n; j++) // j je vrstica
+ zmnozek = zmnozek*(v[j][i]); // iščemo po stolpcih
+ if (zmnozek > nz) {
+ nz = zmnozek;
+ slint_array_print(v[z % n]+((r-1)-(n-1)), n, stdout);
+ fprintf(stdout, ": nova navpična z največjim zmnožkom %lld.\n", nz);
+ }
+ }
+ i = 0; // stolpec
+ j = 0; // vrstica
+ k = 0; // orientacija: 0: \, 1: /
+ for (k = 0; k <= 1; k++) {
+ for (i = k ? n - 1 : 0; i < dolzina_vrstice[0]; i++) {
+ zmnozek = 1;
+ for (j = 0; j < n; j++) {
+ if (i >= dolzina_vrstice[j])
+ goto continue_nov_stolpec_diagonala;
+ if (k)
+ zmnozek = zmnozek * v[j][i-j];
+ else
+ zmnozek = zmnozek * v[j][i+j];
+ }
+ if (zmnozek > nz) {
+ nz = zmnozek;
+ slint_array_print(v[z % n]+((r-1)-(n-1)), n, stdout);
+ fprintf(stdout, ": nove diagonale z največjim zmnožk. %lld.\n", nz);
+ }
+ continue_nov_stolpec_diagonala:
+ ;
+ }
+ }
+ }
r = 0;
}
c = fgetc(stdin);
}
// sedaj samo preverimo, če se pravilno preberejo številke #DEBUG
- for (i = 0; i < z; i++) {
- ulint_array_print(v[i], dolzina_vrstice[i], stderr);
- fprintf(stderr, "\n");
- }
+ // for (i = 0; i < n; i++) {
+ // slint_array_print(v[i], dolzina_vrstice[i], stderr);
+ // fprintf(stderr, "\n");
+ // }
return 0;
}