[UVA] 11392 - Binary*3 Type Multiple
|
I I U C O N L I N E C O N T E S T 2 0 0 8 |
|
|
Problem H: Binary*3 Type Multiple |
|
|
Input: standard input |
|
|
|
|
|
Mahbub thinks that he has found something interesting but he is not sure whether he is right or not. For each integer he seems to find a multiple of it such that it is only composed of 3s and 0s. Can you help him?
You will be given a positive integer K. You have to find a positive multiple of K which is only composed of 3s and 0s. And in addition to this, the digits of that multiple have to be in non-increasing order. If there are more than one such multiple you have to choose the one which is shortest in length. Even after this if more than one multiple remain then you should choose the lexicographically largest one.
For example, For K = 4, our desired multiple is 300. For K = 7, it is 333333. And for K = 14, it will be 3333330.
|
|
|
Input |
|
|
The input consists of several lines containing one positive integer K.
|
|
|
Output |
|
|
Your code should produce one line of output containing space separated 3 integers. First integer is the length of the multiple, second integer number of 3s in the multiple and third integer number of 0s in your multiple.
|
|
|
Constraints |
|
|
- K ≤ 1000000
|
|
|
Sample Input |
Output for Sample Input |
|
4 7 14 |
3 1 2 6 6 0 7 6 1 |
|
|
|
|
Problem setter: Md. Mahbubul Hasan Special thanks to: Abduallah Al Mahmud Source: BdOI Warmup |
|
找一個長度越短越好，數字越大越好 (只能由 0 和 3 構成的數字)，且符合 non-increasing order。
可以被 K 整除。
題目解法：
由於 non-increasing order，一定是多個 3 後面接 多個 0 的數字型態。
那麼對所有 333...333 計算模結果，查找重複，之後扣掉即可。
O(n)。
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
int prev[1048576];
int main() {
int n;
int i, j;
while(scanf("%d", &n) == 1) {
if(n == 1 || n == 3) {
puts("1 1 0");
continue;
}
memset(prev, 0, n*4);
prev[j = 3%n] = 2;
prev[0] = 1;
for(i = 3; ; i++) {
j = (j*10+3)%n;
if(prev[j]) {
printf("%d %d %d\n", i-1, i-prev[j], prev[j]-1);
break;
}
prev[j] = i;
}
}
return 0;
}