// Coins.cpp : Defines the entry point for the console application. // #include #include using namespace std; const int max_n = 100000; const int max_s = 1000000000; const int max_a = 1000000000; typedef unsigned long long ul64; int coins(istream& fin, ostream& fout) { int n, s; int* a = new int[max_n]; ul64* d = new ul64[max_n + 1]; d[0] = 1; fin >> n >> s; //if (n < 1 || n > max_n) // return 1; //if (s < 0 || s > max_s) // return 1; for (int i = 0; i < n; i++) { fin >> a[i]; //if (a[i] < 2 || a[i] > max_a) // return 1; d[i + 1] = d[i] * a[i]; } if (s == 0) { fout << 0 << endl; } else { ul64 r = s; int c = 0; for(int i = n; i >= 0 && r > 0; i--) { if (r < d[i]) continue; while (r >= d[i]) { int cd = r / d[i]; r -= cd * d[i]; c += cd; } } fout << c << endl; } return 0; } int main(int argc, char* argv[]) { //#ifdef _DEBUG // int res = coins(cin, cout); // return res; //#else fstream fin, fout; fin.open("coins.in", ios_base::in); fout.open("coins.out", ios_base::out); return coins(fin, fout); //#endif }