test/aoj/3134/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3134

Depends on

• Fast Zeta transform (Subsets) (Mylib/Convolution/fast_zeta_transform_subset.cpp)
• Input vector (Mylib/IO/input_vector.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3134"

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
#include "Mylib/Convolution/fast_zeta_transform_subset.cpp"
#include "Mylib/IO/input_vector.cpp"

namespace hl = haar_lib;

int main() {
  int N, K;
  std::cin >> N >> K;

  auto A = hl::input_vector<int>(N);

  std::vector<int> sum(1 << N);

  for (int i = 0; i < 1 << N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (not(i & (1 << j))) {
        sum[i | (1 << j)] = sum[i] + A[j];
      }
    }
  }

  std::vector<int> f(1 << N);
  for (int i = 0; i < 1 << N; ++i) {
    if (sum[i] == K) f[i] = true;
  }

  f = hl::fast_zeta_transform_subset(f, std::logical_or<bool>());

  int ans = N;

  for (int i = 0; i < 1 << N; ++i) {
    if (not f[i]) {
      ans = std::min(ans, N - __builtin_popcount(i));
    }
  }

  std::cout << ans << std::endl;

  return 0;
}

#line 1 "test/aoj/3134/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3134"

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
#line 2 "Mylib/Convolution/fast_zeta_transform_subset.cpp"
#include <cassert>
#line 5 "Mylib/Convolution/fast_zeta_transform_subset.cpp"

namespace haar_lib {
  template <typename T, typename Func = std::plus<T>>
  std::vector<T> fast_zeta_transform_subset(std::vector<T> f, const Func &op = std::plus<T>()) {
    const int N = f.size();
    assert((N & (N - 1)) == 0 && "N must be a power of 2");
    for (int i = 1; i < N; i <<= 1) {
      for (int j = 0; j < N; ++j) {
        if (j & i) f[j] = op(f[j], f[j ^ i]);
      }
    }
    return f;
  }
}  // namespace haar_lib
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 9 "test/aoj/3134/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int N, K;
  std::cin >> N >> K;

  auto A = hl::input_vector<int>(N);

  std::vector<int> sum(1 << N);

  for (int i = 0; i < 1 << N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (not(i & (1 << j))) {
        sum[i | (1 << j)] = sum[i] + A[j];
      }
    }
  }

  std::vector<int> f(1 << N);
  for (int i = 0; i < 1 << N; ++i) {
    if (sum[i] == K) f[i] = true;
  }

  f = hl::fast_zeta_transform_subset(f, std::logical_or<bool>());

  int ans = N;

  for (int i = 0; i < 1 << N; ++i) {
    if (not f[i]) {
      ans = std::min(ans, N - __builtin_popcount(i));
    }
  }

  std::cout << ans << std::endl;

  return 0;
}

Back to top page