Weboldalunk cookie-kat használhat, hogy megjegyezze a belépési adatokat, egyedi beállításokat, továbbá statisztikai célokra és hogy a személyes érdeklődéshez igazítsa hirdetéseit. További információ
Kezdőoldal » Számítástechnika » Programozás » Szöveges feladat megoldás?

Szöveges feladat megoldás?

Figyelt kérdés

Egy folyó partján állunk, amin sziklákon ugrálva akarunk átkelni. N darab (1 <= N <= 80 000) szikla van a vízben és maximum 1 sziklát vagyunk képesek átugrani (tehát az i-edik szikláról az i+1 vagy i+2 sziklára ugorhatunk). K darab (0 <= K <= N) szikla nagyon csúszik, ezekre nem ugorhatunk.

Adott az N szám és egy K elemű tömb, ami a csúszós sziklák indexét tartalmazza (1-gyel kezdődő indexeléssel).

Hányfélekeppen juthatunk át a túlpartra?

Az eredményt modulo 1000000007 adja meg!


Először azt gondoltam, hogy ez egy sima kombinatorikai formulával kiszámolható (bár gondolom a tanár akkor sem arra lenne kiváncsi), de a csúszós sziklák bekavarnak, nem tudom hogy kéne megcsinálni.



okt. 1. 19:33
1 2
 11/17 anonim ***** válasza:
100%
Miről beszélsz 10-es?
okt. 2. 07:28
Hasznos számodra ez a válasz?
 12/17 anonim ***** válasza:

Lehet teljesen mas modszernek erti azt, ha Pythonban csak a vegen veszed a modulot?

De csinalhatod ott is pontosan ugyanugy, mint pl. C++-ban.

Hogy erted #10?

okt. 2. 08:51
Hasznos számodra ez a válasz?
 13/17 anonim ***** válasza:
70%

Van egy válaszoló aki a hasonló algoritmikus kérdésekhez mindig beírja az alábbiak valamelyikét, vagy ezek valamilyen kombinációját:

- rossz megoldást

- már megint te?

- nem tudsz guglizni?

- mennyit fizetsz?

- akkor várjuk a megoldást (ezt mindig egy másik válaszolónak)

És közben persze ő nem tudja megoldani a feladatot.

A 2-es biztos ő, lehet a 10-es is.

okt. 2. 10:07
Hasznos számodra ez a válasz?
 14/17 anonim válasza:

#10: ??? Kifejthetnéd bővebben, mert így semmi értelme.


Mindenesetre a megoldás:


from typing import Iterable

MOD = 1000000007

def count_ways(stone_count: int, slippery_stones: Iterable[int]):

last = 1

second_last = 0

for i in range(1, stone_count+2):

if last == second_last and last == 0:

return 0

if i in slippery_stones:

current = 0

else:

current = (last + second_last) % MOD

second_last = last

last = current


return current


Minden kőre annyiféleképp léphetsz, amennyire az őt megelőző, és az azt megelőzőre összesen. Ha egy kő csúszós, akkor 0-féleképp léphetsz rá. Ha egy helyet megelőző két helyre nem juthatsz el, akkor felesleges tovább számolni, nem tudsz átjutni a túloldalra. A feladat szövege nem volt pontos, nem tudjuk, hogy a kövek a partok között vannak-e vagy valamelyik part a szélső kövek egyike-e. (Ezért feltételeztem, hogy a kövek a két part között vannak.) A kombinatorikai formula azért nem egyszerű, mert a csúszós kövek nem "távolíthatóak el" könnyen, hatásuk függ az őt megelőző kövekhez vezető utak számától. Ráadásul, ha iskolai feladatról beszélünk, akkor könnyebb belátni ennek a megoldásnak a helyességét, mint egy bonyolult kombinatorikai feladat megoldását.

okt. 2. 16:11
Hasznos számodra ez a válasz?
 15/17 anonim válasza:

[link]

Utolsó voltam

okt. 2. 16:12
Hasznos számodra ez a válasz?
 16/17 A kérdező kommentje:
Már kaptam tegnap megoldást, de köszi azért ezt is.
okt. 2. 18:12
 17/17 A kérdező kommentje:
Úgy látom ez a modot is rosszul számolja egyébként, 47-nél pl 1778742007-et ad 778742000 helyett.
okt. 2. 18:49
1 2

Kapcsolódó kérdések:





Minden jog fenntartva © 2020, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | WebMinute Kft. | Facebook | Kapcsolat: info@gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!