[C++][Algorytmy] Cwany Lutek - zadanie SPOJ

[Dumel]

nie moge znalezc bledu w moim rozwiazaniu prosciutkiego zadania Cwany Lutek z pl.spoj.pl:
moglibyscie mi wskazac co jest zle w tym kodzie?:

Ukryta treść:    

Kod: Zaznacz cały

//pl.spoj.pl
//zadanie: Cwany Lutek
//zlozonosc obliczeniowa: O(d*lg max(N))
#include <iostream>
using namespace std;
int wykladnik2(int n);

main()
{
ios_base::sync_with_stdio(0);

//dane wejsciowe
int d;                         //ilosc testow
cin>>d;
int* N = new int[d];
int* K = new int[d];
    
for(int i(0); i<d; ++i)
{
  cin>>N[i]>>K[i];
}

//wynik
for(int i(0); i<d; ++i)
{
 if(K>N)
   cout<<"P"<<endl;
 else
 {
 if( wykladnik2(N[i]) > ( wykladnik2(K[i])+wykladnik2(N[i]-K[i]) ) )
   cout<<"P"<<endl;
 else
   cout<<"N"<<endl;
 }
}
delete[] N;
delete[] K;
return(0);
}

//twierdzenie Lagrange'a
int wykladnik2(int n)
{
int w(2);
int wykladnik(0);
while(n/w>=1)
{
wykladnik+=(int)(n/w);
w*=2;
}
return(wykladnik);
}

[spammer]

Siema.

Zrobiłeś jeden malutki błąd

Ukryta treść:    

Kod: Zaznacz cały

//wynik
for(int i(0); i<d; ++i)
{
    if(K[i]>N[i])
   cout<<"P"<<endl;
else
{
   if( wykladnik2(N[i]) > ( wykladnik2(K[i])+wykladnik2(N[i]-K[i]) ) )
   cout<<"P"<<endl;
else
   cout<<"N"<<endl;
}
}

Widzisz już ??:D Pierwszy warunek if źle zrobiłeś dałeś zwykłą zmienną, a powinna być tablica tak jak później.

[Dumel]

dzieki

[doniczek]

wiem że zadanie stare, ale może mi ktoś po króctce wytłumaczyć przedstawione wyżej rozwiązanie albo wskazać jakiś trop ? z góry dzięki

[Dumel]

jedno z twierdzeń Lagrange'a (bardzo łatwe w dowodzie) głosi że:
Liczba pierwsza p wystepuje w rozkładzie na czynniki liczby n! o potędze w wykładniku
\(\displaystyle{ \sum_{k=1}^{\infty}\lfloor \frac{n}{p^k} \rfloor}\)
oczywiście od pewnego miejsca wyrazy szeregu się zerują

[argv]

Ja znalazłem rozwiązanie w czasie stałym

(n | k) == n ? cout << "N" : cout << "P"

Czemu to działa możesz poczytać tu:

[95Villain95]

Witam, siedzę nad tym zadaniem już trochę i usiłuję, niestety bez powodzenia go ogarnąć.Rozumiem, że mógłbym skorzystać ze wzoru na kombinację bez powtórzeń, jednak ciężko by było nie przekroczyć limitu czasu? Wracając do tego sposobu, to czy ktoś może mi krok po kroku wytłumaczyć pracę programu ? Nie rozumiem funkcji z twierdzeniem Lagrange'a(czytałem o tym twierdzeniu, jednak wiele mi to nie dało) i skąd pewność, że jeśli druga liczba będzie większa od pierwszej, to rezultat będzie liczbą parzystą?

-- 3 lut 2015, o 21:14 --

Odświeżam.