Omówienie zadania Klub Księgarza / Olimpiada Informatyczna Juniorów

Omówienie zadania Klub Księgarza / Olimpiada Informatyczna Juniorów

Szczegółowe omówienie zadania Klub Księgarza ze sparingu Olimpiady Informatycznej Juniorów:
https://youtu.be/f0elTQkIyN0?t=2922

Link do zadania Klub Księgarza:
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
——-
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";
}
Link do pliku z kodem C++ zadania Klub Księgarza 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz