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