mihaild

Untitled

Nov 6th, 2016
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.24 KB | None | 0 0
  1. /*
  2.  * Template for contests - different includes and templates
  3.  * Real task code is in the end
  4.  * Mikhail Dektyarow <[email protected]>, 2009-2016
  5.  */
  6. #include <cstdio>
  7. #include <cstdint>
  8. #include <cstdlib>
  9. #include <cstring>
  10. #include <cmath>
  11. #include <climits>
  12. #include <cassert>
  13. #include <string>
  14. #include <vector>
  15. #include <algorithm>
  16. #include <map>
  17. #include <set>
  18. #include <deque>
  19. #include <queue>
  20. #include <sstream>
  21. #include <numeric>
  22. #include <stack>
  23. #include <bitset>
  24. #include <iostream>
  25. #include <string>
  26. using namespace std;
  27.  
  28. /*
  29.  * DEFINES
  30.  */
  31. #define FOR(i, a, b) for (int i(a), _b(b); i <= _b; ++i)
  32. #define REP(i, n) for (int i(0), _n(n); i < _n; ++i)
  33.  
  34. /*
  35.  * Types
  36.  */
  37. using ipair = pair<int, int>;
  38. using int64 = int64_t;
  39. using uint64 = uint64_t;
  40.  
  41. /*
  42.  * Different useful templates
  43.  */
  44. template<typename T> void remin(T& a, const T& b) {
  45.     if (b < a) {
  46.         a = b;
  47.     }
  48. }
  49. template<typename T> void remax(T& a, const T& b) {
  50.     if (b > a) {
  51.         a = b;
  52.     }
  53. }
  54. template<class T1, class T2>inline istream& operator>> (istream &s, pair<T1, T2>& p) {
  55.     return s >> p.first >> p.second;
  56. }
  57. template<class T1, class T2>inline ostream& operator<< (ostream &s, const pair<T1, T2> p) {
  58.     return s << "(" << p.first << " " << p.second << ")";
  59. }
  60. template<class T1>inline ostream& operator<< (ostream& s, const vector<T1>& container) {
  61.     for (const auto& i : container) s << i << ' ';
  62.     return s;
  63. }
  64. template<class T1>inline istream& operator>> (istream&s, vector<T1>& container) {
  65.     for (auto& i : container) s >> i;
  66.     return s;
  67. }
  68. /*
  69.  * Euclide's algorithm
  70.  */
  71. template<class T> inline T euclide(T a,T b,T &x,T &y) {
  72.     if (a < 0) {
  73.         T d = euclide(-a, b, x, y);
  74.         x = -x;
  75.         return d;
  76.     }
  77.     if (b < 0) {
  78.         T d = euclide(a, -b, x, y);
  79.         y = -y;
  80.         return d;
  81.     }
  82.     if (b == 0){
  83.         x = 1;
  84.         y = 0;
  85.         return a;
  86.     }
  87.     else {
  88.         T d = euclide(b, a % b, x, y);
  89.         T t = x;
  90.         x = y;
  91.         y = t - (a / b) * y;
  92.         return d;
  93.     }
  94. }
  95. template<class T> inline T euclide(T a, T b) {
  96.     T x, y;
  97.     return euclide(a, b, x, y);
  98. }
  99. /*
  100.  * Factorizing a number
  101.  */
  102. template<class T> inline vector<pair<T,int> > factorize_slow(T n) {
  103.     vector<pair<T,int>> result;
  104.     for (T i=2; n>1; ) {
  105.         if (n%i == 0 ){
  106.             int C=0;
  107.             for ( ; n%i==0; C++) {
  108.                 n /= i;
  109.             }
  110.             result.emplace_back(i, C);
  111.         }
  112.         ++i;
  113.         if (i > n / i) {
  114.             i=n;
  115.         }
  116.     }
  117.     if (n > 1) {
  118.         result.emplace_back(n,1);
  119.     }
  120.     return result;
  121. }
  122. template<class T> inline bool isPrimeNumber(T n) {
  123.     if( n <= 1) {
  124.         return false;
  125.     }
  126.     for (T i = 2; i * i <= n; ++i) {
  127.         if (n % i == 0) {
  128.             return false;
  129.         }
  130.     }
  131.     return true;
  132. }
  133. //Searching prime numbers
  134. //Using Sieve of Atkin (http://en.wikipedia.org/wiki/Sieve_of_Atkin)
  135. vector<bool> gen_primes_sieve(int limit) {
  136.     int sqr_lim;
  137.     int x2, y2;
  138.     int n;
  139.     vector<bool> is_prime(limit+1, false);
  140.     sqr_lim = (int)sqrt((long double)limit);
  141.     is_prime[2] = true;
  142.     is_prime[3] = true;
  143.     x2 = 0;
  144.     for (int i = 1; i <= sqr_lim; i++) {
  145.         x2 += 2 * i - 1;
  146.         y2 = 0;
  147.         for (int j = 1; j <= sqr_lim; j++) {
  148.             y2 += 2 * j - 1;
  149.             n = 4 * x2 + y2;
  150.             if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
  151.                 is_prime[n] = !is_prime[n];
  152.             n -= x2;
  153.             if ((n <= limit) && (n % 12 == 7))
  154.                 is_prime[n] = !is_prime[n];
  155.             n -= 2 * y2;
  156.             if ((i > j) && (n <= limit) && (n % 12 == 11))
  157.                 is_prime[n] = !is_prime[n];
  158.         }
  159.     }
  160.     for (int i = 5; i <= sqr_lim; i++) {
  161.         if (is_prime[i]) {
  162.             n = i * i;
  163.             for (int j = n; j <= limit; j += n) {
  164.                 is_prime[j] = false;
  165.             }
  166.         }
  167.     }
  168.     return is_prime;
  169. }
  170. vector<int> gen_primes_vector(int limit) {
  171.     auto is_prime = gen_primes_sieve(limit);
  172.     vector<int> primes;
  173.     for (size_t i = 0; i < is_prime.size(); ++i) {
  174.         if (is_prime[i]) {
  175.             primes.push_back(i);
  176.         }
  177.     }
  178.     return primes;
  179. }
  180. vector<ipair> factorize_fast(const vector<int>& primes, int n) {
  181.     vector<ipair> result;
  182.     while (true) {
  183.         for (const auto& p : primes) {
  184.             if (p * p > n) {
  185.                 if (n > 1) {
  186.                     result.emplace_back(n, 1);
  187.                 }
  188.                 return result;
  189.             }
  190.             int c = 0;
  191.             while (n % p == 0) {
  192.                 ++c;
  193.                 n /= p;
  194.             }
  195.             if (c) {
  196.                 result.emplace_back(p, c);
  197.             }
  198.         }
  199.     }
  200. }
  201.  
  202. template<class T> T fast_pow(const T& what, int n) {
  203.     if (!n) {
  204.         return T(1);
  205.     }
  206.     if (n == 1) {
  207.         return what;
  208.     }
  209.     T tmp = fast_pow(what, n / 2);
  210.     tmp *= tmp;
  211.     if (n % 2) {
  212.         tmp *= what;
  213.     }
  214.     return tmp;
  215. }
  216.  
  217. /*
  218.  * Real code
  219.  */
  220.  
  221. int main(void) {
  222.     int __number_of_cases;
  223.     cin >> __number_of_cases;
  224.     REP(__number_of_case, __number_of_cases) {
  225.         cerr << "case " << __number_of_case << endl;
  226.         uint64 C, D, V;
  227.         cin >> C >> D >> V;
  228.         vector<uint64> coins(D);
  229.         cin >> coins;
  230.         cout << "Case #" << __number_of_case+1 << ": " << get(C, V, coins) << '\n';
  231.     }
  232. }
Advertisement
Add Comment
Please, Sign In to add comment