Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Concurenta intre femei

Constructie casa Dumbravita

Soluționarea problemei intre...

Telefon pentru un adolescent pana...
 rundll32 , problema windows 10

Acoperis tabla Evertile

Lia Olguța Vasilescu: ”...

Schema VU-metru pentru dc-7g3hwa
 Ungaria lui Orban - procedura de ...

nu merge se intalez pe partitie

"Superweapon-ul" romanesc...

Colecție carți religioa...
 Exemple de job postings de progra...

Atestat

Pasaport expirat.

Cerere modificare aplicatie apk
 
Forumul Softpedia folosește "cookies" pentru a oferi utilizatorilor o experiență completă. Vezi detalii sau închide mesaj (x)

Problem„ secvenț„

  • Please log in to reply
19 replies to this topic

#1
Baggins

Baggins

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130
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: Moderators
  • Posts: 21,569
  • Înscris: 24.02.2007
  • ID membru: 146,987
Raspuns gresit sau ai depasit timpul?

#3
Baggins

Baggins

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130
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,596
  • Înscris: 22.02.2009
  • ID membru: 422,002
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

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130
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,596
  • Înscris: 22.02.2009
  • ID membru: 422,002
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

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130
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,596
  • Înscris: 22.02.2009
  • ID membru: 422,002
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

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130
#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,596
  • Înscris: 22.02.2009
  • ID membru: 422,002
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

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130
#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,596
  • Înscris: 22.02.2009
  • ID membru: 422,002
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

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130
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,596
  • Înscris: 22.02.2009
  • ID membru: 422,002
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

    Guru Member

  • Grup: Moderators
  • Posts: 15,775
  • Înscris: 10.08.2005
  • ID membru: 43,530
  • Locație: Iasi

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,596
  • Înscris: 22.02.2009
  • ID membru: 422,002
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

    Guru Member

  • Grup: Moderators
  • Posts: 15,775
  • Înscris: 10.08.2005
  • ID membru: 43,530
  • Locație: Iasi
Exprima-l in pseudocod, sa vedem daca @OP reuseste sa-l inteleaga

#18
Baggins

Baggins

    Junior

  • Grup: Members
  • Posts: 70
  • Înscris: 09.10.2014
  • ID membru: 882,130

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


0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users