Задача на переливания (задача на граф)

[WarM19]

В наличии имеется три сосуда, объемом N, M, K литров соответственно. Изначально они заполнены водой на X, Y, Z литров. Необходимо объем воды X + Y + Z разделить между сосудами так, чтобы в первом сосуде было P литров, во втором Q литров и в третьем R литров за минимально возможное число переливаний. Дополнительную воду использовать нельзя. Иногда такое разбиение выполнить невозможно.
Входные данные.
Данные читаются из файла с именем “input.txt”.
Структура файла:
N M K
X Y Z
P Q R
Выходные данные.
В файл “output.txt” вывести единственное число – число переливаний, необходимое для того, чтобы разделить воду между сосудами. Если разбиение осуществить невозможно, то вывести -1.
Ограничения.
1 <= N, M, K, X, Y, Z, P, Q, R <= 10000.
N >= X
M >=Y
K >= Z
X + Y + Z = P + Q + R
Не более 2 секунд на тест.
Пример.
Input.txt Output.txt
3 2 1 2
1 2 1
3 1 0
Очень надеюсь на помощь, если честно уже задолбался, надеюсь кто-нибудь поможет, заранее спасибо!

[digitalis]

Все кинулись помогать и уткнулись в : на каком языке, соб-сно?

[evg_m]

3 переливания. (кто меньше? )

1, 2. X-P разлить во второй (X1) и третий (X-P-X1)
3. Y+X1-Q вылить в третий.

Иногда такое разбиение выполнить невозможно.

Z+(X-P-X1) +(Y+X1-Q) <> R

P.S. в требованиях задач кое-что пропущено.

[Serge_Bliznykov]

Сообщение от digitalis

Все кинулись помогать и уткнулись в : на каком языке, соб-сно?

а Вы сможете алгоритм решения расписать?
можно просто словесный. Или в виде блок-схемы?

я, например, не могу.

[Serge_Bliznykov]

Сообщение от evg_m

3 переливания. (кто меньше? )

это Вы для какой задачи 3 переливания насчитали?

для контрпримера из пост #1 два:
1) сначала полностью выливаем 3-й сосуд в первый.
2) выливаем из второго в первый до полноты.
итог
3 1 0

[val_nnm]

Написал на C#

using System;
using System.Collections.Generic;
namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            Tuple<int, int, int> volume = new Tuple<int, int, int>(3, 2, 1);
            Tuple<int, int, int> target = new Tuple<int, int, int>(3, 1, 0);

            //Вновь полученные варианты которые нужно разливать другими способами
            HashSet<Tuple<int, int, int>> newAll = new HashSet<Tuple<int, int, int>>();
            newAll.Add(new Tuple<int, int, int>(1, 2, 1));

            //Все варианты уже рассмотренные ранее которые можно не обрабатывать заново
            HashSet<Tuple<int, int, int>> all = new HashSet<Tuple<int, int, int>>(newAll);

            int count = -1;
            while (newAll.Count>0)
            {
                count++;
                if (newAll.Contains(target)) break;
                HashSet<Tuple<int, int, int>> newAvailable = new HashSet<Tuple<int, int, int>>();
                foreach (var tmp in newAll)
                {
                    //Судя по условия X + Y + Z = P + Q + R воду выливать нельзя. Если воду выливать разрешено, то разкоментировать следующие строки.
                    //newAvailable.Add(new Tuple<int, int, int>(0, tmp.Item2, tmp.Item3)); // Выливаем воду из 1
                    //newAvailable.Add(new Tuple<int, int, int>(tmp.Item1, 0, tmp.Item3)); // Выливаем воду из 2
                    //newAvailable.Add(new Tuple<int, int, int>(tmp.Item1, tmp.Item2, 0)); // Выливаем воду из 3

                    {
                        var v = Math.Min(tmp.Item1, volume.Item2 - tmp.Item2);
                        newAvailable.Add(new Tuple<int, int, int>(tmp.Item1 - v, tmp.Item2 + v, tmp.Item3)); // Переливаем воду из 1 в 2
                    }

                    {
                        var v = Math.Min(tmp.Item1, volume.Item3 - tmp.Item3);
                        newAvailable.Add(new Tuple<int, int, int>(tmp.Item1 - v, tmp.Item2, tmp.Item3 + v)); // Переливаем воду из 1 в 3
                    }
                    {
                        var v = Math.Min(tmp.Item2, volume.Item1 - tmp.Item1);
                        newAvailable.Add(new Tuple<int, int, int>(tmp.Item1 + v, tmp.Item2 - v, tmp.Item3)); // Переливаем воду из 2 в 1
                    }
                    {
                        var v = Math.Min(tmp.Item2, volume.Item3 - tmp.Item3);
                        newAvailable.Add(new Tuple<int, int, int>(tmp.Item1, tmp.Item2 - v, tmp.Item3 + v)); // Переливаем воду из 2 в 3
                    }
                    {
                        var v = Math.Min(tmp.Item3, volume.Item1 - tmp.Item1);
                        newAvailable.Add(new Tuple<int, int, int>(tmp.Item1 + v, tmp.Item2, tmp.Item3 - v)); // Переливаем воду из 3 в 1
                    }
                    {
                        var v = Math.Min(tmp.Item3, volume.Item2 - tmp.Item2);
                        newAvailable.Add(new Tuple<int, int, int>(tmp.Item1, tmp.Item2 + v, tmp.Item3 - v)); // Переливаем воду из 3 в 2
                    }
                }
                newAll.Clear();
                foreach (var tmp in newAvailable)
                {
                    if (all.Add(tmp))
                    {
                        newAll.Add(tmp);
                    }
                }
            }
            if (newAll.Count == 0) count = -1;
            Console.WriteLine(count);
            Console.ReadLine();
        }
    }
}

Только полноценно тестировать код сейчас нет времени, воспринимайте это лишь как общую идею алгоритма решения. (в коде могут быть ошибки)

[ViktorR]

Так понимаю, что сосуды переставлять нельзя.

...разделить между сосудами так, чтобы в первом сосуде было P литров, во втором Q литров и в третьем R литров...

Если построить разности между тем, что есть и тем что необходимо, то станет понятно откуда брать и куда лить.

Input.txt	Output.txt
 3 2 1	           2
 1 2 1
 3 1 0
------
-2 1 1

Может есть и другие варианты?
Предварительно контролируем соответствие объёма сосуда требуемому объёму воды.