De ce pana la 10^6? Eu mi-am generat pana la sqrt(10^6)...
Cred ca pana la 10^6 ar lua mai mult timp generarea si nici nu vad cu ce m-ar ajuta.

Ma opresc cand gasesc un factor care apare de doua ori, dar tot iau TLE. Am incercat sa exclud si patratele perfecte din cautare si tot TLE...

Calcularea vectorului X am observat ca ia peste jumatate din timp pe testele mari. Aici nu se poate optimiza nimic?

tii minte intrun vector numerele prime, si apoi cand factorizezi parcurgi numai acele numere atata timp cat prim*prim < n.

Pai asa fac, iar asta e O(MAX sqrt MAX) deoarece se parcurg toate numerele de la 2 la MAX, iar pt fiecare numar i din acestea se parcurg O(sqrt(i)) numere => O(MAX sqrt MAX) in total...
 

Cum pot determina eficient numerele in a caror descompunere fiecare divizor prim apare o singura data?

Cu factorizarea fiecarui numar se ajunge la O(MAX sqrt MAX) si imi iese din timp pe aproape toate testele...

Daca ai un graf cu 4 noduri si urmatoarele muchii + capacitati:

1 2 3
2 3 100
3 4 100

Capacitatea de la 1 la 4 este 3. Dar daca maresti capacitatea pe muchia 1 2 la 10, capacitatea de la 1 la 4 va fi 10. Daca in schimb maresti capacitatea pe muchia 2 3, capacitatea de la 1 la 4 tot 3 va ramane. Problema cere gasirea acestor muchii (cum e 1 2 - critica).

 
Nu m-as fi gandit la asta . Mersi mult, am luat accepted.

Pai eu nu fac pur si simplu drum initial + eliminare muchii + inca un drum. Am zis ca fac unele modificari pe graf si pe acest drum. Pe exemplu imi da 8.

Cat despre algoritm, mai pe larg e cam asa:

Gaseste un drum minim de la 1 la n.
Toate muchiile le inlocuiesc cu arce orientate catre sursa (mai exact, daca drumul e format din muchiile (1,2), (2,3), acestea vor fi inlocuite cu arcele 2->1 si 3->2). Costul acestor arce il pun pe -1.
Rulez din nou algoritmul de drum minim (eu am ales bellman ford sa n-am probleme cu costurile negative..). Apoi elimin muchiile alese atat in primul drum cat si in cel de-al doilea, si imi raman muchiile drumului dus-intors.

Edit: Alte idei de rezolvare care ar fi? Am inteles ca se poate face si cu flux?

Nu m-am uitat ce drum aleg (ar fi mai dificila reconstituirea..), dar imi da 6, atat cu rezolvarea eficienta cat si cu back. Nu e bine 6?

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1747

Iau WA. Pe toate testele pe care le pot verifica manual (sau cu back; ar fi culmea ca si backu sa dea *acelasi* raspuns gresit) imi da bine. Aveti niste teste sau idei ce ar putea avea?

Eu gasesc un drum minim, fac niste transformari pe graf, mai gasesc un drum minim, iar apoi prelucrez drumurile gasite...

Super, eu am facut problema fractii mult mai urat. Tin minte ca generam numere prime si apoi foloseam doua formule. Nu m-am gandit sa fac scazand din multiplii...

Mersi mult, foarte folositor!

Un pic mai pe larg:

Pentru a genera numere aleatorii, folosesti functia rand() din headerul <cstdlib>

Pentru a genera numere random diferite la fiecare executie a programului, poti sa incluzi headerul <ctime> si inainte de a apela functia rand(), sa apelezi srand(time(0)) (o singura data in tot programul).

Pentru a genera numere random intr-un anumit interval [0, n), folosesti rand() % n.

Succes!

Da, asa e. M-am grabit. Tot am comentat si decomentat portiuni si schimbat tipuri de date si nu mai stiam de ce ba iau 100 ba 0...

Mersi .

Daca are cineva chef sa se uite peste sursele astea 2 si sa-mi explice de ce una ia 100 si cealalta 0, i-as fi super recunoscator...

