USACO 3.1 – Humble Numbers | Jack Neus
Read full article from USACO 3.1 – Humble Numbers | Jack Neus
For a given set of K prime numbers S = {p1, p2, …, pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of 'humble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a humble number.Your job is to find the Nth humble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.
Solution: Let the array H be our set of humble numbers. Make H[0] = 1, even though 1 isn't humble. Now, for each p in S, we will keep track of which humble number we should multiply it by in, let's say, array M. In other words, start off all indices of M at 0. Then, to generate the next humble number, we find the smallest S[i] * H[M[i]]. At first, we will be getting S[i] * H[M[0]], or S[i].
Consider this example:
S = {2, 3, 4, 5}
M = {0, 0, 0, 0}
H = {1}
Minimal S[i] * H[M[i]] = 2 (S[0])
M = {1, 0, 0, 0}
H = {1, 2}
Minimal S[i] * H[M[i]] = 3 (S[1])
At this point, M = {1, 1, 0, 0}, and H = {1, 2, 3}.
After you understand this, the implementation is pretty easy. Note that if you have ties, you have to increase M[i] for all i that yield the minimal answer.
using namespace std;
#define CODE_WORKS true
ifstream in("humble.in");
ofstream out("humble.out");
int main(){
int K, N;
in >> K >> N;
int S[K], M[K];
long H[N + 1];
for(int i = 0; i < K; i++){
in >> S[i];
}
memset(M, 0, sizeof(M));
H[0] = 1;
int pos = 0;
while(pos < N + 1){
long next = INFINITY;
vector<int> which;
for(int i = 0; i < K; i++){
long sol = S[i] * H[M[i]];
if(sol > H[pos] && sol <= next){
if(sol < next){
next = sol;
which.resize(1);
which[0] = i;
}
else if(sol == next){
which.push_back(i);
}
}
}
H[++pos] = next;
for(int i = 0; i < which.size(); i++) M[which[i]]++;
}
out << H[N] << endl;
}
http://blog.csdn.net/enjoying_science/article/details/38584021Read full article from USACO 3.1 – Humble Numbers | Jack Neus
