题目描述
有三个杯子,容量分别为 A,B,C。
初始时,C 杯装满了水,而 A,B 杯都是空的。
现在在保证不会有漏水的情况下进行若干次如下操作:
将一个杯子 x 中的水倒到另一个杯子 y 中,当 x 空了或者 y 满了时就停止(满足其中一个条件才停下)。
请问,在操作全部结束后,C 中的水量有多少种可能性。
输入格式
输入包含多组测试数据。
每组数据占一行,包含三个整数 A,B,C。
输出格式
每组数据输出一个结果,占一行。
数据范围
0≤A,B,C≤4000,
每个输入最多包含 100 组数据。
样例
输入样例:
0 5 5
2 2 4
输出样例:
2
3
算法1
(暴力枚举) $O()$
1.python3 TLE了。
时间复杂度
参考文献
python3 代码
import sys
from typing import List
sys.setrecursionlimit(100000)
radix = 5000
def get_state(cur: List[int]) -> int:
res = cur[0] * 5000 * 5000 + cur[1] * 5000 + cur[2]
return res
def main():
def pour(cur: List[int], i: int, j: int) -> None:
t = min(cur[i], capacity[j] - cur[j])
cur[i] -= t
cur[j] += t
def dfs(cur: List) -> None:
state_set.add(get_state(cur))
c_set.add(cur[2])
a = [0, 0, 0]
for i in range(3):
for j in range(3):
if i != j:
for k in range(3):
a[k] = cur[k]
pour(a, i, j)
if get_state(a) not in state_set:
dfs(a)
capacity = [0 for _ in range(3)]
state_set = set()
c_set = set()
line = sys.stdin.readline()
while line:
capacity = [int(x) for x in line.split()]
state_set.clear()
c_set.clear()
cur = [0, 0, capacity[2]]
dfs(cur)
res = len(c_set)
print(res)
line = sys.stdin.readline()
if __name__ == '__main__':
main()
C++ 代码
#include <iostream>
#include <string.h>
#include <algorithm>
#include <unordered_set>
using namespace std;
long long radix = 5000;
int capacity[3];
unordered_set<long long>state_set;
unordered_set<int> c_set;
long long get_state(int cur [])
{
long long res = cur[0] * radix * radix + cur[1] * radix + cur[2];
return res;
}
void pour(int cur [], int i, int j)
{
int t = min(cur[i], capacity[j] - cur[j]);
cur[i] -= t;
cur[j] += t;
}
void dfs(int cur[])
{
state_set.insert(get_state(cur));
c_set.insert(cur[2]);
int a[3];
for (int i = 0; i < 3; i ++)
{
for (int j = 0; j < 3; j ++)
{
if (i != j)
{
memcpy(a, cur, sizeof(a));
pour(a, i, j);
if (state_set.find(get_state(a)) == state_set.end())
{
dfs(a);
}
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >> capacity[0] >> capacity[1] >> capacity[2])
{
state_set.clear();
c_set.clear();
int cur[3] = {0, 0, capacity[2]};
dfs(cur);
cout << (int)c_set.size() << endl;
}
return 0;
}
java 代码
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
public class Main
{
static int radix = 5000; //进制
static int [] capacity = new int [3]; //容量
static Set<Long> state_set = new HashSet<>(); //3个杯子的状态
static Set<Integer> c_set = new HashSet<>(); //C杯容量的情况
static long get_state(int [] nums)
{
long res = nums[0] * radix * radix + nums[1] * radix + nums[2];
return res;
}
static void pour(int [] cur, int i, int j)
{
int t = Math.min(cur[i], capacity[j] - cur[j]);
cur[i] -= t;
cur[j] += t;
}
static void dfs(int [] cur)
{
state_set.add(get_state(cur));
c_set.add(cur[2]);
int [] a = new int[3];
for (int i = 0; i < 3; i ++)
{
for (int j = 0; j < 3; j ++)
{
if (i != j)
{
System.arraycopy(cur, 0, a, 0, 3);
pour(a, i, j);
if (state_set.contains(get_state(a)) == false )
{
dfs(a);
}
}
}
}
}
public static void main(String [] args) throws Exception
{
Scanner scan = new Scanner(System.in);
while (scan.hasNext() == true)
{
capacity[0] = scan.nextInt();
capacity[1] = scan.nextInt();
capacity[2] = scan.nextInt();
int [] cur = new int [] {0, 0, capacity[2]};
state_set.clear();
c_set.clear();
dfs(cur);
int res = c_set.size();
System.out.println(res);
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla