fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <tuple>
  5.  
  6. using namespace std;
  7.  
  8. // Maksymalna liczba żetonów, którą będziemy śledzić w BFS.
  9. // Wartość 20 jest wystarczająca dla reguł o wartościach 0-9.
  10. const int MAX_T = 21;
  11.  
  12. struct Rule {
  13.     int a, b, c, ap, bp, cp;
  14. };
  15.  
  16. struct State {
  17.     int z, s, m;
  18. };
  19.  
  20. void solve() {
  21.     int z0, s0, m0, zt, st, mt;
  22.     if (!(cin >> z0 >> s0 >> m0)) return;
  23.     cin >> zt >> st >> mt;
  24.  
  25.     int r;
  26.     cin >> r;
  27.     vector<Rule> rules(r);
  28.     for (int i = 0; i < r; ++i) {
  29.         cin >> rules[i].a >> rules[i].b >> rules[i].c 
  30.             >> rules[i].ap >> rules[i].bp >> rules[i].cp;
  31.     }
  32.  
  33.     // Tablica odległości: dist[złote][srebrne][miedziane]
  34.     // Inicjalizujemy -1 (nieodwiedzone)
  35.     int dist[MAX_T + 1][MAX_T + 1][MAX_T + 1];
  36.     for (int i = 0; i <= MAX_T; ++i)
  37.         for (int j = 0; j <= MAX_T; ++j)
  38.             for (int k = 0; k <= MAX_T; ++k)
  39.                 dist[i][j][k] = -1;
  40.  
  41.     queue<State> q;
  42.  
  43.     // Startowy stan (z przycięciem do MAX_T)
  44.     int sz = min(z0, MAX_T), ss = min(s0, MAX_T), sm = min(m0, MAX_T);
  45.     dist[sz][ss][sm] = 0;
  46.     q.push({sz, ss, sm});
  47.  
  48.     while (!q.empty()) {
  49.         State curr = q.front();
  50.         q.pop();
  51.  
  52.         // Sprawdzamy, czy aktualny stan spełnia warunek otwarcia Sezamu
  53.         if (curr.z >= zt && curr.s >= st && curr.m >= mt) {
  54.             cout << dist[curr.z][curr.s][curr.m] << endl;
  55.             return;
  56.         }
  57.  
  58.         for (const auto& rule : rules) {
  59.             // Czy Alibabę stać na tę wymianę?
  60.             if (curr.z >= rule.a && curr.s >= rule.b && curr.m >= rule.c) {
  61.                 // Obliczamy nowy stan
  62.                 int nz = min(MAX_T, curr.z - rule.a + rule.ap);
  63.                 int ns = min(MAX_T, curr.s - rule.b + rule.bp);
  64.                 int nm = min(MAX_T, curr.z - rule.c + rule.cp); 
  65.                 // UWAGA: powyżej wkradł się błąd logiczny w nm, powinno być:
  66.                 nm = min(MAX_T, curr.m - rule.c + rule.cp);
  67.  
  68.                 if (dist[nz][ns][nm] == -1) {
  69.                     dist[nz][ns][nm] = dist[curr.z][curr.s][curr.m] + 1;
  70.                     q.push({nz, ns, nm});
  71.                 }
  72.             }
  73.         }
  74.     }
  75.  
  76.     cout << "NIE" << endl;
  77. }
  78.  
  79. int main() {
  80.     ios_base::sync_with_stdio(false);
  81.     cin.tie(NULL);
  82.  
  83.     int d;
  84.     cin >> d;
  85.     while (d--) {
  86.         solve();
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2
stdout
copy 
NIE
9
https://ideone.com/gowWmN
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!