A vending machine gives change to its customers.
There are four coins: 10, 50, 100 and 500 won.
The first line gives how many 10, 50, 100 and 500 won coins are in the machine, in that order.
The second line gives the number of customers q, and each of the next q lines gives a customer's price p and the money m they put in.
The money customers put in is collected separately and is never used as change.
Process the customers in order and print one line for each.
If m is less than p, print "short".
Otherwise make the change c = m - p with 500, 100, 50 and 10 won coins, in that order.
For each coin use as many as possible without going over the remaining amount or the number left in the machine.
If this makes exactly c, print how many 500, 100, 50 and 10 won coins were used, in that order, separated by single spaces, and remove those coins from the machine.
When c is 0 this is "0 0 0 0".
If this does not make exactly c, print "no change" and leave the machine's coins as they were.
Input
each coin count 0 to 1000, 1 ≤ q ≤ 100, 10 ≤ p ≤ 10000, 0 ≤ m ≤ 50000, p and m are multiples of 10
Output
one line per customer: four coin counts, "short", or "no change"
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The input lists the small coin first, but the calculation and the output go from the big coin. So loop over the array from back to front: Python range(3, -1, -1) (the end -1 is excluded, so it reaches 0), C family, JS and TS for (i = 3; i >= 0; i--), Craykon for (i = 3; i >= 0; i--). Looping from the small coin gives a wrong answer full of 10 won coins. The number to use is min(remaining / coin, coins left). The integer quotient is Python //, JS/TS Math.floor(a / b), Craykon Mathf.Quot(a, b), and in Java, C#, C and C++ / between ints already is the quotient. Common mistakes are forgetting the coins left, or removing coins while counting so that a failed customer still takes coins away. Count first, check success with a boolean ok = left == 0, and only then remove. The boolean type is Python bool (True/False), Java boolean, C# bool, C++ bool, C bool from <stdbool.h> (no header needed from C23), JS/TS boolean, Craykon true/false. With 10, 50, 100 and 500, each smaller coin divides every bigger one, so using the biggest coin first never misses an amount that could be made.
Pythonmain.py · 21 lines
COINS = [10, 50, 100, 500]stock = list(map(int, input().split()))q = int(input())for _ in range(q): p, m = map(int, input().split()) if m < p: print("short") else: left = m - p used = [0, 0, 0, 0] # 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for i in range(3, -1, -1): used[i] = min(left // COINS[i], stock[i]) left -= used[i] * COINS[i] ok = left == 0 if ok: for i in range(4): stock[i] -= used[i] print(used[3], used[2], used[1], used[0]) else: print("no change") # 자판기 동전은 건드리지 않았다
JavaScriptmain.js · 27 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const COINS = [10, 50, 100, 500];const stock = lines[0].trim().split(/\s+/).map(Number);const q = Number(lines[1]);const out = [];for (let t = 0; t < q; t++) { const [p, m] = lines[2 + t].trim().split(/\s+/).map(Number); if (m < p) { out.push("short"); } else { let left = m - p; const used = [0, 0, 0, 0]; // 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for (let i = 3; i >= 0; i--) { used[i] = Math.min(Math.floor(left / COINS[i]), stock[i]); left -= used[i] * COINS[i]; } const ok = left === 0; if (ok) { for (let i = 0; i < 4; i++) stock[i] -= used[i]; out.push([used[3], used[2], used[1], used[0]].join(" ")); } else { out.push("no change"); // 자판기 동전은 건드리지 않았다 } }}console.log(out.join("\n"));
TypeScriptmain.ts · 28 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const COINS: number[] = [10, 50, 100, 500];const stock: number[] = lines[0].trim().split(/\s+/).map(Number);const q: number = Number(lines[1]);const out: string[] = [];for (let t = 0; t < q; t++) { const [p, m] = lines[2 + t].trim().split(/\s+/).map(Number); if (m < p) { out.push("short"); } else { let left: number = m - p; const used: number[] = [0, 0, 0, 0]; // 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for (let i = 3; i >= 0; i--) { used[i] = Math.min(Math.floor(left / COINS[i]), stock[i]); left -= used[i] * COINS[i]; } const ok: boolean = left === 0; if (ok) { for (let i = 0; i < 4; i++) stock[i] -= used[i]; out.push([used[3], used[2], used[1], used[0]].join(" ")); } else { out.push("no change"); // 자판기 동전은 건드리지 않았다 } }}console.log(out.join("\n"));
JavaMain.java · 36 lines
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] coins = {10, 50, 100, 500}; int[] stock = new int[4]; for (int i = 0; i < 4; i++) stock[i] = sc.nextInt(); int q = sc.nextInt(); StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { int p = sc.nextInt(); int m = sc.nextInt(); if (m < p) { out.append("short\n"); } else { int left = m - p; int[] used = new int[4]; // 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for (int i = 3; i >= 0; i--) { used[i] = Math.min(left / coins[i], stock[i]); left -= used[i] * coins[i]; } boolean ok = left == 0; if (ok) { for (int i = 0; i < 4; i++) stock[i] -= used[i]; out.append(used[3]).append(' ').append(used[2]).append(' ') .append(used[1]).append(' ').append(used[0]).append('\n'); } else { out.append("no change\n"); // 자판기 동전은 건드리지 않았다 } } } System.out.print(out); }}
C#Main.cs · 42 lines
using System;using System.Linq;class Program{ static void Main() { int[] coins = { 10, 50, 100, 500 }; int[] stock = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int q = int.Parse(Console.ReadLine()); for (int t = 0; t < q; t++) { int[] pm = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int p = pm[0], m = pm[1]; if (m < p) { Console.WriteLine("short"); } else { int left = m - p; int[] used = new int[4]; // 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for (int i = 3; i >= 0; i--) { used[i] = Math.Min(left / coins[i], stock[i]); left -= used[i] * coins[i]; } bool ok = left == 0; if (ok) { for (int i = 0; i < 4; i++) stock[i] -= used[i]; Console.WriteLine($"{used[3]} {used[2]} {used[1]} {used[0]}"); } else { Console.WriteLine("no change"); // 자판기 동전은 건드리지 않았다 } } } }}
C++main.cpp · 33 lines
#include <algorithm>#include <array>#include <iostream>int main() { const std::array<int, 4> coins = {10, 50, 100, 500}; std::array<int, 4> stock; for (int& s : stock) std::cin >> s; int q; std::cin >> q; for (int t = 0; t < q; t++) { int p, m; std::cin >> p >> m; if (m < p) { std::cout << "short\n"; } else { int left = m - p; std::array<int, 4> used{}; // 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for (int i = 3; i >= 0; i--) { used[i] = std::min(left / coins[i], stock[i]); left -= used[i] * coins[i]; } bool ok = left == 0; if (ok) { for (int i = 0; i < 4; i++) stock[i] -= used[i]; std::cout << used[3] << ' ' << used[2] << ' ' << used[1] << ' ' << used[0] << '\n'; } else { std::cout << "no change\n"; // 자판기 동전은 건드리지 않았다 } } }}
Cmain.c · 34 lines
#include <stdbool.h>#include <stdio.h>int main(void) { const int coins[4] = {10, 50, 100, 500}; int stock[4]; for (int i = 0; i < 4; i++) scanf("%d", &stock[i]); int q; scanf("%d", &q); for (int t = 0; t < q; t++) { int p, m; scanf("%d %d", &p, &m); if (m < p) { puts("short"); } else { int left = m - p; int used[4] = {0}; // 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for (int i = 3; i >= 0; i--) { int can = left / coins[i]; used[i] = can < stock[i] ? can : stock[i]; left -= used[i] * coins[i]; } bool ok = left == 0; if (ok) { for (int i = 0; i < 4; i++) stock[i] -= used[i]; printf("%d %d %d %d\n", used[3], used[2], used[1], used[0]); } else { puts("no change"); // 자판기 동전은 건드리지 않았다 } } } return 0;}
Craykonmain.cray · 37 lines
COINS = [10, 50, 100, 500];stock = Console.ReadNumbers();q = Console.ReadLine().ToNumber();for (t = 0; t < q; t++){ pm = Console.ReadNumbers(); p = pm[0]; m = pm[1]; if (m < p) { Console.WriteLine("short"); } else { left = m - p; used = [0, 0, 0, 0]; // 큰 동전부터: 자리 3(500원)에서 0(10원)으로 거꾸로 for (i = 3; i >= 0; i--) { used[i] = Mathf.Min(Mathf.Quot(left, COINS[i]), stock[i]); left -= used[i] * COINS[i]; } ok = left == 0; if (ok) { for (i = 0; i < 4; i++) { stock[i] -= used[i]; } Console.WriteLine([used[3], used[2], used[1], used[0]]); } else { Console.WriteLine("no change"); // 자판기 동전은 건드리지 않았다 } }}