•DITzoneC
|
|
« Răspunde #25 : Iulie 12, 2007, 11:15:52 » |
|
Cred ca ar trebui sa dea 600 Ii pui sa concureze asa: 6 4 4 4 4 2 2 2 1 4 4 4 4 2 2 1 1 4
|
|
« Ultima modificare: Iulie 12, 2007, 11:18:07 de către Adrian Diaconu »
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #26 : August 30, 2007, 21:31:24 » |
|
am verificat toate exemplele de pe forum + vreo 2 de'ale mele.. toate imi dau cat ar trebui (ma refer la cele de pe forum.. )... totusi.. iau incorect.... .. vreo sugestie?
|
|
|
Memorat
|
|
|
|
•coderninu
Strain
Karma: 1
Deconectat
Mesaje: 26
|
|
« Răspunde #27 : August 12, 2008, 18:13:33 » |
|
Toate testele de pe forum si exemplu imi dau bine. Sortez crescator si fol doua deque. Are cineva timp sa se uite peste sursa mea si sa imi dea un exemplu pe care nu merge?
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #28 : August 12, 2008, 22:06:45 » |
|
Nu ştiu unde ai folosit deque. Se poate şi fără.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•miculprogramator
|
|
« Răspunde #29 : Iulie 18, 2009, 22:00:40 » |
|
Fara dinamica/greedy nu se poate? Merita incercat un brute ?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #30 : Iulie 19, 2009, 00:03:01 » |
|
Nu prea sunt probleme pe infoarena care sa mearga cu brute .
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•Marius
|
|
« Răspunde #32 : Iulie 19, 2009, 14:09:04 » |
|
Fara dinamica/greedy nu se poate? Merita incercat un brute ? Pentru ca unul să joace cât mai bine, celălalt trebuie să joace cât mai prost. Ţin minte că jucând cât mai prost am reuşit să rezolv foarte uşor problema cu Greedy.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•miculprogramator
|
|
« Răspunde #33 : Iulie 19, 2009, 15:46:33 » |
|
Eu m-am gandit sa sortez caii crescator. Compar primul cal al lui Gigel cu armasarul lui Ionel. Daca este mai mare Gigel +200,daca este egal 0, daca este mai mic -200. Si asa aflu profitul lui Gigel. Nu cred ca este varianta cea mai optima,dar asta mi-a venit in minte. Eu Greedy si dinamica nu stiu...
|
|
|
Memorat
|
|
|
|
•c_e_manu
|
|
« Răspunde #34 : Iulie 19, 2009, 23:09:11 » |
|
Nu cred ca e chiar corect ce ai spus tu, dar sa stii ca modalitatea ta de rezolvare e o tehnica greedy. Pe scurt in asta consta greedy: alegerea variantei optime (ce pare optima) la fiecare pas si de multe ori sortezi intr-un anumit mod datele. Sper ca nu m-am bagat in seama degeaba Bafta! PS:Esti fana LP?
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #35 : Iulie 20, 2009, 08:11:48 » |
|
Mersi pentru indicatii. O sa revin la problema asta dupa ce citesc cate ceva despre greedy. P.S: Linkin Park rocks.
|
|
|
Memorat
|
|
|
|
•Patrunjelu
Strain
Karma: 2
Deconectat
Mesaje: 18
|
|
« Răspunde #36 : Martie 20, 2011, 17:44:44 » |
|
Hi, thread necromancer here. All jokes aside, asta-i rezolvarea mea: #include <stdio.h> #include <algorithm> using namespace std; const long infi = 2147483647; long t, n, suma;
long caiA[1010]; long caiB[1010];
int main() { freopen("cai.in", "r", stdin); freopen("cai.out", "w", stdout); scanf("%d", &t); bool fweaker; bool fequal; int retinequal; int retincmm; for (int i = 0; i < t; ++i) { suma = 0; scanf("%d", &n); for (int j = 0; j < n; ++j) //Citim caii lui gigel { scanf("%d", &caiA[j]); } for (int j = 0; j < n; ++j) //Si caii lui ionel { scanf("%d", &caiB[j]); } sort(caiA, caiA + n); //Ordine crescatoare sort(caiB, caiB + n); //Ordine crescatoare for (int j = 0; j < n; ++j) //Pentru fiecare cal de-al lui Gigel, pornind de la cel mai slab { fequal = false; //Presupunem ca nu poate face remiza cu nici un cal de la Ionel fweaker = false; //Presupunem ca nu exista cal de-al lui Ionel mai slab decat calul curent de la Gigel retinequal = 0; //Retine pozitia pe care se afla calul cu care poate face remiza retincmm = -1; //Retine pozitia celui mai puternic cal de la Ionel. La fiecare cursa, presupunem ca nu am gasit inca for (int q = n-1; q >= 0; --q) //Pentru fiecare cal de-al lui Ionel, de la cel mai puternic in jos { if (caiA[j] > caiB[q]) //Daca calul curent al lui Gigel il poate bate pe cel al lui Ionel { suma += 200; //Marim suma deoarece a obtinut o victorie caiB[q] = infi; //Calul curent al lui Ionel a fost invins (nu va mai concura) fweaker = true; //Am gasit un cal mai slab decat al lui Gigel break; //Oprim for-ul } else //Altfel { if ((caiA[j] == caiB[q]) && (fequal == false)) //Daca puterea celor doi este identica si nu am gasit inca o astfel de pereche { fequal = true; //Mentionam ca am gasit o pereche retinequal = q; //Retinem pozitia pe care se afla calul pt. remiza @ Ionel } else //Altfel, calul lui este mai puternic decat al lui gigel { if ((caiB[q] != infi) && (retincmm == -1)) //Daca calul nu a participat deja la curse si nu am gasit deja un cal mai puternic la Gigel retincmm = q; //Retinem pozitia pe care se afla calul cel mai puternic } } } //Gata for-ul if (fweaker == false) { if ((fequal == true) && (retincmm == -1)) //Daca putem face remiza { caiB[retinequal] = infi; //Facem //continue; } else { //altfel... suma-=200; caiB[retincmm] = infi; //Si il scoatem din joc pe cel mai puternic cal de-al lui Ionel } } } printf("%d\n", suma); } return 0; } Mai exact, eu sortez crescator caii (retinuti in 2 siruri) si incepand cu primul cal al lui Gigel (cel mai slab), verific cu fiecare cal de-al lui Ionel (incepand cu cel mai puternic -> parcurg descrescator) care-i situatia. Fiecare cal de-al lui Gigel incearca sa bata un cal cat mai puternic de la Ionel. Daca nu poate asta, atunci il scoate pe cel mai puternic cal de-al lui Ionel din joc (din multimea de cai care nu au participat inca la curse), pentru a face viata mai usoara cailor ce urmeaza. Daca cumva nu poate bate un cal si nici nu-i unul mai puternic disponibil, face remiza. infi marcheaza un cal care a participat deja la cursa. Pe toate exemplele mele da bine. La fel si pe cele de pe forum. Nu prea imi vine nimic in minte in momentul asta. In caz ca e cineva de pe aici dispus sa se uite la vechile surse de 100p pentru mine, ar fi super Sau daca greseala mea se observa usor, astept sugestii.
|
|
|
Memorat
|
|
|
|
•Master011
Strain
Karma: 1
Deconectat
Mesaje: 2
|
|
« Răspunde #37 : Martie 31, 2013, 14:13:33 » |
|
Cat de mare poate sa fie T-ul (numarul de teste)?
|
|
|
Memorat
|
|
|
|
•Schumi
Client obisnuit
Karma: 36
Deconectat
Mesaje: 74
|
|
« Răspunde #38 : Aprilie 01, 2013, 13:17:29 » |
|
Numarul de teste nu influenteaza in nici un fel algoritmul de rezolvare
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #39 : Aprilie 01, 2013, 13:38:01 » |
|
Conteaza, daca vrei sa stii ca algoritmul tau are complexitatea buna. T <= 20, am completat si enuntul.
|
|
|
Memorat
|
Am zis
|
|
|
•Master011
Strain
Karma: 1
Deconectat
Mesaje: 2
|
|
« Răspunde #40 : Aprilie 04, 2013, 11:06:03 » |
|
Mersi mult Eu stiu sa fac problema in O(T*n^2) dar este cam la limita... care este complexitatea buna?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #41 : Aprilie 04, 2013, 12:31:01 » |
|
Da, e ok.
|
|
|
Memorat
|
Am zis
|
|
|
•andreiiii
|
|
« Răspunde #42 : Decembrie 15, 2013, 18:29:36 » |
|
Testul nu este suficient de bun. Iau 100 dar pe testul: 2 20 20 20 30 imi da 0 , ar trebui sa-mi dea -200.
|
|
|
Memorat
|
|
|
|
|
•xtreme77
Client obisnuit
Karma: 7
Deconectat
Mesaje: 69
|
|
« Răspunde #44 : Septembrie 24, 2014, 21:34:34 » |
|
Nu cred ca ai vreo sansa sa scoti problema asta de 100 cu o complexitate mai buna de O ( n ^ 2 ) . Poti incerca o varianta cu dinamica sau o varianta cu un greedy care se vrea a fi mai degraba un brut. Numai bine si succes . Solutia oferita de tine nu cred ca este optima . Cred ca greseala e la nivelul conceptual,nu la nivelul care tine de implementare.
|
|
|
Memorat
|
|
|
|
•andrei.arnautu
Client obisnuit
Karma: 9
Deconectat
Mesaje: 58
|
|
« Răspunde #45 : Noiembrie 30, 2014, 02:52:04 » |
|
Frumoasa problema!
|
|
« Ultima modificare: Noiembrie 30, 2014, 03:10:10 de către Arnautu Andrei »
|
Memorat
|
|
|
|
|