Я решил задачу с помощью графа, где вершинки - состояния ёмкостей,и рассмотрел из очередного состояния все переходы, запоминая те состояния ,где уже был.
Но я никак не могу оценить кол-во возможных состояний. Может кто-нибудь подскажет как оценить? Самая грубая оценка - у нас есть числа a,b,c>=0 и a+b+c=N(для случая,когда не подливаем и не выливаем-в этом случае сумма константа). Тогда количество таких чисел O(N^3),но это ужасная оценка.

Согласен, было бы интересно узнать максимальное количество возможных состояний и при каких значениях a,b,c оно достигается

Edited by author 16.11.2019 13:00

Можно оценивать так: пусть ёмкости не превосходят значения C. Рассмотрим возможные переходы между состояниями.
1) Когда подливаем из заправки в канистру. Тогда канистра, в которую подливаем, становится полной.
2) Когда переливаем между канистрами. Тогда либо канистра, в которую переливаем, становится полной, либо канистра, из которой переливаем, становится пустой (либо и то, и то).
Получается, что в каждом состоянии хотя бы одна канистра либо пустая, либо полная. Тогда количество состояний можно оценить как 6*(С+1)^2, то бишь O(C^2).