Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <math.h>
- #include <vector>
- #include <fstream>
- using namespace std;
- void BackTracking(int nCoin);
- int N, M;
- vector<int> usedCoins;
- vector<int> coinsIn;
- int minAmount = M + M + 10, currAmount = 0;
- long long Summ = 0;
- void doSearch() {
- BackTracking(0);
- }
- void BackTracking(int nCoin) {
- if (nCoin >= M) return;
- if (Summ > N) return;
- for (int i = 0; i < 3; i++) {
- if (i != 0) {
- currAmount++;
- Summ += coinsIn[nCoin];
- }
- usedCoins.push_back( coinsIn[nCoin] );
- cout << "i " << i << " nCoin " << nCoin << " Summ " << Summ << " currAmount " << currAmount << endl;
- if (Summ == N) {
- cout << "!!!!!!";
- if (currAmount < minAmount) {
- minAmount = currAmount;
- }
- }
- BackTracking(nCoin + 1);
- }
- currAmount -= 2;
- Summ -= 2*coinsIn[nCoin];
- usedCoins.pop_back();
- usedCoins.pop_back();
- usedCoins.pop_back();
- }
- int main()
- {
- long long sum;
- cin >> N >> M;
- for (int i = 0; i < M; ++i) {
- int t;
- cin >> t;
- coinsIn.push_back(t);
- sum += t*2;
- }
- if (sum < N) {
- cout << "-1";
- } else if (sum == N) {
- cout << coinsIn.size()*2 << endl;
- for (int i = 0; i < coinsIn.size(); i++) {
- cout << coinsIn[i] << " " << coinsIn[i] << " ";
- }
- } else {
- doSearch();
- cout << minAmount << endl;
- for (int i = 0; i < minAmount; i++) {
- cout << usedCoins[i] << " ";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement