2014-06-03

UVa 1051 - Bipartite Numbers

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

The executive officers of the company where you work want to send each other encrypted messages. Rather than use off-the-shelf encryption software such as PGP, they have tasked the IT staff with handling the encryption problem. The IT staff decided on a solution that requires public and private integer keys. The idea is that everyone can see your public key, but only you know your private key.

Your best friend in the company is a wonderful person but a not-so-wonderful programmer. He has created a publicprivate key scheme as follows. A public key can be any positive integer. The corresponding private key is the smallest bipartite number that is greater than and a multiple of the public key.

A bipartite number is any positive integer that contains exactly 2 distinct decimal digits s and t such that s is not 0 and all occurrences of s precede all occurrences of t. For example 44444411 is bipartite (s is 4 and t is 1), So are 41, 10000000, and 5555556. However, neither 4444114 nor 44444 are bipartite.

Notice that the large bipartite number 88888888888800000 can be nicely described as 12 8’s followed by 5 0’s. You can express any bipartite number using four numbers: m s n t. The numbers s and t are the leading and trailing digits as described above, m is the number of times the digit s appears in the bipartite number, and n is the number of times the digit t appears.

The trouble with your friend’s scheme is that it is not too difficult to compute a private key if you know the public key. You need to convince your friend that his public-private key scheme is inadequate before he loses his job over his bad decision! You must write a program that takes public keys as input and displays the corresponding private keys.

Input

The input consists of several test cases. Each test case is on a separate line, and it consists of a single public key in the range 1…99999.

The last case is followed by a line containing the integer zero.

Output

For each test case, display a line consisting of the public key, a colon, then 4 integers m s n t where m, n, s, and t are as described above.

Sample Input

Sample Output

1
2
3

125: 1 5 2 0 
17502: 4 7 4 8 
2005: 3 2 3 5

Claimer: The data used in this problem is unofficial data prepared by Derek Kisman. So any mistake here does not imply mistake in the offcial judge data. Only Derek Kisman is responsible for the mistakes. Report mistakes to dkisman@acm.org

Solution

題目描述：

現在找一個 public key，這個 public key 符合 format xxx...xyyy...y，其中 x, y 是 0-9 構成的。

而你的 private key N 是給定的，接著找一個符合規定的 public key，是 N 的倍數且最大於 N 的最小值。

題目解法：

題目給定的最大值 88888888888800000 沒有任何意義。可能會超過好幾位，連 long long 64 bits 都裝不下。

需要廣度搜索來完成，但是要找到 public key > N 會有點麻煩。

一開始嘗試在最大值下面建表查找，但卡了很多 WA，後來發現不合理的測資。
之後採用類似最短路徑的 BFS，藉由狀態 dist[MOD][2] 找到最小長度。但是這種作法不容易處理 > N 的判斷。
因此，採用一個迭代窮舉，窮舉最後的 public key 長度，然後找切割的位置分配給 x, y。

但是這樣做還是很容易 TLE，我們特別對 10 的倍數作調整，這些亂做不好說明。

更多 More
可以先把輸入讀進來，然後一次做完分析的離散處理，說不定會比較快。

// Accepted
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
struct ELE {
    int m, s, n, t;
    ELE(int a = 0, int b = 0, int c = 0, int d = 0):
        m(a), s(b), n(c), t(d) {}
    bool operator<(const ELE &x) const {
        if(m + n != x.m + x.n)
            return m + n < x.m + x.n;
        if(s != x.s)
            return s < x.s;
        if(m != x.m)
            return s < x.t;
        return t < x.t;
    }
};
#define MAXL 9999
int M1[MAXL];
int M10[MAXL];
int largeN(int N, ELE key) {
    if(key.m + key.n > 5) // > 100000
        return 1;
    int tmp = 0;
    for(int i = 0; i < key.m; i++)
        tmp = tmp * 10 + key.s;
    for(int i = 0; i < key.n; i++)
        tmp = tmp * 10 + key.t;
    return tmp > N;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout);   
    for(int N; scanf("%d", &N) == 1 && N; ) {
        
        M1[0] = 0;
        M10[0] = 1;
        for(int i = 1; i < MAXL; i++) {
            M1[i] = (M1[i-1] * 10 + 1)%N;
            M10[i] = (M10[i-1] * 10)%N;
        }
        
        ELE key(MAXL);
        for(int len = 2; len < MAXL; len++) {
            for(int i = N%10 || len <= 20 ? 1 : len - 20; i < len; i++) {
                for(int p = 1; p < 10; p++) {
                    for(int q = 0; q < 10; q++) {
                        if(p == q)
                            continue;
                        long long m = ((long long)M1[i] * M10[len - i] * p + M1[len - i] * q)%N;
                        ELE tkey(i, p, len - i, q);
                        if(m == 0 && largeN(N, tkey) && tkey < key) {
                            key = tkey;
                        }
                    }
                }
            }
            if(key.m != MAXL)
                break;
        }
        printf("%d: %d %d %d %d\n", N, 
            key.m, key.s, key.n, key.t);
    }
    return 0;
}
/*
190
24822
344
4455
*/

Morris' Blog