Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Template for contests - different includes and templates
- * Real task code is in the end
- * Mikhail Dektyarow <[email protected]>, 2009-2016
- */
- #include <cstdio>
- #include <cstdint>
- #include <cstdlib>
- #include <cstring>
- #include <cmath>
- #include <climits>
- #include <cassert>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <deque>
- #include <queue>
- #include <sstream>
- #include <numeric>
- #include <stack>
- #include <bitset>
- #include <iostream>
- #include <string>
- using namespace std;
- /*
- * DEFINES
- */
- #define FOR(i, a, b) for (int i(a), _b(b); i <= _b; ++i)
- #define REP(i, n) for (int i(0), _n(n); i < _n; ++i)
- /*
- * Types
- */
- using ipair = pair<int, int>;
- using int64 = int64_t;
- using uint64 = uint64_t;
- /*
- * Different useful templates
- */
- template<typename T> void remin(T& a, const T& b) {
- if (b < a) {
- a = b;
- }
- }
- template<typename T> void remax(T& a, const T& b) {
- if (b > a) {
- a = b;
- }
- }
- template<class T1, class T2>inline istream& operator>> (istream &s, pair<T1, T2>& p) {
- return s >> p.first >> p.second;
- }
- template<class T1, class T2>inline ostream& operator<< (ostream &s, const pair<T1, T2> p) {
- return s << "(" << p.first << " " << p.second << ")";
- }
- template<class T1>inline ostream& operator<< (ostream& s, const vector<T1>& container) {
- for (const auto& i : container) s << i << ' ';
- return s;
- }
- template<class T1>inline istream& operator>> (istream&s, vector<T1>& container) {
- for (auto& i : container) s >> i;
- return s;
- }
- /*
- * Euclide's algorithm
- */
- template<class T> inline T euclide(T a,T b,T &x,T &y) {
- if (a < 0) {
- T d = euclide(-a, b, x, y);
- x = -x;
- return d;
- }
- if (b < 0) {
- T d = euclide(a, -b, x, y);
- y = -y;
- return d;
- }
- if (b == 0){
- x = 1;
- y = 0;
- return a;
- }
- else {
- T d = euclide(b, a % b, x, y);
- T t = x;
- x = y;
- y = t - (a / b) * y;
- return d;
- }
- }
- template<class T> inline T euclide(T a, T b) {
- T x, y;
- return euclide(a, b, x, y);
- }
- /*
- * Factorizing a number
- */
- template<class T> inline vector<pair<T,int> > factorize_slow(T n) {
- vector<pair<T,int>> result;
- for (T i=2; n>1; ) {
- if (n%i == 0 ){
- int C=0;
- for ( ; n%i==0; C++) {
- n /= i;
- }
- result.emplace_back(i, C);
- }
- ++i;
- if (i > n / i) {
- i=n;
- }
- }
- if (n > 1) {
- result.emplace_back(n,1);
- }
- return result;
- }
- template<class T> inline bool isPrimeNumber(T n) {
- if( n <= 1) {
- return false;
- }
- for (T i = 2; i * i <= n; ++i) {
- if (n % i == 0) {
- return false;
- }
- }
- return true;
- }
- //Searching prime numbers
- //Using Sieve of Atkin (http://en.wikipedia.org/wiki/Sieve_of_Atkin)
- vector<bool> gen_primes_sieve(int limit) {
- int sqr_lim;
- int x2, y2;
- int n;
- vector<bool> is_prime(limit+1, false);
- sqr_lim = (int)sqrt((long double)limit);
- is_prime[2] = true;
- is_prime[3] = true;
- x2 = 0;
- for (int i = 1; i <= sqr_lim; i++) {
- x2 += 2 * i - 1;
- y2 = 0;
- for (int j = 1; j <= sqr_lim; j++) {
- y2 += 2 * j - 1;
- n = 4 * x2 + y2;
- if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
- is_prime[n] = !is_prime[n];
- n -= x2;
- if ((n <= limit) && (n % 12 == 7))
- is_prime[n] = !is_prime[n];
- n -= 2 * y2;
- if ((i > j) && (n <= limit) && (n % 12 == 11))
- is_prime[n] = !is_prime[n];
- }
- }
- for (int i = 5; i <= sqr_lim; i++) {
- if (is_prime[i]) {
- n = i * i;
- for (int j = n; j <= limit; j += n) {
- is_prime[j] = false;
- }
- }
- }
- return is_prime;
- }
- vector<int> gen_primes_vector(int limit) {
- auto is_prime = gen_primes_sieve(limit);
- vector<int> primes;
- for (size_t i = 0; i < is_prime.size(); ++i) {
- if (is_prime[i]) {
- primes.push_back(i);
- }
- }
- return primes;
- }
- vector<ipair> factorize_fast(const vector<int>& primes, int n) {
- vector<ipair> result;
- while (true) {
- for (const auto& p : primes) {
- if (p * p > n) {
- if (n > 1) {
- result.emplace_back(n, 1);
- }
- return result;
- }
- int c = 0;
- while (n % p == 0) {
- ++c;
- n /= p;
- }
- if (c) {
- result.emplace_back(p, c);
- }
- }
- }
- }
- template<class T> T fast_pow(const T& what, int n) {
- if (!n) {
- return T(1);
- }
- if (n == 1) {
- return what;
- }
- T tmp = fast_pow(what, n / 2);
- tmp *= tmp;
- if (n % 2) {
- tmp *= what;
- }
- return tmp;
- }
- /*
- * Real code
- */
- int main(void) {
- int __number_of_cases;
- cin >> __number_of_cases;
- REP(__number_of_case, __number_of_cases) {
- cerr << "case " << __number_of_case << endl;
- uint64 C, D, V;
- cin >> C >> D >> V;
- vector<uint64> coins(D);
- cin >> coins;
- cout << "Case #" << __number_of_case+1 << ": " << get(C, V, coins) << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment