uva725

maksyuki 发表于 oj 分类，标签: 基础算法-枚举

11 6月 2018

Write a program that finds and displays all pairs of 5-digit numbers that between them use the digits 0 through 9 once each, such that the first number divided by the second is equal to an integer N, where 2 ≤ N ≤ 79. That is,
abcde / fghij = N, where each letter represents a different digit. The first digit of one of the numerals is allowed to be
zero.
Input
Each line of the input file consists of a valid integer N. An input of zero is to terminate the program.
Output
Your program have to display ALL qualifying pairs of numerals, sorted by increasing numerator (and, of course, denominator). Your output should be in the following general form:
xxxxx / xxxxx = N
xxxxx / xxxxx = N
.
.
In case there are no pairs of numerals satisfying the condition, you must write ‘There are no solutions for N.’. Separate the output for two different values of N by a blank line.
Sample Input
61
62
0
Sample Output
There are no solutions for 61.
79546 / 01283 = 62
94736 / 01528 = 62

题目类型：暴力枚举

算法分析：直接枚举除数并乘以n，看被除数是否满足要求

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2018/6/11 0:08:30
last modified  :2018/6/11 9:51:42
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int n;
bool is_have = false;
bool dig[16];
bool vis[16];

void dfs(int p, string sa) {
    if(p == 6) {
        int v = stoi(sa);
        int tt = v * n;
        string sb = to_string(tt);
        if(sb.size() <= 5) {
            bool is_valid = true;
            for(int i = 0; i < 16; i++)
                vis[i] = dig[i];

            for(int i = 0; sb[i]; i++) {
                if(vis[sb[i]-'0']) {
                    is_valid = false;
                    break;
                }
                else 
                    vis[sb[i]-'0'] = true;
            }

            if(is_valid) {
                is_have = true;
                if(sb.size() == 4) {
                    if(!vis[0])
                        cout << "0" << sb << " / " << sa << " = " << n << endl;
                }

                else
                    cout << sb << " / " << sa << " = " << n << endl;
            }
        }
        return ;
    }
    
    for(int i = 0; i <= 9; i++)
        if(!dig[i]) {
            dig[i] = true;
            dfs(p + 1, sa + to_string(i));
            dig[i] = false;
        }
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif

    bool is_first = true;
    while(cin >> n) {
        if(!n) break;

        is_have = false;
        memset(dig, false, sizeof(dig));

        if(is_first) is_first = false;
        else cout << endl;

        dfs(1, "");
        if(!is_have)
            cout << "There are no solutions for " << n << "." << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

/**************************************************

filename :c.cpp

author :maksyuki

created time :2018/6/11 0:08:30

last modified :2018/6/11 9:51:42

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int n;

bool is_have = false;

bool dig[16];

bool vis[16];

void dfs(int p, string sa) {

if(p == 6) {

int v = stoi(sa);

int tt = v * n;

string sb = to_string(tt);

if(sb.size() <= 5) {

bool is_valid = true;

for(int i = 0; i < 16; i++)

vis[i] = dig[i];

for(int i = 0; sb[i]; i++) {

if(vis[sb[i]-'0']) {

is_valid = false;

break;

}

else

vis[sb[i]-'0'] = true;

}

if(is_valid) {

is_have = true;

if(sb.size() == 4) {

if(!vis[0])

cout << "0" << sb << " / " << sa << " = " << n << endl;

}

else

cout << sb << " / " << sa << " = " << n << endl;

}

return ;

}

for(int i = 0; i <= 9; i++)

if(!dig[i]) {

dig[i] = true;

dfs(p + 1, sa + to_string(i));

dig[i] = false;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

bool is_first = true;

while(cin >> n) {

if(!n) break;

is_have = false;

memset(dig, false, sizeof(dig));

if(is_first) is_first = false;

else cout << endl;

dfs(1, "");

if(!is_have)

cout << "There are no solutions for " << n << "." << endl;

}

return 0;

}

Codeforces Round #486(Div.3) (6/6)

uva11059

超客的水墨烟雨

uva725

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30