ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1437. ACM для ГСМ

I got AC! But i have question
Послано Felix_Mate 13 июл 2015 10:29
Я решил задачу с помощью графа, где вершинки - состояния ёмкостей,и рассмотрел из очередного состояния все переходы, запоминая те состояния ,где уже был.
Но я никак не могу оценить кол-во возможных состояний. Может кто-нибудь подскажет как оценить? Самая грубая оценка - у нас есть числа a,b,c>=0 и a+b+c=N(для случая,когда не подливаем и не выливаем-в этом случае сумма константа). Тогда количество таких чисел O(N^3),но это ужасная оценка.
Re: I got AC! But i have question
Послано a2ch 15 ноя 2019 15:20
Согласен, было бы интересно узнать максимальное количество возможных состояний и при каких значениях a,b,c оно достигается

Edited by author 16.11.2019 13:00
Re: I got AC! But i have question
Послано InstouT94 28 мар 2023 13:43
Можно оценивать так: пусть ёмкости не превосходят значения C. Рассмотрим возможные переходы между состояниями.
1) Когда подливаем из заправки в канистру. Тогда канистра, в которую подливаем, становится полной.
2) Когда переливаем между канистрами. Тогда либо канистра, в которую переливаем, становится полной, либо канистра, из которой переливаем, становится пустой (либо и то, и то).
Получается, что в каждом состоянии хотя бы одна канистра либо пустая, либо полная. Тогда количество состояний можно оценить как 6*(С+1)^2, то бишь O(C^2).