fork download 
  1. const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
  2.  
  3. const isPossible = (a, b, c) =>
  4.   c <= Math.max(a, b) && c % gcd(a, b) === 0;
  5.  
  6. const minSteps = (a, b, c) => {
  7.   if (!isPossible(a, b, c)) return -1;
  8.  
  9.   const visited = new Set();
  10.   const queue = [[0, 0, 0]];
  11.  
  12.   while (queue.length) {
  13.     const [x, y, steps] = queue.shift();
  14.     if (x === c || y === c) return steps;
  15.  
  16.     const key = x + y;
  17.     if (visited.has(key)) continue;
  18.     visited.add(key);
  19.  
  20.     const nextStates = [
  21.       [a, y], [x, b],
  22.       [0, y], [x, 0],
  23.       [x - Math.min(x, b - y), y + Math.min(x, b - y)],
  24.       [x + Math.min(y, a - x), y - Math.min(y, a - x)]
  25.     ];
  26.  
  27.     for (const [nx, ny] of nextStates) {
  28.       queue.push([nx, ny, steps + 1]);
  29.     }
  30.   }
  31.  
  32.   return -1;
  33. };
  34.  
  35.  
  36. process.stdin.resume();
  37. process.stdin.setEncoding('utf8');
  38.  
  39. process.stdin.on('data', function (chunk) {
  40. 	var lines = chunk.toString().split('\n');
  41.  
  42.  
  43. const t = Number(lines[0]);
  44. let idx = 1;
  45.  
  46. for (let i = 0; i < t; i++) {
  47.   const a = Number(lines[idx++]);
  48.   const b = Number(lines[idx++]);
  49.   const c = Number(lines[idx++]);
  50.   console.log(minSteps(a, b, c));
  51. }
  52. });
  53.  
  54.  
Success #stdin #stdout 0.11s 36236KB
comments (?)
stdin 
2
5
2
3
2
3
4
stdout 
2
-1
https://ideone.com/dsjkPg
language:
Node.js (node 20.14)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!