二つの水差しでぴったり量る手順

from collections import deque  def 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 None  q = 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)))

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"));

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"));

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);    }}

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);    }}

#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';    }}

#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;}

// 빈 두 물통에서 한쪽에 딱 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.つなぐ(" "));    }}