Chirurgia cranio-cerebrală minim invazivă
Tehnicile minim invazive impun utilizarea unei tehnologii ultramoderne. Endoscoapele operatorii de diverse tipuri, microscopul operator dedicat, neuronavigația, neuroelectrofiziologia, tehnicile avansate de anestezie, chirurgia cu pacientul treaz reprezintă armamentarium fără de care neurochirurgia prin "gaura cheii" nu ar fi posibilă. Folosind tehnicile de mai sus, tratăm un spectru larg de patologii cranio-cerebrale. www.neurohope.ro |
Problemã secvențã
Last Updated: Mar 21 2017 17:54, Started by
Baggins
, Mar 13 2017 17:46
·
0
#1
Posted 13 March 2017 - 17:46
Pentru problema aceasta obțin doar 10p. Care ar fi problema?
#include <iostream> #include <fstream> using namespace std; /**< Cerința Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2^k, unde k este un număr natural dat. Date de intrare Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații. Date de ieșire Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k. Restricții și precizări 1 ≤ n ≤ 500.000 1 ≤ k ≤ 10.000 numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 10^18 */ ifstream f("memory006.in"); ofstream g("memory006.out"); void Citire(long long x[], unsigned n) { for (unsigned i = 0; i < n; i++) f >> x[i]; } bool isPowerOf2(long long n) { return (n != 0) && ((n & (n - 1)) == 0); } unsigned Secv(long long x[], unsigned n, unsigned k) { long long produs; unsigned i = 0, nr = 0; while (i < n) { while (!isPowerOf2(x[i]) && i < n) i++; // start=i produs = 1; while (isPowerOf2(x[i]) && i < n) { produs *= x[i]; if (produs == k) { nr++; break; } i++; } // stop=i-1; } return nr; } int main() { long long* x; unsigned n, k; f >> n >> k; x = new long long[n]; Citire(x, n); unsigned p = 2; while (--k) p *= 2; unsigned S = Secv(x, n, p); g << S; delete x; f.close(); g.close(); return 0; } Edited by Baggins, 13 March 2017 - 17:47. |
#3
Posted 13 March 2017 - 22:16
Răspuns greșit la al doilea test și "Caught fatal signal 11" la restul.
|
#4
Posted 14 March 2017 - 11:12
Cateva intrebari ajutatoare.
1. Cum functioneaza programul tau pentru k>18. 2. Ce se intampla daca ultimul element din sir nu este putere a lui 2? |
#5
Posted 14 March 2017 - 14:45
1. Corect. Am modificat p-ul de la unsigned la long long.
2. Nimic, îl sare. Edited by Baggins, 14 March 2017 - 14:45. |
#6
Posted 14 March 2017 - 15:34
N-am fost atent la scriere si ma gandeam la 10^18. Prima intrebare ramane valabila, dar cu o mica modificare.
1. Ce se intampla in cazul in care k>=64? 2. Te rog sa faci debug si sa vezi ce se intampla. Pune un breakpoint imediat dupa linia: produs = 1;. Al doilea while avanseaza i-ul pana la n, doar ca dupa aia faci o alta verificare in al treilea while. Iar compilatoarele executa comenzile intr-o anumita ordine. Asadar, prima data va fi evaluata expresia: isPowerOf2(x[i]), pentru i=n. Mie mi se pare un caz clasic de OOB. |
#7
Posted 14 March 2017 - 16:04
Am remediat problema lucrând doar cu exponenții lui 2.
#include <iostream> #include <fstream> #include <cmath> using namespace std; /**< Cerința Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2^k, unde k este un număr natural dat. Date de intrare Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații. Date de ieșire Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k. Restricții și precizări 1 ≤ n ≤ 500.000 1 ≤ k ≤ 10.000 numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 10^18 */ ifstream f("memory006.in"); ofstream g("memory006.out"); void Citire(long long x[], unsigned n) { for (unsigned i = 0; i < n; i++) f >> x[i]; } bool isPowerOf2(long long n) { return (n != 0) && ((n & (n - 1)) == 0); } unsigned Secv(long long x[], unsigned n, unsigned k) { unsigned i = 0, nr = 0, exponent; while (i < n) { while (!isPowerOf2(x[i]) && i < n) i++; // start=i exponent = 0; while (isPowerOf2(x[i]) && i < n) { exponent += log2(x[i]); if (exponent == k) { nr++; break; } i++; } // stop=i-1; } return nr; } int main() { long long* x; unsigned n, k; f >> n >> k; x = new long long[n]; Citire(x, n); unsigned S = Secv(x, n, k); g << S; delete x; f.close(); g.close(); return 0; } I-am făcut debug și merge cum l-am gândit eu să meargă. Este vreun caz în care nu face ceea ce ar trebui? Acum obțin 0p. edit: am înțeles la ce te referi, modific Edited by Baggins, 14 March 2017 - 16:16. |
#8
Posted 14 March 2017 - 16:38
Mi-e greu sa ma gandesc la toate scenariile fara pix si foaie. Dar aparent tu mai scapi de niste cazuri, de exemplu pentru secventa 2 2 2 2 2 2 si k=4, raspunsul trebuie sa fie 3. Banuiesc ca tu intorci 1. O alta problema pare a fi pentru sirul 4 4 4 4 4 4 2 si k=3 unde cred ca raspunsul tau este 0 si ar trebui sa fie 1.
|
#9
Posted 14 March 2017 - 17:12
#include <iostream> #include <fstream> #include <cmath> using namespace std; /**< Cerința Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2^k, unde k este un număr natural dat. Date de intrare Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații. Date de ieșire Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k. Restricții și precizări 1 ≤ n ≤ 500.000 1 ≤ k ≤ 10.000 numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 10^18 */ ifstream f("memory006.in"); ofstream g("memory006.out"); void Citire(long long x[], unsigned n) { for (unsigned i = 0; i < n; i++) f >> x[i]; } bool isPowerOf2(long long n) { return (n != 0) && ((n & (n - 1)) == 0); } unsigned Secv(long long x[], unsigned n, unsigned k) { unsigned i = 0, nr = 0, exponent, lungSecv; while (i < n) { while (!isPowerOf2(x[i]) && i < n) i++; // start=i lungSecv=0; exponent = 0; while (isPowerOf2(x[i]) && i < n) { exponent += log2(x[i]); if(exponent == k) nr++; lungSecv++; i++; } // stop=i-1; i-=lungSecv-1; } return nr; } int main() { long long* x; unsigned n, k; f >> n >> k; x = new long long[n]; Citire(x, n); unsigned S = Secv(x, n, k); g << S; delete x; f.close(); g.close(); return 0; } Aici parcurg toate secvențele. Tot 0p primesc cu eroarea "Exited with error status 127". Habar n-am de la ce. Îmi poți sugera o altă metodă de a aborda problema, mai eficientă? Edited by Baggins, 14 March 2017 - 17:12. |
#10
Posted 14 March 2017 - 17:31
Tot n-ai corecat OOB-ul de care vorbeam. Conditiile se executa intr-o ordine, iar eventual unele sunt sarite.
Foloseste un alt contor pentru al 3-lea switch pe care evident il initializezi cu i. In plus n-ai rezolvat cazul Quote O alta problema pare a fi pentru sirul 4 4 4 4 4 4 2 si k=3 unde cred ca raspunsul tau este 0 si ar trebui sa fie 1. |
|
#11
Posted 19 March 2017 - 00:43
#include <iostream> #include <fstream> #include <cmath> using namespace std; /**< Cerința Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2^k, unde k este un număr natural dat. Date de intrare Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații. Date de ieșire Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k. Restricții și precizări 1 ≤ n ≤ 500.000 1 ≤ k ≤ 10.000 numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 10^18 */ ifstream f("memory006.in"); ofstream g("memory006.out"); void Citire(long long x[], long n) { for (long i = 0; i < n; i++) f >> x[i]; } bool isPowerOf2(long long n) { return (n != 0) && ((n & (n - 1)) == 0); } unsigned Secv(long long x[],long n,long k) { long i=0,nr=0,expSum,exp,start; while(i<n) { while(!isPowerOf2(x[i]) && i<n) i++; start=i; expSum=0; while(isPowerOf2(x[i]) && i<n) { exp=log2(x[i]); expSum+=exp; if(expSum==k) { nr++; i=start+1; break; } if(expSum>k) { i=start+1; break; } i++; } } return nr; } int main() { long long* x; long n, k; f >> n >> k; x = new long long[n]; Citire(x, n); unsigned S = Secv(x, n, k); g << S; delete x; f.close(); g.close(); return 0; }Funcționează pentru toate cazurile acum. Nu am înțeles încă ce nu e ok, despre ce ordine a instrucțiunilor este vorba. Edited by Baggins, 19 March 2017 - 01:01. |
#12
Posted 20 March 2017 - 17:44
N-am vazut ca ai raspuns.
Problema este aici: while(!isPowerOf2(x[i]) && i<n) i++;Hai sa luam un caz simplu, n=2, k=4, sirul: 3 3 Te rog sa identifici si sa precizezi tot ceea ce executa calculatorul, stiind ca i=0 este starea initiala (inainte ca acest cod sa fie executat). Doresc de la tine pasi sparti pe bucatele cat mai mici, folosind doar ceea ce ai aici. Este foarte probabil ca pentru acest cod sa nu ai probleme grave (SIGSEV) insa exista un OOB clar. |
#13
Posted 20 March 2017 - 23:24
i=0
intră-n primul while, intră-n al doilea while x[0] = 3 nu e putere a lui 2 => i++ => i=1 x[1] = 3 nu e putere a lui 2 => i++ => i=2 i=2 nu mai verifică i<n => iese din al doilea while nu intră-n al treilea while pentru că nu e îndeplinită i<n iese din primul while |
#14
Posted 21 March 2017 - 10:29
#15
Posted 21 March 2017 - 10:31
Quote Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2^k, unde k este un număr natural dat. 7 4 2 4 5 -- daca tot verifici numerele (powerof2), poti sa extragi doar exponentul daca este valid -1 2 1 2 -1 astfel, problema nu mai tine de inmultire, ci de adunare |
|
#16
Posted 21 March 2017 - 11:35
Daca tot vorbim de optimizari, atunci ar fi trebuit sa faca cu 2 contori. Nu e nevoie sa adunam toti exponentii de fiecare data. Sigur, algoritmul este putin mai complicat decat sa faci un for care sa adune tot intre 2 limite, dar nici pe departe a fi complicat per se.
|
#17
Posted 21 March 2017 - 12:51
Exprima-l in pseudocod, sa vedem daca @OP reuseste sa-l inteleaga
|
#18
Posted 21 March 2017 - 15:21
Quote
5 3 7 4 2 4 5 -- daca tot verifici numerele (powerof2), poti sa extragi doar exponentul daca este valid -1 2 1 2 -1 astfel, problema nu mai tine de inmultire, ci de adunare Quote
Intre cele 2 chestiuni se mai executa ceva. Acel ceva genereaza un OOB. Acum întrebarea mea este: în condiții de admitere, se pune o asemenea problemă? Până la urmă, problema îmi scoate output-ul corect. Înțeleg, parțial, și de ce nu obțin punctaj pe pbinfo, dar nu mă deranjează cât timp am rezolvat problema. Am abordat problema asemănător cum au abordat ei o problemă cu secvență din baremul de aici de la admiterea de anul trecut, tot cu 3 while-uri. Edited by Baggins, 21 March 2017 - 15:42. |
Anunturi
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users