fork(3) download
copy 
  1. /*__ _(_) __ _  ___  ___ _   _  __| | __ _ _   _| |_ ___  
  2.  / _` | |/ _` |/ _ \/ __| | | |/ _` |/ _` | | | | __/ _ \ 
  3. | (_| | | (_| | (_) \__ \ |_| | (_| | (_| | |_| | || (_) |
  4.  \__, |_|\__,_|\___/|___/\__,_|\__,_|\__,_|\__,_|\__\___/ 
  5.  |___/                                  Accepted Code  */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     int T;
  12.     scanf("%d",&T);
  13.     while(T--)
  14.     {
  15.         int n;
  16.         bool ok=false;
  17.         scanf("%d",&n);
  18.  
  19.         vector<int> a;
  20.         for(int i=0; i<n; i++)
  21.         {
  22.             int x;
  23.             scanf("%d",&x);
  24.             a.push_back(x);
  25.         }
  26.         for(int i=n; i<4; i++) a.push_back(0);
  27.  
  28.         int r[4];
  29.         memset(r,0,sizeof(r));
  30.         for(int i=0; i<n; i++)
  31.             scanf("%d",r+i);
  32.  
  33.         ok=true;
  34.         for(int i=0; i<n; i++)
  35.             if(a[i]!=r[i]) ok=false;
  36.         if(ok)
  37.         {
  38.             printf("%d\n",0);
  39.             continue;
  40.         }
  41.  
  42.         int8_t exist[50][50][50][50];
  43.         memset(exist,0,sizeof(exist));
  44.  
  45.         queue<vector<int>> lq;
  46.  
  47.         for(lq.push(a), exist[a[0]][a[1]][a[2]][a[3]]=1; !lq.empty(); lq.pop())
  48.         {
  49.             vector<int> cur=lq.front();
  50.             //Do nuoc tu i sang j
  51.             vector<int> w;
  52.             for(int i=0; i<n; i++)
  53.             {
  54.                 for(int j=0; j<n; j++)
  55.                     if(i!=j && cur[i]<=a[j]-cur[j])
  56.                     {
  57.                         // Tien hanh do
  58.                         w=cur;
  59.                         w[j]+=w[i];
  60.                         w[i]=0;
  61.                         // kiem tra da thoa man chua?
  62.                         ok=true;
  63.                         for(int k=0; k<n; k++)
  64.                             if(r[k]!=w[k])
  65.                             {
  66.                                 ok=false;
  67.                                 break;
  68.                             }
  69.                         // Neu da thao man roi
  70.                         if(ok)
  71.                         {
  72.                             printf("%d\n",exist[cur[0]][cur[1]][cur[2]][cur[3]]);
  73.                             break;
  74.                         }
  75.                         if(exist[w[0]][w[1]][w[2]][w[3]]==0)
  76.                         {
  77.                             exist[w[0]][w[1]][w[2]][w[3]]=exist[cur[0]][cur[1]][cur[2]][cur[3]]+1;
  78.                             lq.push(w);
  79.  
  80.                         }
  81.                     }
  82.                 if(ok) break;
  83.             }
  84.             if(ok) break;
  85.             // Do day binh j bang nuoc tu i;
  86.             for(int i=0; i<n; i++)
  87.             {
  88.                 for(int j=0; j<n; j++)
  89.                     if(i!=j && cur[j]!=a[j] && cur[i]>a[j]-cur[j])
  90.                     {
  91.                         w=cur;
  92.                         w[i]=cur[i]-(a[j]-cur[j]);
  93.                         w[j]=a[j];
  94.                         // kiem tra da thoa man chua?
  95.                         ok=true;
  96.                         for(int k=0; k<n; k++)
  97.                             if(r[k]!=w[k])
  98.                             {
  99.                                 ok=false;
  100.                                 break;
  101.                             }
  102.                         // Neu da thao man roi
  103.                         if(ok)
  104.                         {
  105.                             printf("%d\n",exist[cur[0]][cur[1]][cur[2]][cur[3]]);
  106.                             break;
  107.                         }
  108.                         if(exist[w[0]][w[1]][w[2]][w[3]]==0)
  109.                         {
  110.                             exist[w[0]][w[1]][w[2]][w[3]]=exist[cur[0]][cur[1]][cur[2]][cur[3]]+1;
  111.                             lq.push(w);
  112.                         }
  113.                     }
  114.                 if(ok) break;
  115.             }
  116.             if(ok) break;
  117.  
  118.             //Do nuoc ra cong.
  119.             for(int i=0; i<n; i++)
  120.                 if(cur[i]>0)
  121.                 {
  122.                     w=cur;
  123.                     w[i]=0;
  124.                     // kiem tra da thoa man chua?
  125.                     ok=true;
  126.                     for(int k=0; k<n; k++)
  127.                         if(r[k]!=w[k])
  128.                         {
  129.                             ok=false;
  130.                             break;
  131.                         }
  132.                     // Neu da thao man roi
  133.                     if(ok)
  134.                     {
  135.                         printf("%d\n",exist[cur[0]][cur[1]][cur[2]][cur[3]]);
  136.                         break;
  137.                     }
  138.                     if(exist[w[0]][w[1]][w[2]][w[3]]==0)
  139.                     {
  140.                         exist[w[0]][w[1]][w[2]][w[3]]=exist[cur[0]][cur[1]][cur[2]][cur[3]]+1;
  141.                         lq.push(w);
  142.                     }
  143.                 }
  144.             if(ok) break;
  145.         }
  146.         if(lq.empty()) printf("NO\n");
  147.     }
  148.     return 0;
  149. }
  150.  
Success #stdin #stdout 0s 9456KB
comments (?)
stdin
copy 
2

3
3 5 5
0 0 4

2
20 25
10 16
stdout
copy 
6
NO
https://ideone.com/oiWe2E
CTAIN - Containers
language:
C++14 (gcc 8.3)
created:
9 years 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!