有两个没有刻度的水壶。 A 壶最多装 A 升，B 壶最多装 B 升。 开始时两个壶都是空的，每次可以做下面六种操作中的一种。 每种操作都有编号。 - 1：用水龙头把 A 壶装满。 2：把 B 壶装满。 - 3：把 A 壶的水全部倒掉。 4：把 B 壶的水全部倒掉。 - 5：把 A 壶的水倒进 B 壶。 一直倒到 A 壶空了或 B 壶满了为止，水既不会溢出也不会消失。 - 6：用同样的方法把 B 壶的水倒进 A 壶。 求让两个壶中的某一个刚好装有 t 升的最短操作顺序。 如果最短的顺序有好几种，就从前往后比较操作编号，选在第一个不同位置上编号较小的那一种。 答案先写操作次数 k，接着按顺序写 k 个操作编号。 如果一开始某个壶里就有 t 升（t = 0），只输出 0。 如果怎样都做不到，输出 -1。
输入
第一行为询问数 q（1 ≤ q ≤ 20）。 接下来 q 行为 A、B、t（1 ≤ A, B ≤ 90，0 ≤ t ≤ 90）
输出
每个询问一行，输出 "k 操作1 … 操作k"（用一个空格分隔），或 -1
样例 1 · stdin
4
3 5 4
2 4 3
7 7 0
1 4 2
stdout
6 2 6 3 6 2 6
-1
0
4 1 5 1 5
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
把两个壶中的水量 (a, b) 看作一个格子，一次操作就是从格子到格子的一步。 最短的顺序用广度优先搜索（BFS）来求。 从队列前面取出、把新格子放到后面，就会依次取出 0 步的格子、1 步的格子、2 步的格子，所以第一次取出目标格子时就是最短的。 为每个格子记下"第一次从哪个格子进来"和"当时做的操作"，再从目标格子沿着前一个格子一路回溯到 (0, 0)，就得到顺序。 从 1 号开始依次尝试操作，并且只在第一次到达时记录，同样步数的格子就会按编号靠前的顺序进入队列，于是自然选出编号较小的顺序。 格子最多 91 × 91 个，所以把 (a, b) 换成一个数 a * (B + 1) + b，记在一个列表里就够了。 队列各语言不同：Python collections.deque 的 popleft()，Java ArrayDeque 的 add、poll，C# Queue<T> 的 Enqueue、Dequeue，C++ std::queue 的 push、front、pop。 C 没有队列，要用数组和头尾下标来做；JS/TS 的 shift() 要从前面移除，可能较慢，所以在数组上放一个头下标并移动它。 Craykon 也用 添加 放入并移动头下标，在 新列表 里记下前一个格子和操作。"找不到"用 Python None、JS/TS/Java/C# null、C++ std::optional、Craykon 空 返回。 六个陷阱：① 从后面取出（Python pop()）就成了栈，变成深度优先搜索，第一次找到的路不是最短的。 Java ArrayDeque 的 push、pop 都用前端，同样会变成栈。 ② 倒的量是 min(a, B − b)。 接水的壶装满时把剩下的水倒掉（把倒水的壶设为 0），能量出的量就会不同。 ③ 只在新放入的格子上检查目标，会漏掉起始格子 (0, 0)，t = 0 时答出一次操作而不是 0。 ④ 目标是"某一个壶"，所以只有 B 壶是 t 的情况也算答案。 ⑤ 沿着前一个格子收集的操作是从结尾往开头倒着出来的。 要反转后再输出（Python [::-1]、JS/TS reverse()、Java Collections.reverse、C# List.Reverse()、C++ std::reverse、Craykon 反转()）。 ⑥ 不按编号顺序尝试操作（例如先试 B 的操作），当 A 一侧和 B 一侧有同样短的路时（像 1 4 2 那样），就会给出别的顺序。
Pythonmain.py · 36 行
from collections import dequedef shortest_plan(A, B, t): """빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 None.""" w = B + 1 # 상태 (a, b)를 수 하나 a * w + b로 적는다 prev = [-1] * ((A + 1) * w) # 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) move = [0] * ((A + 1) * w) # 그때 한 동작 번호 prev[0] = 0 queue = deque([0]) while queue: s = queue.popleft() a, b = divmod(s, w) if a == t or b == t: # 꺼낸 차례가 곧 가깝고 앞선 차례다 plan = [] while s != 0: # 앞 상태를 따라가면 끝에서 처음 쪽으로 거꾸로 나온다 plan.append(move[s]) s = prev[s] return plan[::-1] ab = min(a, B - b) # A에서 B로 부을 수 있는 양 ba = min(b, A - a) # B에서 A로 부을 수 있는 양 nexts = [(A, b), (a, B), (0, b), (a, 0), (a - ab, b + ab), (a + ba, b - ba)] for k, (na, nb) in enumerate(nexts, start=1): # 동작 번호가 작은 것부터 n = na * w + nb if prev[n] < 0: # 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s move[n] = k queue.append(n) return Noneq = int(input())for _ in range(q): A, B, t = map(int, input().split()) plan = shortest_plan(A, B, t) print(-1 if plan is None else " ".join(map(str, [len(plan)] + plan)))
JavaScriptmain.js · 41 行
const lines = require("fs").readFileSync(0, "utf8").trim().split("\n");// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 nullfunction shortestPlan(A, B, t) { const w = B + 1; // 상태 (a, b)를 수 하나 a * w + b로 적는다 const prev = new Array((A + 1) * w).fill(-1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) const move = new Array((A + 1) * w).fill(0); // 그때 한 동작 번호 prev[0] = 0; const queue = [0]; for (let head = 0; head < queue.length; head++) { // shift() 대신 머리 번호를 옮긴다 let s = queue[head]; const a = Math.floor(s / w); const b = s % w; if (a === t || b === t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 const plan = []; for (; s !== 0; s = prev[s]) plan.push(move[s]); // 끝에서 처음 쪽으로 거꾸로 나온다 return plan.reverse(); } const ab = Math.min(a, B - b); // A에서 B로 부을 수 있는 양 const ba = Math.min(b, A - a); // B에서 A로 부을 수 있는 양 const nexts = [[A, b], [a, B], [0, b], [a, 0], [a - ab, b + ab], [a + ba, b - ba]]; nexts.forEach(([na, nb], k) => { // 동작 번호(k + 1)가 작은 것부터 const n = na * w + nb; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.push(n); } }); } return null;}const q = Number(lines[0]);const out = [];for (let i = 1; i <= q; i++) { const [A, B, t] = lines[i].trim().split(" ").map(Number); const plan = shortestPlan(A, B, t); out.push(plan === null ? "-1" : [plan.length, ...plan].join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 42 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").trim().split("\n");// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 nullfunction shortestPlan(A: number, B: number, t: number): number[] | null { const w = B + 1; // 상태 (a, b)를 수 하나 a * w + b로 적는다 const prev: number[] = new Array((A + 1) * w).fill(-1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) const move: number[] = new Array((A + 1) * w).fill(0); // 그때 한 동작 번호 prev[0] = 0; const queue: number[] = [0]; for (let head = 0; head < queue.length; head++) { // shift() 대신 머리 번호를 옮긴다 let s = queue[head]; const a = Math.floor(s / w); const b = s % w; if (a === t || b === t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 const plan: number[] = []; for (; s !== 0; s = prev[s]) plan.push(move[s]); // 끝에서 처음 쪽으로 거꾸로 나온다 return plan.reverse(); } const ab = Math.min(a, B - b); // A에서 B로 부을 수 있는 양 const ba = Math.min(b, A - a); // B에서 A로 부을 수 있는 양 const nexts: [number, number][] = [[A, b], [a, B], [0, b], [a, 0], [a - ab, b + ab], [a + ba, b - ba]]; nexts.forEach(([na, nb], k) => { // 동작 번호(k + 1)가 작은 것부터 const n = na * w + nb; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.push(n); } }); } return null;}const q = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= q; i++) { const [A, B, t] = lines[i].trim().split(" ").map(Number); const plan = shortestPlan(A, B, t); out.push(plan === null ? "-1" : [plan.length, ...plan].join(" "));}console.log(out.join("\n"));
JavaMain.java · 66 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.StringTokenizer;public class Main { // 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 null // 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다 static List<Integer> shortestPlan(int A, int B, int t) { int w = B + 1; int[] prev = new int[(A + 1) * w]; // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) int[] move = new int[(A + 1) * w]; // 그때 한 동작 번호 Arrays.fill(prev, -1); prev[0] = 0; ArrayDeque<Integer> queue = new ArrayDeque<>(); queue.add(0); while (!queue.isEmpty()) { int s = queue.poll(); // 앞에서 꺼낸다(add는 뒤에 넣는다) int a = s / w, b = s % w; if (a == t || b == t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 List<Integer> plan = new ArrayList<>(); for (; s != 0; s = prev[s]) plan.add(move[s]); // 끝에서 처음 쪽으로 거꾸로 Collections.reverse(plan); return plan; } int ab = Math.min(a, B - b); // A에서 B로 부을 수 있는 양 int ba = Math.min(b, A - a); // B에서 A로 부을 수 있는 양 int[][] nexts = {{A, b}, {a, B}, {0, b}, {a, 0}, {a - ab, b + ab}, {a + ba, b - ba}}; for (int k = 0; k < 6; k++) { // 동작 번호(k + 1)가 작은 것부터 int n = nexts[k][0] * w + nexts[k][1]; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.add(n); } } } return null; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); int A = Integer.parseInt(st.nextToken()); int B = Integer.parseInt(st.nextToken()); int t = Integer.parseInt(st.nextToken()); List<Integer> plan = shortestPlan(A, B, t); if (plan == null) { out.append(-1).append('\n'); continue; } out.append(plan.size()); for (int k : plan) out.append(' ').append(k); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 58 行
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ // 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 null // 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다 static List<int>? ShortestPlan(int A, int B, int t) { int w = B + 1; var prev = Enumerable.Repeat(-1, (A + 1) * w).ToArray(); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) var move = new int[(A + 1) * w]; // 그때 한 동작 번호 prev[0] = 0; var queue = new Queue<int>(); queue.Enqueue(0); while (queue.Count > 0) { int s = queue.Dequeue(); int a = s / w, b = s % w; if (a == t || b == t) // 꺼낸 차례가 곧 가깝고 앞선 차례다 { var plan = new List<int>(); for (; s != 0; s = prev[s]) plan.Add(move[s]); // 끝에서 처음 쪽으로 거꾸로 plan.Reverse(); return plan; } int ab = Math.Min(a, B - b); // A에서 B로 부을 수 있는 양 int ba = Math.Min(b, A - a); // B에서 A로 부을 수 있는 양 var nexts = new[] { (A, b), (a, B), (0, b), (a, 0), (a - ab, b + ab), (a + ba, b - ba) }; for (int k = 0; k < 6; k++) // 동작 번호(k + 1)가 작은 것부터 { int n = nexts[k].Item1 * w + nexts[k].Item2; if (prev[n] < 0) // 처음 닿을 때만 적는다(넣을 때 표시) { prev[n] = s; move[n] = k + 1; queue.Enqueue(n); } } } return null; } static void Main() { int q = int.Parse(Console.ReadLine()!.Trim()); var output = new StringBuilder(); for (int i = 0; i < q; i++) { int[] p = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); var plan = ShortestPlan(p[0], p[1], p[2]); output.Append(plan == null ? "-1" : string.Join(" ", plan.Prepend(plan.Count))).Append('\n'); } Console.Write(output); }}
C++main.cpp · 56 行
#include <algorithm>#include <iostream>#include <optional>#include <queue>#include <vector>// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 빈 optional// 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다std::optional<std::vector<int>> shortestPlan(int A, int B, int t) { int w = B + 1; std::vector<int> prev((A + 1) * w, -1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) std::vector<int> move((A + 1) * w, 0); // 그때 한 동작 번호 std::queue<int> queue; prev[0] = 0; queue.push(0); while (!queue.empty()) { int s = queue.front(); // front()로 읽고 pop()으로 뺀다 queue.pop(); int a = s / w, b = s % w; if (a == t || b == t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 std::vector<int> plan; for (; s != 0; s = prev[s]) plan.push_back(move[s]); // 끝에서 처음 쪽으로 거꾸로 std::reverse(plan.begin(), plan.end()); return plan; } int ab = std::min(a, B - b); // A에서 B로 부을 수 있는 양 int ba = std::min(b, A - a); // B에서 A로 부을 수 있는 양 int nexts[6][2] = {{A, b}, {a, B}, {0, b}, {a, 0}, {a - ab, b + ab}, {a + ba, b - ba}}; for (int k = 0; k < 6; k++) { // 동작 번호(k + 1)가 작은 것부터 int n = nexts[k][0] * w + nexts[k][1]; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.push(n); } } } return std::nullopt;}int main() { int q; std::cin >> q; while (q--) { int A, B, t; std::cin >> A >> B >> t; auto plan = shortestPlan(A, B, t); if (!plan) { std::cout << -1 << '\n'; continue; } std::cout << plan->size(); for (int k : *plan) std::cout << ' ' << k; std::cout << '\n'; }}
Cmain.c · 61 行
#include <stdio.h>#define MAXS (91 * 91)static int prev[MAXS]; /* 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) */static int move[MAXS]; /* 그때 한 동작 번호 */static int queue[MAXS]; /* 상태마다 한 번만 들어가니 이 크기면 된다 */static int plan[MAXS];static int min(int x, int y) { return x < y ? x : y; }/* 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호(가장 앞선 것)를 plan에 채우고 개수를 돌려준다. 안 되면 -1 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다 */static int shortest_plan(int A, int B, int t) { int w = B + 1; for (int s = 0; s < (A + 1) * w; s++) prev[s] = -1; int head = 0, tail = 0; prev[0] = 0; queue[tail++] = 0; while (head < tail) { int s = queue[head++]; int a = s / w, b = s % w; if (a == t || b == t) { /* 꺼낸 차례가 곧 가깝고 앞선 차례다 */ int len = 0; for (; s != 0; s = prev[s]) plan[len++] = move[s]; /* 끝에서 처음 쪽으로 거꾸로 */ for (int i = 0, j = len - 1; i < j; i++, j--) { int tmp = plan[i]; plan[i] = plan[j]; plan[j] = tmp; } return len; } int ab = min(a, B - b); /* A에서 B로 부을 수 있는 양 */ int ba = min(b, A - a); /* B에서 A로 부을 수 있는 양 */ int na[6] = {A, a, 0, a, a - ab, a + ba}; int nb[6] = {b, B, b, 0, b + ab, b - ba}; for (int k = 0; k < 6; k++) { /* 동작 번호(k + 1)가 작은 것부터 */ int n = na[k] * w + nb[k]; if (prev[n] < 0) { /* 처음 닿을 때만 적는다(넣을 때 표시) */ prev[n] = s; move[n] = k + 1; queue[tail++] = n; } } } return -1;}int main(void) { int q; scanf("%d", &q); while (q--) { int A, B, t; scanf("%d %d %d", &A, &B, &t); int len = shortest_plan(A, B, t); printf("%d", len); for (int i = 0; i < len; i++) printf(" %d", plan[i]); printf("\n"); } return 0;}
Craykonmain.cray · 59 行
// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 빈값// 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다가장짧은계획(A, B, t){ w = B + 1; prev = 新列表((A + 1) * w, -1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) move = 新列表((A + 1) * w, 0); // 그때 한 동작 번호 prev[0] = 0; queue = [0]; head = 0; // 목록 앞에서 빼지 않고 머리 번호를 옮긴다 当 (head < queue.数量) { s = queue[head]; head += 1; a = 数学.商(s, w); b = s % w; 如果 (a == t || b == t) { plan = []; 当 (s != 0) { plan.添加(move[s]); s = prev[s]; } plan.反转(); 返回 plan; } ab = 数学.较小值(a, B - b); // A에서 B로 부을 수 있는 양 ba = 数学.较小值(b, A - a); // B에서 A로 부을 수 있는 양 nexts = [A * w + b, a * w + B, b, a * w, (a - ab) * w + b + ab, (a + ba) * w + b - ba]; 循环 (k = 0; k < 6; k++) { n = nexts[k]; 如果 (prev[n] < 0) { prev[n] = s; move[n] = k + 1; queue.添加(n); } } } 返回 空;}q = 控制台.读行().去空白().转数字();循环 (i = 0; i < q; i++){ p = 控制台.读数字(); plan = 가장짧은계획(p[0], p[1], p[2]); 如果 (plan == 空) { 控制台.输出(-1); } 否则 { plan.插入(0, plan.数量); 控制台.输出(plan.连接(" ")); }}