BÀI B: Cửa hàng kỳ lạ

B.cpp

#include <bits/stdc++.h>

#define _for(i,a,b) for (int i=(a),_b_=(b);i<_b_;i++)
#define _fod(i,a,b) for (int i=(a),_b_=(b);i>_b_;i--)
#define _it(i,v) for (typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define _all(v) v.begin(), v.end()
#define __(v) memset(v,0,sizeof(v))

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
template<typename T> vector<T> &operator += (vector<T> &v, T x) {v.push_back(x);return v;}

void solve() {
	int n,m;
	cin>>n>>m;
	int arr[n];
	_for(i,0,n) cin>>arr[i];
	int d[n];
	int k = 1,sum,nMin = 1e9+1;
	while(k <= n){
		_for(i,0,k){
			d[i] = i;
		}
		bool True = 1;
		while(True){
			sum = 0;
			_for(i,0,k) sum += arr[d[i]];
			if(sum >= m && sum < nMin) nMin = sum;
			_fod(i,k-1,-1){
				if(d[i] < n - k +i){
					d[i]+= 1;
					_for(j,i+1,n) d[j] = d[j-1]+1;
					break;
				}else if(i == 0 && d[i] == n-k){
					True = 0;
					break;
				}
			}
		}
		k++;
	}
	if(nMin > 1e9) cout<<(-1)<<endl;
	else cout<<nMin<<endl;
}

int main(){
    #ifdef HieuNguyen
    freopen("B.inp","r",stdin);
	//freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t,ii = 0;
    cin>>t;
    while(t--){
    	cout<<"Case #"<<(++ii)<<": ";
    	solve();
	}
}

BÀI B: Cửa hàng kỳ lạ
Trong khu vực Nam sống có một cửa hàng với quy tắc kì lạ: không bao giờ thối tiền lại cho khách J. Bạn muốn mua món hàng có giá trị là M, thì bạn phải trả cho chủ cửa hàng với số tiền lớn hơn hoặc bằng M và số tiền dư sẽ không được thối lại. Do xung quanh đây chỉ có một cửa hàng này nên Nam phải mua đồ ở đây.
Một lần Nam muốn mua một món hàng có giá trị M, trong túi Nam có N tờ tiền có giá trị là vi (i =1, .., N). Nam muốn chọn ra các tờ tiền để mua món hàng đó sao cho số tiền dư ra là ít nhất.

Input:
Dòng đầu tiên chứa một số nguyên T, số test. T test theo sau mỗi test gồm 2 dòng:

• Dòng 1 gồm 2 số N M cách nhau bởi 1 khoảng trắng tương ứng là số tờ tiền và giá trị mặt hàng mà Nam muốn mua.
  • Dòng 2 gồm N số vi là giá trị của từng tờ tiền.

Output:
Kết quả mỗi test trên một dòng có dạng:
Case #x: S
Trong đó x là test thứ mấy, bắt đầu tính từ 1. S là số tiền mà Nam phải bỏ ra để mua món hàng đó, nếu không thể mua được thì S là -1.

Giới hạn:
T<=100
N>=1, 0<M<109, 0<ai<106
N<=15