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
–
#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])