Search on the blog

2011年2月14日月曜日

How simple it could be!?

Lately I strongly think that things should be as simple as possible.
The simpler, the better.

It's true for computer programming.
If the source code is simple, there's fewer bug contained.
And to help you make things simple, there are some great stuff called "STL."

See the problem below:

I solved similar problems several times. Guess it's got to be a quite famous problem, and I solved it correctly. Then again, I was not sure what approach was appropriate to this problem.
I used to solve it with some queues.

But it hit me today.
It can be solved with priority_queue in much easier way. Once I noticed it, things went simple, neat and tidy!
Pretty simple, huh??



int main() {
int p, q, r, k;

cin >> p >> q >> r >> k;
priority_queue<LL>que;

que.push(-1);

int cnt = 0;
while (!que.empty()) {
LL n = que.top();
while (!que.empty() && que.top() == n)
que.pop();

if (cnt++ == k) {
cout << -n << endl;
break;
}

que.push(n*p);
que.push(n*q);
que.push(n*r);
}

return 0;
}

0 件のコメント:

コメントを投稿