WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM610 Div2 Easy "DivideByZero"

問題

TopCoder Statistics - Problem Statement

ジョンはそれぞれ違った数値が書かれた紙を持っていた。あなたはint[] numbersが与えられる。その数値のリストはジョンが持っている紙に書かれた数値を表している。

ジョンは今、新たに数値が書かれた紙を加えようとしている。そうするために、彼は整数の割り算を利用する。ここでいう割り算では、結果の余りを捨てる。例えば、15 / 5 = 3であり、24 / 5 = 4である。

ジョンは次の操作を繰り返す。任意の2枚の紙を選び、そこに書かれている大きいほうの数値をA,他方をBとする。C = A / Bとする。もしCと書かれた紙がない場合、Cを紙に書いてそれを加える。

この操作を紙を加えることができなくなるまで繰り返す。最終的に、何枚の紙を持つことになるのかを返せ。

制約

1 <= numbers.size() <= 100
1 <= 紙に書かれた数値 <= 100


考えたこと

シミュレートするだけ


ソースコード

class DivideByZero {

    public:

    int CountNumbers(vector <int> numbers) {
        

        while (true) {
            int N = numbers.size();
            sort(numbers.begin(), numbers.end(), greater<int>());
            bool update = false;
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    int add = numbers[i] / numbers[j];
                    bool ok = true;
                    for (int k = 0; k < numbers.size(); k++) {
                        if (numbers[k] == add) ok = false;
                    }
                    if (ok) {
                        numbers.push_back(add);
                        update = true;
                    }
                }
            }
            if (!update) break;
        }
        
        return numbers.size();
    }
};