|
|
back to boardI got AC! But i have question Я решил задачу с помощью графа, где вершинки - состояния ёмкостей,и рассмотрел из очередного состояния все переходы, запоминая те состояния ,где уже был. Но я никак не могу оценить кол-во возможных состояний. Может кто-нибудь подскажет как оценить? Самая грубая оценка - у нас есть числа a,b,c>=0 и a+b+c=N(для случая,когда не подливаем и не выливаем-в этом случае сумма константа). Тогда количество таких чисел O(N^3),но это ужасная оценка. Re: I got AC! But i have question Posted by a2ch 15 Nov 2019 15:20 Согласен, было бы интересно узнать максимальное количество возможных состояний и при каких значениях a,b,c оно достигается Edited by author 16.11.2019 13:00 Re: I got AC! But i have question Можно оценивать так: пусть ёмкости не превосходят значения C. Рассмотрим возможные переходы между состояниями. 1) Когда подливаем из заправки в канистру. Тогда канистра, в которую подливаем, становится полной. 2) Когда переливаем между канистрами. Тогда либо канистра, в которую переливаем, становится полной, либо канистра, из которой переливаем, становится пустой (либо и то, и то). Получается, что в каждом состоянии хотя бы одна канистра либо пустая, либо полная. Тогда количество состояний можно оценить как 6*(С+1)^2, то бишь O(C^2). |
|
|