Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Wc Geberit

Routere detinute in trecut si in ...

Teii din fața casei

E-Mail in serie prin Excel si Out...
 Modul alimentare rulou/jaluzea ex...

Recuperare fișiere dupa form...

Aplicatii stress test RAM

Asigurare auto hibrid
 Asus B550M - PC-ul nu porneste di...

Tzanca Uraganu - Inconjurat de Fe...

explicatie montaj breadboard

3 Doors Down - Kryptonite
 Semnalizati cand virati pe un dru...

Succesiune - mostenire apartament...

Donez Siofor de 1000mg ( diabet t...

Izolatie intre parter si etaj
 

Problemã secvențã

- - - - -
  • Please log in to reply
19 replies to this topic

#1
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
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.


#2
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,189
  • Înscris: 24.02.2007
Raspuns gresit sau ai depasit timpul?

#3
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
Răspuns greșit la al doilea test și "Caught fatal signal 11" la restul.

#4
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
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
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
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
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
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
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
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
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
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
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
#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
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
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
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
#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
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
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
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014
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
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
Nu degeaba ti-am cerut sa detaliezi ce se executa.

View PostBaggins, on 20 martie 2017 - 23:24, said:

i++ => i=2
i=2 nu mai verifică i<n
Intre cele 2 chestiuni se mai executa ceva. Acel ceva genereaza un OOB.

#15
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005

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.
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

#16
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
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
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
Exprima-l in pseudocod, sa vedem daca @OP reuseste sa-l inteleaga

#18
Baggins

Baggins

    Member

  • Grup: Members
  • Posts: 264
  • Înscris: 09.10.2014

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
corect, în mare parte, asta fac și eu

Quote

Intre cele 2 chestiuni se mai executa ceva. Acel ceva genereaza un OOB.
Am văzut și eu la debug că se execută ceva în gol, n-am știut ce, dar am observat.
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

Chirurgia cranio-cerebrală minim invazivă 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

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate