#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize ("unroll-loops")
#define _CRT_SECURE_NO_WARNINGS
#define what_is(x) cerr << #x << " is " << x << endl;
// Leetcode
//static const auto speedup =[]() {std::ios::sync_with_stdio(false); std::cin.tie(NULL); return 0;}();
//__builtin_popcount()
typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define endl '\n'
#define INF (long long)1e18 + 5 //Infinity
#define MOD 1000000007
#define M_PI 3.141592653589793
#define f(i,a,b) for (i = a; i < b; i++)
#define rv(i,a,b) for (i = a; i >= b; i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vld vector<ld>
#define ss second
#define ff first
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define tri pair<ll, pll>
#define vii vector<pii>
#define vll vector<pll>
#define vlll vector<tri>
#define vvi vector<vi>
#define vvl vector<vl>
#define clr(arr) memset(arr, 0, sizeof (arr))
using namespace std;
using namespace __gnu_pbds;
/*
Custom comparator comparator.
auto cmp = [](int a, int b) {
return a < b;
};
set<int, decltype(cmp)> st(cmp);
*/
template<class keyType, class valueType = null_type, class cmp = std::less<keyType>>
using myTree =
tree<
keyType,
valueType,
cmp,
rb_tree_tag,
tree_order_statistics_node_update>;
/*
myTree<int> myset;
myTree<pair<int, int>> myMultiset;
myTree<int, int> mapping;
myTree<pair<int, int>, int> myMultimap;
*/
/*
myset.order_of_key(any_key); --> Returns an int, the number of elements strictly smaller than this key.
myset.find_by_order(position); --> Returns and iterator pointing to the position. Starts from 0.
*/
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void print(vld &combination) {
ll i;
f(i, 0, sz(combination)) {
cout<<combination[i]<<' ';
}
}
vld getCurrentDistribution(ll bitmask, const vld &allowedDenominations) {
ll position = 0;
vld distribution;
while(bitmask) {
if(bitmask & 1) {
distribution.eb(allowedDenominations[position]);
}
position++;
bitmask >>= 1;
}
return distribution;
}
ld findSum(const vld& distribution) {
ld sum = 0;
for(auto itr = distribution.begin(); itr != distribution.end(); itr++) {
sum += *itr;
}
return sum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*cout<<fixed<<setprecision(7);
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
*/
ll minSum, maxSum, noOfItems;
cin>>minSum>>maxSum>>noOfItems;
ll noOfDenominations, i;
cin>>noOfDenominations;
vld allowedDenominations(noOfDenominations);
f(i, 0, noOfDenominations) {
cin>>allowedDenominations[i];
}
ll optimisingDenominationCountThreshold = 18;
if(noOfDenominations > optimisingDenominationCountThreshold) {
noOfDenominations = optimisingDenominationCountThreshold;
shuffle(allowedDenominations.begin(), allowedDenominations.end(), rng);
allowedDenominations.erase(allowedDenominations.begin() + optimisingDenominationCountThreshold,
allowedDenominations.end());
}
vector<pair<vld, ld>> validCombinations;
vld currentDistribution;
ll bitmask, totalDistributionPossibilites = pow(2, noOfDenominations);
f(bitmask, 0, totalDistributionPossibilites) {
currentDistribution = getCurrentDistribution(bitmask, allowedDenominations);
ld sum = findSum(currentDistribution);
if(sum >= minSum
&& sum <= maxSum
&& sz(currentDistribution) >= noOfItems) {
validCombinations.pb({currentDistribution, sum});
}
currentDistribution.clear();
}
ll noOfValidCombinations = sz(validCombinations);
if(!noOfValidCombinations) {
cout<<"No valid distribution found";
return 0;
}
// choose any random distribution and its corresponding sum to use in the current gameplay
pair<vld, ld> randomSumCombination = validCombinations[rng() % noOfValidCombinations];
vld distribution(noOfItems, 0);
ll distributionBucketSize = sz(randomSumCombination.ff) / noOfItems, j = 0;
f(i, 0, noOfItems) {
ll k = 0;
f(k, 0, distributionBucketSize) {
distribution[i] += randomSumCombination.ff[j++];
}
}
while(j < sz(randomSumCombination.ff)) {
distribution[noOfItems - 1] += randomSumCombination.ff[j++];
}
cout<<"Chosen sum for gameplay: "<<randomSumCombination.ss<<endl<<"Item price distribution: ";
print(distribution);
cout<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}
/*
Input:
1 8000000 6
30 200 200 200 100 100 50 50 2 1 10 10 5 1 2 20 1 0.05 0.02 0.2 0.5 0.05 0.02 0.2 0.5 0.2 0.5 0.05 0.02 0.2 0.5
One possible Output:
Chosen sum for gameplay: 468.7
Item price distribution: 10 0.5 1 1 200 256.2
-------------------------
Input:
600 4000 4
20 200 200 200 100 100 50 50 2 1 10 10 5 1 2 20 1 0.05 0.02 0.2 0.5
One possible output:
Chosen sum for gameplay: 773.02
Item price distribution: 400 300 52 21.02
*/
