fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define nmax (long long)(1e6+7)
  5. #define oo (long long)(1e18)
  6. #define INF (int)(1e9+7)
  7. #define fi first
  8. #define se second
  9. #define pii pair<int, int>
  10. #define Hung ""
  11. using namespace std;
  12.  
  13.  
  14. ll m, b[2007], dp[1 << 22];
  15.  
  16. int main()
  17. {
  18.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  19.     if (fopen(Hung".inp", "r")){
  20.         freopen(Hung".inp", "r", stdin);
  21.         freopen(Hung".out", "w", stdout);
  22.     }
  23.     cin >> m;
  24.     for (ll i=1; i<=m; i++){
  25.         cin >> b[i];
  26.     }
  27.     vector<ll> v;
  28.     for (ll mask=0; mask<(1 << m); mask++){
  29.         bool ok = true;
  30.         for (ll i=1; i<=m; i++){
  31.             if ((mask >> (i - 1)) & 1){
  32.                 for (ll j=i + 1; j<=m; j++){
  33.                     if (i != j && ((mask >> (j - 1)) & 1)){
  34.                         if (abs(b[i] - b[j]) == 1 || abs(b[i] - b[j]) == 8 || abs(b[i] - b[j]) == 9){
  35.                             ok = false;
  36.                             break;
  37.                         }
  38.                     }
  39.                 }
  40.             }
  41.             if (ok == false){
  42.                 break;
  43.             }
  44.         }
  45.         if (ok == true)
  46.             v.push_back(mask);
  47.     }
  48.     if (v.empty()) cout << '0';
  49.     else{
  50.         ll res = oo;
  51.         for (ll i=0; i<v.size(); i++){
  52.             ll cnt = __builtin_popcount(v[i]);
  53.             res = min(res, m - cnt);
  54.         }
  55.         cout << res;
  56.     }
  57.     return 0;
  58. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9g5UKK
language:
C++ (gcc 8.3)
created:
4 days 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!