Afişează mesaje
|
Pagini: [1]
|
1
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Another solution.
|
: Martie 29, 2012, 11:25:47
|
Se poate renunta la recursivitatea indirecta, arbori dar si la chestia aia pe nivele, folosind o singura functie recursiva. Ideea este ca atunci cand dai de un + sau - sa te comporti la fel cum s-ar deschide o paranteza imediat dupa acel operator de prioritate scazuta, iar cand dai iar de un astfel de operator faci la fel cum s-ar fi inchis paranteza, astfel returnand ceea ce ai calculat deja. In felul asta stii ca intotdeauna * si / vor avea prioritate, deoarece se vor gasi numai intre acele pseudoparanteze.
|
|
|
2
|
infoarena - concursuri, probleme, evaluator, articole / SPOJ / 15. SHPATH
|
: Iunie 11, 2011, 21:34:42
|
Esec dupa esec ...  Am testat-o de-am inebunit si pe valori mari (mai mari decat in cerinta) si pe teste ciudate/lungi si totul e ok, apoi ii dau submit imi intra in 3.7s (sub 5 limita) de memorie nici nu mai vorbesc in schimb imi da WA: sursa la shpath. Folosesc un simplu bfs cu actualizari pe un graf neorientat cu lista de adiacenta (in loc de Dijkstra). L.E.:Cred ca stiu unde gresesc, dar acum iau sigsev (trebuie sa implementez coada aia calumea, uitam sa adaug nod in coada in momentul cand faceam o actualizare). Edit2: Da ... cum credeam, idiotul din mine loveste din nou am reparat greseala ( http://codepad.org/ahSZrldH) dar iau tle, era si cazul fiindca m-a mancat in cur sa nu bag Dijkstra. Last edit: Folosind varianta cu limita de 25 de secunde (TSHPATH) nu pot scoate mai putin de 24 secunde (imi trebuie sub 20), varianta fiind asta. Am facut o versiune mult mai optima si mai "atenta", dar in practica se descurca ceva mai prost decat sursa de mai sus. A iesit pana la urma s-o f*t: http://codepad.org/w4wD8YUl
|
|
|
3
|
infoarena - concursuri, probleme, evaluator, articole / SPOJ / Răspuns: 503. PRINT
|
: Iunie 09, 2011, 19:22:08
|
Zis si facut ... am implementat algoritmul in C (pentru problema Dk mai intai), dar mi-l ia pe 9 ca numar prim, pana si algoritmul in sine de pe pagina lor de wikipedia. Python putin modificat, dar structura algoritmului e aceeasi: import random import math def miller_rabin(n): k = 1000 s = max(f for f in range(0, int(math.log(n,2))) if (n-1) % 2**f == 0) d = (n-1) / 2**s for i in xrange(k): a = random.randrange(2, n-1) x = pow(a, d, n) if x == 1 or x == n-1: continue for r in range(1, s+1): if x == s: return False x = pow(x, 2, n) if x == 1: return False if x == n-1: break return True print filter(miller_rabin, range(5, 100, 2)) Si implementarea in C (mai e loc de optimizari): http://pastebin.com/5e8e9dWhAm verificat si algoritmul din pseudocod cu bazele 2 7 si 61 (care merg corect pe numere sub 4 miliarde) dar mi-l ia si aici pe 9 (posibil si altele) oricum pe problema Dk iau cateva WA in rest numai TLE  .
|
|
|
4
|
infoarena - concursuri, probleme, evaluator, articole / SPOJ / 503. PRINT
|
: Iunie 08, 2011, 21:55:51
|
Stie cineva o abordare mai rapida la PRINT decat O(t*(b-a)*sqrt(b)/2) pentru a afisa toate numerele prime dintr-un interval ? Am incercat asta, dar imi ia cateva secunde pe test numai pentru afisare pe cand mie trebuie sa-mi ia maxim 0.06 in medie sa se incadreze in 9-10 secunde la 150 teste maxim. Ciur nu cred ca merge nu-ti pun la dispozitie 2gb ram, oricum am vazut best answers si de 2s cu 1.7mb am ramas oO. Am incercat si pe biti (mini ciur + verificare daca e prim cu ultimu bit ... la fel fail). Merci anticipat!
|
|
|
5
|
infoarena - concursuri, probleme, evaluator, articole / SPOJ / 439. TMUL
|
: Mai 07, 2011, 13:55:48
|
Nu am nici cea mai mica idee de ce obtin WA pe TMUL (dupa ce trec de asta vreau sa nu scot TLE pe MUL). L-am testat in toate felurile si da bine. #include <stdio.h> #include <ctype.h> #define base 1000000000 #define len 9 #define N 1113
unsigned long long first[N], second[N], last[2 * N];
inline void init() { char chr; unsigned short cnt; unsigned long total; first[0] = second[0] = 0; cnt = 0; total = getchar() - '0'; while (!isspace(chr = getchar())) { if (++cnt != len) { total = total * 10 + chr - '0'; } else { first[++first[0]] = total; total = chr - '0'; cnt = 0; } } first[++first[0]] = total; cnt = 0; total = getchar() - '0'; while (!(isspace(chr = getchar()) || chr == EOF)) { if (++cnt != len) { total = total * 10 + chr - '0'; } else { second[++second[0]] = total; total = chr - '0'; cnt = 0; } } second[++second[0]] = total; }
inline void zfill(unsigned long nr, char str[]) { unsigned short cnt = 0, i = 0; if (!nr) { cnt = 1; } else { while (nr > 0) { ++cnt; nr /= 10; } } for (; i < len - cnt; ++i) { str[i] = '0'; } str[i] = 0; }
inline void process() { unsigned long long temp = 0; unsigned short i, j; char str[10]; if (!first[1] || !second[1]) { putchar('0'); } else { last[0] = first[0] + second[0] - 1; for (i = first[0]; i > 0; --i) { for (j = second[0]; j > 0; --j) { last[i + j - 1] += first[i] * second[j] + temp; temp = last[i + j - 1] / base; last[i + j - 1] %= base; } } if (temp) { printf("%lu", (unsigned long) temp); } for (i = 1; i <= last[0]; ++i) { if (i != 1) { zfill((unsigned long) last[i], str); } else { str[0] = 0; } printf("%s%lu", str, (unsigned long) last[i]); last[i] = 0; } } putchar('\n'); }
int main() { short nr; freopen("mul.in", "rt", stdin); scanf("%hd\n", &nr); while (nr-- > 0) { init(); process(); } return 0; }
Edit ... am rezolvat, nu aveam grija la mutiplul lungimii bazei si la transport. http://pastebin.com/iMmPUa4d
|
|
|
6
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: TLCS rapid
|
: Aprilie 27, 2011, 17:39:44
|
Corect, dar scorul il ia de pe spoj (teste, compilare, run totul se face acolo) ... oricum am reusit sa-mi iasa de 1000. Dinamica clasica numai ca pentru generarea solutiei trebuie folosit un vector nu o structura/clasa cum am facut eu. Si apoi pentru fiecare caracter se cauta pozitiile de unde a ramas cautarea anterioara. Desi pare ineficient e mai rapid.
|
|
|
11
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 026 Energii
|
: Decembrie 29, 2010, 01:49:52
|
Am doua surse cu o foarte mica diferenta: Prima sursa goodA doua sursa badDiferenta intre good si bad este ca am dat swap la dimensiuni intr-o matrice, adica am inversat liniile cu coloanele schimband de asemenea si rolul indicilor pentru a avea aceleasi rezultate, insa la a doua sursa primesc TLE (time limit exceeded) si nu inteleg de ce fiindca atat ordinul de complexitate, numarul cat si resursele alocate instructiunilor raman aceleasi. Mai exact din O(g*w) am facut O(w*g).
|
|
|
|