681 Numar2

[•DITzoneC]

Aici puteţi discuta despre problema Numar2.

[•anna_bozianu]

Am trimis 2 surse cu care luam 100 p pe evaluatoarele OJI si ..hopa. Zero. La ambele. Dupa care am vazut ca de fapt doar numele problemei era putin modificat.
Of neatentia asta. 

[•MciprianM]

Eroare de compilare in evaluator:
user.cpp:12: warning: this decimal constant is unsigned only in ISO C90
user.cpp: In function 'int main()':
user.cpp:9: warning: comparison between signed and unsigned integer expressions
user.cpp:12: error: reference to 'min' is ambiguous
user.cpp:4: error: candidates are: long unsigned int min
/usr/include/c++/4.2/bits/stl_algobase.h:226: error:                 template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
/usr/include/c++/4.2/bits/stl_algobase.h:182: error:                 template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
user.cpp:12: error: reference to 'min' is ambiguous
user.cpp:4: error: candidates are: long unsigned int min
/usr/include/c++/4.2/bits/stl_algobase.h:226: error:                 template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
/usr/include/c++/4.2/bits/stl_algobase.h:182: error:                 template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
user.cpp:13: warning: comparison between signed and unsigned integer expressions
user.cpp:14: warning: comparison between signed and unsigned integer expressions
user.cpp:14: error: reference to 'min' is ambiguous
user.cpp:4: error: candidates are: long unsigned int min
/usr/include/c++/4.2/bits/stl_algobase.h:226: error:                 template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
/usr/include/c++/4.2/bits/stl_algobase.h:182: error:                 template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
user.cpp:14: error: reference to 'min' is ambiguous
user.cpp:4: error: candidates are: long unsigned int min
/usr/include/c++/4.2/bits/stl_algobase.h:226: error:                 template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
/usr/include/c++/4.2/bits/stl_algobase.h:182: error:                 template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
user.cpp:15: error: reference to 'min' is ambiguous
user.cpp:4: error: candidates are: long unsigned int min
/usr/include/c++/4.2/bits/stl_algobase.h:226: error:                 template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
/usr/include/c++/4.2/bits/stl_algobase.h:182: error:                 template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)



L.E. Era de la mine...

[•Robytzza]

si mie imi dadea uneori eroare asta cand mai puneam si using namespace std

[•razvanelu99]

am trimis aceeasi sursa cu care am luat 100P la oji. aici iau doar 80p. ce se intampla cu testele 1 si 3? iau "wrong answer" pe ele. sunt niste cazuri particulare?

[•gabitzish1]

Testele sunt aceleasi ca si la OJI. Sursa ta probabil nu e aceeasi pentru ca am verificat'o pe testele 1 si 3, si chiar afisaza raspunsuri gresite.

[•Omega91]

Salutare, am luat 100 pct la aceasta problema, desi la ultimul exemplu primesc segv pe calc de acasa. Curios ca in problema apare acel exemplu, dar in teste nu am vazut nr asa de mari. Pacat ca nu sunt si la oni teste asa de lejere

[•alexandru92]

Chiar nu pot sa-mi dau seama unde gresesc, cred ca este de la back dar nu inteleg de ce 

Cod:

#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

/*
 *
 */
using namespace std;
ofstream gdb( "debug.txt" );
int N, M, k, sign;
vector< int > v,  pr;
int f( int x )
{
	int i, s;
	const int Npr=pr.size();
	for( i=s=0; i < Npr; s+=x/pr[i], ++i );
	return s;
}
int search( int left, int right )
{
	int middle, M2;
	while( left <= right )
	{
		middle=left+(right-left)/2;
		M2=f( middle );
		if( M2 == M )
			return middle;
		if( M2 >= M )
			right=middle-1;
		else left=middle+1;
	}
	return -1;
}
inline void back( int l, int last, int p )
{
	if( l == k )
		pr.push_back(sign*p);
	else for( int i=last+1; i <= N-k+l; ++i )
			if( p*v[i] <= M*v[0] )
				back( l+1, i, p*v[i] );
			else break;
}
int main( void )
{
	int x;
	ifstream in( "numar2.in" );
	in>>N>>M;
	//gdb<<N<<' '<<M<<'\n';
	copy( istream_iterator<int>(in), istream_iterator<int>(), back_inserter(v) );
	//copy( v.begin(), v.end(), ostream_iterator<int>( gdb, " " ) );
	//gdb<<'\n';
	for( sign=1, k=1; k < N; ++k, sign*=-1 )
		back( 0, -1, 1  );
	//copy( pr.begin(), pr.end(), ostream_iterator<int>( gdb, " " ) );
	//gdb<<'\n';
	x=search( 1, M*v[0] );
	//gdb<<x<<'\n';
	for( ; x; --x )
		for( k=0; k < N; ++k )
			if( 0 == x%v[k]  )
			{
				ofstream out("numar2.out" );
				out<<x;
	//			gdb<<x;
				return EXIT_SUCCESS;
			}
	return EXIT_SUCCESS;
}

[•chibicitiberiu]

Sooper faina problema... 100 pct din prima sursa trimisa
Ma mir ca e foarte foarte simpla. Mi-a luat vreo 20 minute sa o rezolv + debugging.

[•DanceKriss]

folosind un AVL actualizat pas cu pas.... iar apoi o parcurgere SRD ce complexitate pe cel mai rau caz se obtine ?
 

[•romircea2010]

poate nu imi dau eu seama dar nu cred ca numarul 14 apartine sirului b la exemplul unu.

[•PlayLikeNeverB4]

14 e multiplu al lui 2.

[•romircea2010]

ok, mersi, nu citisem cu atentie, credeam ca elementele din sirul b trebuie sa fie produse de numere prime din sirul a.

[•NaSa]

De ce nu ati lasat timpul de 1sec/test de la oji 2008?

[•soriyn]

La problema asta ar merge refacut un test si eventual grupat cu altele. E destul de aiurea sa se ia 100 cu un algoritm similar ciurului. Adica mie mi se pare bulaneala. Beleaua e ca un astfel de algoritm obtine timpi mai buni decat solutia oficiala(cel putin implementarea mea)