Advertisement
Guest User

Untitled

a guest
Jul 2nd, 2011
253
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.91 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <cmath>
  7. #include <vector>
  8. #include <string>
  9. #include <map>
  10. #include <algorithm>
  11. #include <deque>
  12. #include <cstdlib>
  13. #include <cstdio>
  14. #include <set>
  15. using namespace std;
  16.  
  17. struct fff {
  18.     int reg1;
  19.     int reg2;
  20.     int k;
  21. };
  22.  
  23. fff from[259] = {};
  24.  
  25. int len = 0;
  26.  
  27. int reg[277] = {};
  28.  
  29. int DFS1(int x) {
  30.     if (x == 1) return 0;
  31.  
  32.     int reg1 = -1;
  33.     if (from[x].reg1 != 0) {
  34.         bool fnd = false;
  35.         for (int i=0; i<26; i++) {
  36.             if (reg[i] == from[x].reg1) {
  37.                 reg1 = i;
  38.                 fnd = true;
  39.                 break;
  40.             }
  41.         }
  42.         if (!fnd) {
  43.           //  if (from[x].reg1 == -1) {
  44.           //     cout << ';' << endl; // never printed
  45.           //  }
  46.             reg1 = DFS1(from[x].reg1);
  47.         }
  48.     }
  49.  
  50.     int reg2 = reg[from[x].reg2];
  51.  
  52.     bool fnd = false;
  53.     for (int i=0; i<26; i++) {
  54.         if (reg[i] == from[x].reg2) {
  55.             reg2 = i;
  56.             fnd = true;
  57.             break;
  58.         }
  59.     }
  60.     if (!fnd)
  61.         reg2 = DFS1(from[x].reg2);
  62.  
  63.     for (int i=0; i<26; i++) {
  64.         if (reg[i] == 0) {
  65.             reg[i] = x;
  66.  
  67.             if (reg1 == -1)
  68.                 ++len;
  69.             else
  70.                 ++len;
  71.             return i;
  72.         }
  73.     }
  74.     return -1;
  75. }
  76.  
  77. int findRes(int start, int reach) {
  78.     vector<int> can;
  79.     can.push_back(0);
  80.  
  81.     can.push_back(start);
  82.  
  83.     memset(from, -1, sizeof from);
  84.     from[start].reg1 = 0;
  85.  
  86.     for (int e=0; e<6; e++) {
  87.         set<int> can2;
  88.         for (int i=0; i<can.size(); i++)
  89.             can2.insert(can[i]);
  90.  
  91.         for (int x=0; x<can.size(); x++) {
  92.             for (int y=0; y<can.size(); y++) {
  93.                 can2.insert(can[x]);
  94.                 can2.insert(can[y]);
  95.  
  96.                 for (int k=1; k<=8; k *= 2) {
  97.                     if (can[x] + can[y] * k <= 255) {
  98.                         if ( from[can[x] + can[y] * k].reg1 == -1) {
  99.                             from[can[x] + can[y] * k].reg1 = can[x];
  100.                             from[can[x] + can[y] * k].reg2 = can[y];
  101.                             from[can[x] + can[y] * k].k = k;
  102.                             can2.insert(can[x] + can[y] * k);
  103.                         }
  104.                     }
  105.                 }
  106.             }
  107.         }
  108.  
  109.         can.clear();
  110.  
  111.         for (set<int>::iterator it = can2.begin(); it != can2.end(); ++it) {
  112.             can.push_back(*it);
  113.  
  114.             if (*it == reach) {
  115.                 return 1;
  116.             }
  117.         }
  118.     }
  119.     return 0;
  120. }
  121.  
  122. int main() {
  123.  
  124.   //  freopen("input.txt", "r", stdin);
  125.   //  freopen("output.txt", "w", stdout);
  126.  
  127.     int b = 122;
  128.     //cin >> b;
  129.  
  130.     memset(reg, 0, sizeof reg);
  131.     reg[0] = 1;
  132.  
  133.     findRes(1,b);
  134.  
  135.     len = 0;
  136.     DFS1(b);
  137.     printf("%d\n", len );
  138.  
  139.     return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement