505. Cwany Lutek [CWANY_LU]

[bunker96]

Witam,
Proszę was o wszelkie metody optymalizacji algorytmy do tego zadania: http://pl.spoj.com/problems/CWANY_LU/
Na chwilę obecną skrypt przekracza czas i dostaje 0 punktów.
Oto kodzik:

unsigned long long int k,n,wynik;
int silnia(int n)
{
    if(n==0) return 1;
    else return n*silnia(n-1);
}
int main(){
    if(n<2||k>n||k==0)
        cout<<'N'<<endl;
    else
    {
        wynik=1;
        for(int i=k+1;i>0;i--,n--)
        {
            wynik*=n;
        }
        wynik/=silnia(k);
        wynik%=2;
        if(wynik)
            cout<<'N'<<endl;
        else
            cout<<'P'<<endl;
    }
    
}

Za wszelką pomoc jak zawsze bardzo dziękuję.

[narbej]

1. Jak nie musisz, nie używaj zmiennych globalnych.
2. TESTUJ swoje programy!
3. Próbuj samodzielnie rozwiązywać problemy. Po zrobieniu takiego jak powyżej knotu [kodu] nie proś od razu o pomoc na forum lecz goto 1
4. Jak już poprawisz swój ten tutaj kod, to prawdopodobnie? będziesz miał TLE dla wszystkich testów lub dla większości.
5. Narysuj [napisz] sobie, w miarę duży, trójkąt paskala.
6. Myśl jak programista
7. Kombinuj i bądź cwaniszy od lutka.

PS
Raczej zanim nastąpi TLE, to wcześniej przepełni i wyleje się na klawiaturę zawartość stosu systemowego, popatrz:
http://ideone.com/OErUjn

[bunker96]

Pomijając fakt, że nie wczytałem danych wejściowych zauważyłem już, że skrypt jest niestety zbyt słaby aby sobie poradzić. Wiem zbyt szybko się poddałem, zamiast pomyśleć napisałem cokolwiek i wysłałem.
Trójkąt Paskala powiadasz hmmm coś mi się rzuciło w oczy przy jak patrzyłem na grafikach google tabelkę z kombinacjami.
I dzięki za radę z tymi zmiennymi globalnymi

[narbej]

Dobrze, że nie masz pytań do tego zadania
POdpowiadając chodziło mi o wariant trójkąta - trójkąt Sierpińskiego i rekurencyjne przetwożenie go.
Drugi sposób, ale nie informatyczny, to wzór i podstawianie do niego danych, czyli sposób czysto matematyczny. Niestety nie mogę znaleźć ani sobie przypomnieć gdzie go znalazłem ;-(

PS
Nie rób tak na przyszłość. Nie edytuj w taki sposób swojego wcześniejszego postu i w taki sposób jak to widzę, że zrobiłeś
Edytuj, tylko aby poprawić jakieś jaskrawe błędy lub aby usunąć kod. Teraz twoje poprawki są jeszcze gorsze, trzeba było to zostawić albo po prostu skasować tamten kod. Nikt nie będzie wracał i sprawdzał co tam dopisałeś czy pozmieniałeś. Po prostu powinieneś napisać nowy post
Tylko przypadkiem tam zaglądnąłem i ....

[bunker96]

Dzięki narbej. Rozumiem, że dla n=1000 k=250 mam szukać w wierszu 1001 250-ej pozycji trójkąta pascala aby sprawdzić jaka to liczba. Ale jak sprawdzić jaka to liczba? Czy może nie trzeba sprawdzać jaka to liczba?

[narbej]

Jak napisałem wcześniej/wyżej, rozwiązanie O(1), to właśnie taki wzór, ale nie potrafię Ci go objaśnić. Drugi sposób to przeglądnięcie/przetworzenie trójkąta Sierpińskiego.
A więc ani w jednej metodzie, ani w drugiej nie interesuje Cię wartość [jaka to liczba]. Bo zrozumiałem, że chcesz policzyć tą liczbę, a potem sprawdzić, czy jest parzysta, czy nie? Nie to nie tędy droga.

TRÓJKĄT SIERPIŃSKIEGO
"Ziarno", atom:
N
NN
NPN
NNNN

Każdynastępny poziom, powstaje z odpowiedniego dostawienia trójkątów z bieżącego poziomu i wypełnienie pustego miejsca pomiędzy parzystymi:
1. DOSTAWIENIE LEWEGO:
N
NN
NPN
NNNN
N
NN
NPN
NNNN
2. wypełnienie:
N
NN
NPN
NNNN
NPPP
NNPP
NPNP
NNNN

1. dOSTAWIENIE PRAWEGO
   N
   NN
   NPN
   NNNN
   NPPPN
   NNPPNN
   NPNPNPN
   NNNNNNNN

Jeżeli wiesz jak się konstruuje trójkąt, to robisz w odrotnym kierunku:
Nie musisz rysować całego.
Wysokość ziarna = 4 [od 0 do 3]
poziom 1 = 8
poz 2 - 16
i kolejno: 32 64 128 256 512 1024

I teraz robisz rekurencyjnie:
Jeżeli n < 4 to potrafisz odpowiedzieć
else kombinujesz ewentualnie odpowiednio zmniejszasz n i sprawdzasz k

PS
Porysuj sobie mniejsze trójkąty i pokombinuj.
PS 2
Uwzględnij też [potem] podpowiedzi w komentarzach pod zadaniem, oraz pamiętaj, że (8 nad 5) = (8 nad 3)

[bunker96]

Dobra jak narysowałem trójkąt tak do 2 poziomu załapałem o co chodzi. Dzięki.