Đong nước

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 977M
Author:
TICHPX
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Toto bắt đầu học nhập môn trí tuệ nhân tạo với các thuật toán \(A^*\). Toto thích thú với bài toán đong nước, thuật toán rất hay nhưng trình độ lập trình còn yếu nên không thể lập trình được. Bạn hãy giúp Toto nhé

Bài toán: Cho hai bình có sức chứa là n và m lít hãy tìm cách đong k lít nước biết rằng mỗi lần đong có thể đổ hết nước trong một bình đi, hoặc đổ thêm nước vào một bình, hoặc đổ nước từ bình nọ sang bình kia và cho số lượng nước để sử dụng là vô hạn và ban đầu hai bình đều chưa chứa nước.

Input

Một dòng gồm 3 số nguyên n,m,k \((1<=n,m,k<=10000)\)

Ouput

Nếu không đong được xuất ra "Khong dong duoc nuoc", ngược lại chỉ ra số bước ít nhất để đong được k lít nước.

Ví dụ 1.

Input

3 5 4

Output

6

Giải thích : Các trạng thái đong nước như sau : \((0,0)->(0,5)->(3,2)->(0,2)->(2,0)->(2,5)->(3,4)\)

Ví dụ 2.

Input

122 24 11

Output

Khong dong duoc nuoc
tichpx

Comments


  • -2
    asus  commented on May 9, 2023, 8:55 a.m. 
    #include<bits/stdc++.h>
using namespace std;
int BFS(int n,int m,int k)  //so buoc it nhat
{
    queue<pair<int,int> > Q;
    map<pair<int,int>,int> M;
    M[{0,0}]=1;
    Q.push({0,0});
    while(Q.size())
    {
        int x=Q.front().first,y=Q.front().second,z=x+y;
        Q.pop();
        pair<int,int> Next[]={{0,y},{n,y},{x,0},{x,m},{max(0,z-m),
        min(z,m)},{min(z,n),max(0,z-n)}};
        for(auto v:Next)
        if(M[v]==0) //chua co 
        {
            M[v]=M[{x,y}]+1;
            Q.push(v);
            if(v.first==k||v.second==k) return M[v]-1;
        }
    }
    return -1;
}
int main()
{
    cout<<BFS(3,5,4);

}