Lotplace

本人於該blog的全部文章轉移至[UVA] 00725 Division – KKWBlog (kkwtech.com)該網域下，其後此處不進行更新，一律於新站點更新。

作者廢話:
大三想說來刷一波cpe所以就順手寫下解題紀錄順便讓自己再次釐清解題思路

d183. 00725 – Division – 高中生程式解題系統 (zerojudge.tw)
題目擷取至zerojudge
題目重點:
給一個數字找出1對的被除數跟除數能得出該數字
並且條件為5位數並且各數字不能重複(容許1個0出現在數字首位)

解題思路:
先定義符號方便說明:被除數x,除數y,輸入:z
首先先確認x跟除y的有效範圍，因為是5位數又能容許1個0，因此該0只會出現在除數，否則x<y
x: 最大值為5位不重複數字即:98765且永遠等於y*z
y: 最小值為1234
再來是演算法的部分:
因為x / y = z => x = y * z，所以在知道z的狀況下就可以從1234到98765/2(最小輸入為2)開始測試y，知道了y、z就能得出x了，最後在確認有無重複的數字就能成功得到解。
以上方法可以須至少遍歷1234~98765/2次數，但其實從題目給的有效範圍下手就能將次數降低，前面提到x的最大值只能為98765因此可以多加個條件x > 98765時結束遍歷，次數降低為1234~98765/z

#include <iostream>
#include <iomanip>
using namespace std;
bool isrepeat(int a, int i)
{
    //創建check array紀錄有無重複的數字出現
    bool check[10];
    for (int i = 0; i < 10; i++)
    {
        check[i] = false;
    }
    //若2數皆小於10000代表有2個0出現，視為重複
    if (a < 10000 && i < 10000)
    {
        return false;
    }
    //有1個0出現因此將0設為已出現
    if (a < 10000 || i < 10000)
    {
        check[0] = true;
    }
    //遍歷數字
    while (a > 0)
    {
        if (check[a % 10])
        {
            return false;
        }
        check[a % 10] = true;
        a /= 10;
    }
    while (i > 0)
    {
        if (check[i % 10])
        {
            return false;
        }
        check[i % 10] = true;
        i /= 10;
    }
    return true;
}
int main()
{
    int input = 0;
    int a = 0;          //被除數
    bool exist = false; //有無解的出現
    while (1)
    {
        cin >> input;
        if (input == 0)
            break;
        for (int i = 1234; i <= 49382; i++)
        {
            a = input * i;
            if (a > 98765)
            {
                break;
            }
            if (isrepeat(a, i))
            {
                cout << setw(5) << setfill('0') << a;
                cout << " / ";
                cout << setw(5) << setfill('0') << i;
                cout << " = " << input << endl;
                exist = true;
            }
        }
        if (!exist)
        {
            printf("There are no solutions for %d.\n", input);
        }
        exist = false;
    }
}

---

Filed under: UVA - @ 2021 年 9 月 2 日 下午 4:40

標籤: uva