https://atcoder.jp/contests/abc074/tasks/arc083_a
この問題をDFS(深さ優先探索)で解こうと思い、実装してみたのですが、下記の入力例3で無限ループになってしまい解けません。
なぜでしょうか?
書いたコード:
#include <bits/stdc++.h>
int a, b, c, d, e, f;
std::vector<std::tuple<long double, int, int>> vec;
void dfs(int water, int sugar, int limit) {
std::cout << "water:" << water <<"," << "sugar:" <<sugar << std::endl;
if (water+sugar > limit) { //溶液の質量がビーカーより大きい
return;
}
if (sugar > (water/100)*e) { // 砂糖が溶け残る
return;
}
long double density = 100*sugar/(water+sugar); // 密度(濃度を計算)
vec.push_back(std::make_tuple(density, water, sugar)); // vecに格納
dfs(water+100*a, sugar, limit);
dfs(water+100*b, sugar, limit);
dfs(water, sugar+c, limit);
dfs(water, sugar+d, limit);
}
int main() {
std::cin >> a >> b >> c >> d >> e >> f;
dfs(100*a, 0, f);
dfs(100*b, 0, f);
auto e = *std::max_element(vec.begin(), vec.end()); //一番濃度の高いvecを取得。
std::cout << std::get<1>(e) + std::get<2>(e) << " " << std::get<2>(e) << std::endl;
}
すぬけ君はビーカーに砂糖水を作ろうとしています。 最初ビーカーは空です。すぬけ君は以下の
4種類の操作をそれぞれ何回でも行うことができます。一度も行わない操作があっても構いません。操作 1: ビーカーに水を 100A[g] 入れる。
操作 2: ビーカーに水を 100B[g] 入れる。
操作 3: ビーカーに砂糖をC[g] 入れる。
操作 4: ビーカーに砂糖を D[g] 入れる。すぬけ君の実験環境下では、水 100[g] あたり砂糖は E[g] 溶けます。
すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。
ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が F[g] 以下であり、
ビーカーの中に砂糖を溶け残らせてはいけないとき、 すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。
答えが複数ある場合はどれを答えても構いません。水 a[g] と砂糖 b [g] を混ぜた砂糖水の濃度は 100b/(a+b) [%]です。 また、この問題では、砂糖が全く溶けていない水も濃度0[%] の砂糖水と考えることにします。
制約
1≦A 1≦C 1≦E≦100
100A≦F≦3,000
A,B,C,D,E,Fはすべて整数である。入力
入力は以下の形式で標準入力から与えられる。
A B C D E F
出力 整数を空白区切りで 2つ出力せよ。 1つ目は求める砂糖水の質量、2つ目はそれに溶けている砂糖の質量とせよ。
入力例 1
1 2 10 20 15 200
出力例 1
110 10
入力例2
1 2 1 2 100 1000
出力例 2
200 100
入力例 3
17 19 22 26 55 2802
出力例 3
2634 934