Dynamiczna Zabawa Puzzlami – Omówienie zadania

Szczegółowe omówienie zadania Dynamiczna Zabawa Puzzlami:

Link do powyższego omówienia zadania Dynamiczna Zabawa Puzzlami: https://youtu.be/8AyJSrpz7SE?t=1002
Omówienie kodu zadania Dynamiczna Zabawa Puzzlami: https://youtu.be/8AyJSrpz7SE?t=4690

Link do treści zadania Dynamiczna Zabawa Puzzlami: https://szkopul.edu.pl/problemset/problem/dzp/site

Zadanie Dynamiczna Zabawa Puzzlami jest zadaniem na programowanie dynamiczne.

Autorem zadania jest Szymon Hajderek – uczestnik Olimpijskiego Koła Informatycznego.
Bardzo dziękuję!


Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia przygotowujące do Olimpiady Informatycznej: https://oki.org.pl/harmonogram-zajec/

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109


Kod C++ programu Dynamiczna Zabawa Puzzlami, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000*1000 + 7;
const int MOD = 1000*1000*1000 + 7;

// ilePlaski[i] -> na ile sposobow moge ulozyc pasek dlugosci i
// 		tak, ze konczy sie plaskim klockiem
int ilePlaski[MAXN];

// ileDziura[i] -> na ile sposobow moge ulozyc pasek dlugosci i
// 		tak, ze konczy sie dziura
int ileDziura[MAXN];

// ileWystaje[i] -> na ile sposobow moge ulozyc pasek dlugosci i
// 		tak, ze konczy sie wystajacym klockiem
int ileWystaje[MAXN];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n;
	cin >> n;

	ilePlaski[1] = 1;
	ileDziura[1] = 1;
	ileWystaje[1] = 1;

	for (int i = 2; i <= n; ++i) {
		// dokladam na koniec odpowiednio klocek:
		// plaski, z dziura, wystajacy
		ilePlaski[i] = (ilePlaski[i] + ilePlaski[i - 1]) % MOD;
		ilePlaski[i] = (ilePlaski[i] + ileWystaje[i - 1]) % MOD;
		ilePlaski[i] = (ilePlaski[i] + ileDziura[i - 1]) % MOD;

		// dokladam na koniec odpowiednio klocek:
		// z dziura, z dwoma dziurami
		ileDziura[i] = (ileDziura[i] + ilePlaski[i - 1]) % MOD;
		ileDziura[i] = (ileDziura[i] + ileWystaje[i - 1]) % MOD;

		// dokladam na koniec odpowiednio klocek:
		// wystajacy, podwojny wystajacy, podwojny klocek obrocony
		ileWystaje[i] = (ileWystaje[i] + ilePlaski[i - 1]) % MOD;
		ileWystaje[i] = (ileWystaje[i] + ileDziura[i - 2]) % MOD;
		ileWystaje[i] = (ileWystaje[i] + ileDziura[i - 2]) % MOD;
	}

	cout << ilePlaski[n] << '\n';
	return 0;
}
Kod C++ programu Dynamiczna Zabawa Puzzlami, który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Analogiczny kod w języku Python programu Dynamiczna Zabawa Puzzlami:

MAXN = 1000*1000 + 7
MOD = 1000*1000*1000 + 7

# ilePlaski[i] -> na ile sposobow moge ulozyc pasek dlugosci i
# 		tak, ze konczy sie plaskim klockiem
ilePlaski = [0] * MAXN

# ileDziura[i] -> na ile sposobow moge ulozyc pasek dlugosci i
# 		tak, ze konczy sie dziura
ileDziura = [0] * MAXN

# ileWystaje[i] -> na ile sposobow moge ulozyc pasek dlugosci i
# 		tak, ze konczy sie wystajacym klockiem
ileWystaje = [0] * MAXN


ilePlaski[1] = 1
ileDziura[1] = 1
ileWystaje[1] = 1

n = int(input())

for i in range(2, n+1):
	# dokladam na koniec odpowiednio klocek:
	# plaski, z dziura, wystajacy
	ilePlaski[i] = (ilePlaski[i - 1] + ileWystaje[i - 1] + ileDziura[i - 1]) % MOD

	# dokladam na koniec odpowiednio klocek:
	# z dziura, z dwoma dziurami
	ileDziura[i] = (ilePlaski[i - 1] + ileWystaje[i - 1]) % MOD

	# dokladam na koniec odpowiednio klocek:
	# wystajacy, podwojny wystajacy, podwojny klocek obrocony
	ileWystaje[i] = (ilePlaski[i - 1] + 2*ileDziura[i - 2]) % MOD

print(ilePlaski[n])

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz