Szczegółowe omówienie zadania Klub Księgarza ze sparingu Olimpiady Informatycznej Juniorów:
Link do contestu stałego gdzie można wrzucać rozwiązania zadania Klub Księgarza:
–
Zadanie Klub Księgarza to ciekawe zadanie, które ćwiczy Programowanie Dynamiczne.
Programowanie dynamiczne zostało omówione na wykładzie przed sparingiem:
https://www.youtube.com/watch?v=SBBDcyi7Y_g
–
Zadanie Klub Księgarza pochodzi ze sparingu Olimpiady Informatycznej Juniorów.
Każdy kto chce uzyskać dobry wynik w Olimpiadzie Informatycznej Juniorów lub Olimpiadzie Informatycznej Licealistów ma wielką szansę by zaatakować to zadanie!
Jak się uczyć na podstawie takiego zadania?
https://tiny.pl/7x1gg
Jak się uczyć na podstawie takiego zadania?
https://tiny.pl/7x1gg
——-
Kod C++ programu Klub Księgarza, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <cassert>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 200 * 1000 + 10;
const int MAX_K = 5;
ll MOD = 1000 * 1000 * 1000 + 7;
ll dp[N][MAX_K + 1]; //dp[i][v] - liczba cigw dugoci i ktrych suma daje reszt v przy dzieleniu przez K
ll cnt[MAX_K + 1];
int get_divs(int x, int d, int rem) { return x / d + (x % d >= rem ? 1 : 0); } //get_divs(14, 5, 1) = 2 + 1 = 3
int get_divs(int l, int r, int d, int rem) { //get_divs(3, 14, 5, 1)
assert(l >= 1);
return get_divs(r, d, rem) - get_divs(l - 1, d, rem); //get_divs(14, 5, 1) - getdivs(2, 5, 1) = 3 - 1 = 2
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, l, r, div;
cin >> n >> l >> r >> div;
for (int i = 0; i < div; i++) {
dp[0][i] = cnt[i] = get_divs(l, r, div, i) % MOD;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < div; j++) {
for (int k = 0; k < div; k++) {
int v = (j + k) % div;
dp[i][v] += (dp[i - 1][j] * cnt[k]) % MOD;
dp[i][v] %= MOD;
}
}
}
cout << dp[n - 1][0] << "\n";
}