Krokodyle

[HardCoreXPL]

Witam,

Czy może mi ktoś wyjaśnić jak zrobić to zadanie?

http://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/kro/

Dzięki :P

[Sopelek997]

Poziomem nazwijmy linie poziomych ścieżek.

Skrzyżowaniem nazwijmy skrzyżowanie się pionowej i poziomej ścieżki.

Na każdym poziomie możesz przemieścić się do jednego z a+1 możliwych skrzyżowań i przejść na kolejny poziom.

W trakcie przechodzenia do ostatniego poziomu miniemy b takich skrzyżowań.

Łącznie mamy więc

(a+1)^b możliwości przejścia na koniec.

 

Naiwny algorytm potęgowania powinien być wystarczająco szybki, jednak gdybyś chciał to możesz to zoptymalizować. Dwa podejścia masz przedstawione pod tym linkiem.

https://en.wikipedia.org/wiki/Modular_exponentiation

[HardCoreXPL]

Dobra takie coś już miałem ale przy takim kodzie

cout<<((2+1)^100)%10000;

zwraca wartość 103 a nie 2001 i to mi się tutaj nie zgadza. Chyba że coś pomyliłem

[Sopelek997]

bo ^ to nie jest operator potęgowania w C++

[HardCoreXPL]

Hehe zacmienia mozgu dostalem dzieki