Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2187
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2187
Bits Exchanged
Por OBI - Olimpíada Brasileira de Informática 2000 
Brazil
Timelimit: 1
The Weblads islands form an independent kingdom in the Pacific seas. How is a new kingdom, the society is greatly influenced by computer. The official currency is the Bit; there are notes of B$50,00 B$10,00 B$5,00 to B$1,00. You have been hired to assist in the programming of the ATMs of a large bank of Weblands Islands.
The ATMs of Weblands Islands operate with all types of available notes, keeping a stock of ballots for each value (B$50,00 B$10,00 B$5,00 to B$1,00). Bank customers use ATMs to make withdrawals from a certain integer bits.
Your task is to write a program that, given the Bit value desired by the client, determine the number of each of the notes required for this total value to minimize the amount of delivered bills. For example, if the customer wishes to withdraw B$50,00, simply deliver a fifty-one Bits. If the client wishes to withdraw B$72,00, it is necessary to deliver a note of B$50,00 B$10,00 two, and two B$1,00.
Input
The input is composed by multiple test sets. Each test set is composed by a single line, that contains a positive integer numberV (0 ≤ V ≤ 10000), that indicates the solicited number by the costumer. The end of the input is indicated by V = 0.
Output
For each test set of the input your program must produce three lines in the output. The first line must contain a test set identifier, in the format “Teste n”, where n it is numbered from 1. In the second line must appear 4 integer I, J, K e L that represent the result found by your program: I indicates the number of ballots B$50,00, J indicates the number of ballots B$10,00, K indicates the number of ballots B$5,00 e L indicates the number of ballots B$1,00. The third line must be left in blank. The spelling shown in Output Example, below, should be followed strictly.
| Input Sample | Output Sample |
|
1 72 0 |
Teste 1 0 0 0 1 Teste 2 1 2 0 2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdbool.h>
int main (void)
{
short bit, aux;
unsigned short qtsBits50, qtsBits10, qtsBits5, qtsBits1;
unsigned short qtsTestes = 0;
while (true)
{
scanf("%hu", &bit);
if (!bit)
break;
qtsBits50 = qtsBits10 = qtsBits5 = qtsBits1 = 0;
qtsBits50 = bit / 50;
bit = bit % 50;
qtsBits10 = bit / 10;
bit = bit % 10;
qtsBits5 = bit / 5;
bit = bit % 5;
qtsBits1 = bit;
printf("Teste %hu\n", ++qtsTestes);
printf("%hu %hu %hu %hu\n\n", qtsBits50, qtsBits10, qtsBits5, qtsBits1);
}
}
Input
72
0
Output
0 0 0 1
Teste 2
1 2 0 2
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
int main() {
int n, teste = 1;
while (scanf("%d", &n) && n) {
printf("Teste %d\n", teste++);
printf("%d ", n / 50);
n %= 50;
printf("%d ", n / 10);
n %= 10;
printf("%d ", n / 5);
n %= 5;
printf("%d\n\n", n);
}
return 0;
}
Input
72
0
Output
0 0 0 1
Teste 2
1 2 0 2
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("fs")
const lines = readFileSync("/dev/stdin", "utf8")
.split("\n")
.map((line) => Number.parseInt(line, 10))
const BIT_NOTES = [50, 10, 5, 1]
function main() {
const responses = []
for (let i = 0; i < lines.length; i++) {
let sum = lines[i]
if (sum == 0) break
const notes = Array(BIT_NOTES.length).fill(0)
for (let j = 0; j < BIT_NOTES.length; j++) {
if (sum == 0) break
const bitNote = BIT_NOTES[j]
while (sum - bitNote >= 0) {
sum -= bitNote
notes[j] += 1
}
}
responses.push(
`Teste ${i + 1}`,
notes.join(" "),
""
)
}
console.log(responses.join("\n"))
}
main()
Input
72
0
Output
0 0 0 1
Teste 2
1 2 0 2