Advertisement
erek1e

IOI '94 P4 - The Clocks

Jun 6th, 2022
699
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 9, M = 9; // N is number of clocks, M is number of types of move
  6.  
  7. int moves[M] {
  8.     0b110110000, // ABDE
  9.     0b111000000, // ABC
  10.     0b011011000, // BCEF
  11.     0b100100100, // ADG
  12.     0b010111010, // BDEFH
  13.     0b001001001, // CFI
  14.     0b000110110, // DEGH
  15.     0b000000111, // GHI
  16.     0b000011011, // EFHI
  17. };
  18.  
  19. int main() {
  20.     int need = 0;
  21.     for (int i = 0; i < N; ++i) {
  22.         int x; cin >> x;
  23.         need <<= 2;
  24.         need += (4-x)%4;
  25.     }
  26.     int bestMask = 0, minSteps = 4*M;
  27.     for (int bitmask = 0; bitmask < (1 << (2*M)); ++bitmask) {
  28.         int result = 0, steps = 0;
  29.         for (int i = 0; i < M; ++i) {
  30.             int cnt = (bitmask >> (2*i)) & 3;
  31.             steps += cnt;
  32.             for (int j = 0; j < N; ++j) {
  33.                 if (moves[i] & (1 << j)) {
  34.                     int cur = (result >> (2*j)) & 3;
  35.                     result += cnt * (1 << (2*j));
  36.                     if (cur + cnt >= 4) result -= (1 << (2*j+2));
  37.                 }
  38.             }
  39.         }
  40.         if (result == need && steps < minSteps) {
  41.             minSteps = steps;
  42.             bestMask = bitmask;
  43.         }
  44.     }
  45.     for (int i = 0; i < M; ++i) {
  46.         int cnt = (bestMask >> (2*i)) & 3;
  47.         for (int j = 0; j < cnt; ++j) cout << i+1 << ' ';
  48.     }
  49.     cout << endl;
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement