Posted in BFS, Kuangbin

POJ 1426/ kuangbin 1E

10/16/2017
Problem: http://poj.org/problem?id=1426
Solution: BFS. Manage a queue, and for each time push current number + 0 or 1 in
the end all the way untill curr is a multiple of given n. For some
mysterious reason limited to long long…


#include<iostream>
#include<queue>
using namespace std;

int main() {
	long long n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		long long ans = 0;
		queue<long long> q;
		q.push(1);
		while (!q.empty()) {
			long long cur = q.front();
			q.pop();
			if (cur % n == 0) {
				cout << cur << endl;
				break;
			} else {
				q.push(cur * 10);
				q.push(cur * 10 + 1);
			}
		}
	}
	return 0;
} 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s