http://infoarena.ro/job_detail/110845
http://infoarena.ro/job_detail/110843

Singura diferenta este comentariul de pe linia 53.

Practic, cu comentariu iau sigsegv, fara iau 100. Acel vector nu e folosit niciunde in program, si nu-mi dau seama cum ar putea influenta ceva lipsa lui...

ie S o matrice cu semnificatia ca S[p][q] reprezinta numarul de valori de 1 din coloana q de pe liniile ≤ p. Putem calcula aceasta matrice dupa recurenta S[p][q] = S[p][q-1] + T[p][q] unde T este o matrice reprezentand terenul.

nu cumva S[p][q] = S[p-1][q] + T[p][q]?

Folosind calculatorul din windows da:

0,14455445544554455445544554455446

Deci este perioada (6 e de la rotunjire). Nu prea poti obtine atatea cifre exacte dupa virgula folosind double...

Mi-a iesit pana la urma, mersi!

Pai, in solutia oficiala spune:

Pe fiecare muchie a grafului (i,j) se pune o distanta egala cu valoarea A[j] (A fiind matricea data). Se aplica apoi algoritmul Roy-Floyd pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).

Eu asa am facut. Am mai pus si verificarea zisa de tine, dar tot incorect iau..

N-ar trebui sa ajunga doar pasii din solutia oficiala?

Exista ceva cazuri particulare mai subtile? Am facut rezolvarea in O(n³) si iau incorect

Vezi functia shellexecute

http://www.decompile.com/cpp/faq/run_other_programs.htm
http://www.codeproject.com/system/newbiespawn.asp

Tot nu cred ca am inteles... fac in felul urmator si iau 0 puncte, desi pe exemplu merge:

Pentru liste am folosit STL vector.

La inceput setez d[ x] = 0 si il adaug pe x in L[0].

Apoi, pentru fiecare i de la 0 la 1000, parcurg lista L[ i] cu un j si daca i == d[ L[ i][j] ], expandez aceste noduri, adaugand vecinii lor in listele corespunzatoare. Daca pot reduce vreun d pentru vecini, o fac...

Ce n-am inteles? Banuiesc ca se poate intampla ca la un pas i, sa adaug un nod intr-o lista k < i, nod la care nu se va mai ajunge niciodata... atunci cum ar trebui sa procedez?

Mi-ar putea explica cineva mai pe larg un pic solutia oficiala, cea cu dijkstra modificat? Un lucru pe care nu-l inteleg este urmatorul:

Cum ponderile muchiilor sunt numere de la 1 pana la 1000 inseamna ca in d[ i] oricare ar fi nodul i va fi intotdeauna mai mica sau egala cu 1000.

d[ i] ce reprezinta? Daca reprezinta distanta de la sursa pana la nodul i, atunci aceasta poate lua valori mai mari decat 1000... deci ce reprezinta de fapt?

Si inca ceva, listele astea cum se parcurg mai exact?

Ati ales deja? 


Facuta de frate-meu

Nu cred ca un admin iti va da testul 9. Mai bine spui cum te-ai gandit sa rezolvi problema si o sa incercam sa te ajutam, eventual cu un contraexemplu.

Interesant, daca fac urmatoarele modificari:

Cod:

#include <stdio.h>
#include <string.h>

char s[66000];

int main()
{
        int i;
    FILE *f = fopen("test.in","w");
    for (i = 0; i < 32000; i++) fprintf(f, "a");
	for (i = 32000; i < 65000; i++) fprintf(f, "b");
	fclose(f);
	f = fopen("test.in","r");
	fscanf(f, "%s", s);
        i = strlen(s);
        printf("%d\n", i);
	return 0;
}

Afiseaza pe ecran 65000.

Daca nu modific nimic, in fisier am valoarea 61440 la sfarsit. Daca folosesc un watch, mi-l arata pe i ca fiind tot 61440...

Asta pe Windows cu compilator gcc. Banuiesc ca freopen e de vina...

Prin 60 000 de caractere se refera la 60 000 de octeti... deci pune 60000*8.

Cam neclar intr-adevar... si '0' si '1' sunt caractere.

Da.