10962022-03-02 21:01:27peti1234Vizeskannákcpp14Elfogadva 40/4012ms3340 KiB
#include <bits/stdc++.h>

using namespace std;
int m1, m2, m3, l;
set<pair<int, int> > volt;
queue<pair<pair<int, int>, int> > q;

void pb(int a, int b, int db) {
    // ha meg nem volt, az (a, b, c), akkor innen is folytatodik a bejaras
    if (volt.find({a, b})==volt.end()) {
        volt.insert({a, b});
        q.push({{a, b}, db});
    }
}
int main()
{
    cin >> m1 >> m2 >> m3 >> l;
    pb(m1, 0, 0);
    // az alap allapot

    // sima szelességi bejaras
    while (q.size()>0) {
        int a=q.front().first.first, b=q.front().first.second, c=m1-a-b, db=q.front().second;
        // igy egyszerubb egy allapaotot tarolni (a, b, c - hany liter van egy-egy kannaban, db - eddig hany lepest tettunk meg)
        q.pop();
        if (a==l || b==l || c==l) {
            // ha megvan az l liter, akkor keszen vagyunk
            cout << db << "\n";
            return 0;
        }
        db++;

        // 6 lehetoseg van sorban: a->b, b->a, a->c, c->a, b->c, c->b

        int kul=min(a, m2-b);
        pb(a-kul, b+kul, db);

        kul=min(m1-a, b);
        pb(a+kul, b-kul, db);

        kul=min(a, m3-c);
        pb(a-kul, b, db);

        kul=min(m1-a, c);
        pb(a+kul, b, db);

        kul=min(b, m3-c);
        pb(a, b-kul, db);

        kul=min(m2-b, c);
        pb(a, b+kul, db);

    }

    // ha a bejarassal nem talaltunk, akkor nincs megoldas
    cout << -1 << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/02ms1792 KiB
2Elfogadva0/01ms1784 KiB
3Elfogadva1/11ms1852 KiB
4Elfogadva1/11ms1864 KiB
5Elfogadva1/11ms1864 KiB
6Elfogadva1/11ms1864 KiB
7Elfogadva1/11ms1868 KiB
8Elfogadva1/11ms1872 KiB
9Elfogadva1/11ms1876 KiB
10Elfogadva1/11ms1880 KiB
11Elfogadva1/11ms1884 KiB
12Elfogadva1/11ms1892 KiB
13Elfogadva2/21ms1896 KiB
14Elfogadva2/21ms1896 KiB
15Elfogadva2/21ms1904 KiB
16Elfogadva2/21ms1904 KiB
17Elfogadva2/21ms1916 KiB
18Elfogadva2/21ms1912 KiB
19Elfogadva2/21ms1916 KiB
20Elfogadva2/22ms1960 KiB
21Elfogadva2/21ms1932 KiB
22Elfogadva2/21ms1932 KiB
23Elfogadva2/21ms1956 KiB
24Elfogadva2/27ms2788 KiB
25Elfogadva2/24ms2488 KiB
26Elfogadva2/212ms3340 KiB
27Elfogadva2/28ms3060 KiB