Участник:Kachanov vv/ALWFACT

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ALWFACT/

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
 
class Solver {
public:
    Solver(int N, int M) : N(N), M(M) {
        data.resize(N);
    }
 
    void init() {
        for (int i = 0; i < N; i++) {
            cin >> data[i];
        }
        left = 2;
        right = (long long) 1e12;
        ans = right;
    }
 
    void process() {
        sort(data.begin(), data.end(), greater<int>());
        while (left <= right) {
            center = (left + right + 1) / 2;
            int ways = 0;
            getCount(1, center, 0, ways);
            if (ways > M) {
                ans = center;
                right = center - 1;
            } else {
                left = center + 1;
            }
        }
    }
 
    void getCount(long product, long n, int p, int &skipped) {
        if (p >= (int) data.size()) {
            skipped++;
            return;
        } else if (product > n) {
            return;
        }
        while (true) {
            if (product <= n) {
                getCount(product, n, p + 1, skipped);
            } else {
                break;
            }
            product *= data[p];
        }
    }
 
    void dump() {
        cout << ans << endl;
    }
 
private:
    vector<int> data;
    int N, M;
    long left, center, right, ans;
};
 
int main() {
 
    int N, M;
    cin >> N >> M;
    while (N + M != 0) {
        Solver solver(N, M);
        solver.init();
        solver.process();
        solver.dump();
        cin >> N >> M;
    }
 
    return 0;
}