I'll just put the question statement here,

You work as a pizza deliveryman, and one of your deliveries was late by 45 minutes. Of course, the client was not happy. And unfortunately for you, this guy is the Don of the Mafia. You find yourself surrounded by many Italian guys in suits, all ready to end your life with a word from the Don.

He decides to spare you if you "donate" all of your savings to his men. However there's a condition: You must divide all of your money between all of his men. Each person can (but not necessarily) recieve the same amount of money, but each person absolutely must recieve the same number of bills.

The Mafia escorts you to the nearest ATM. This ATM allows you to choose the denomination of each note you withdraw, however the only options are 1 and 2 dollar bills. Determine the minimum number of notes you can withdraw so that the Don's condition is satisfied (good ending). If there is no possible way to do so, print -1 (bad ending)

Input Format

The single line contains two space separated integers n, m, where n is the amount of money in your account, and m is the number of men amongst which you must divide the money

Constraints

0 < n ≤ 10000 1 < m ≤ 10

Output Format

Print a single integer — the minimal number of notes such that the condition is satisfied If there is no such number satisfying the condition, print -1

I've tried so many times to solve this problem but just can't get the logic as to how to approach it,If you guys could help it would mean a lot.

I''ve wrote so many test cases in python but none of them worked,and i'm also not able to view which of my test cases are going wrong,Please help.... Thank you.

CodePudding user response：

Here's a hint. Let's say there are N men and K dollars in your account. You can divide K into a mix of 1 dollar bills and 2 dollar bills. Let's calls these counts Ones and Twos. Such that

K = Ones   2*Twos

To satisfy the requirement that all men receive the same number of bills, but not necessarily the same value of bills, we can use the modulo operator to validate there are no remaining bills when we given each man an equal number of bills:

Or more simply:

(Ones   Twos) % N == 0

Brute force solution is to start with 2 dollar bills and stop when the above equation is satisfied

Twos = K // 2
Ones = K % 2  # either 0 or 1 depending if K is even or odd

For example, if you had K = 101. Then you start with 50 "twos" and a single "one" dollar bill set.

And then your loop is basically evaluating if (Ones Twos) % N == 0. If this equation is satisfied, you are done. If not, deduct 1 from Twos and add 2 to Ones. (e.g. 49 "twos" and 3 "ones" in the next iteration) Stop when you...

CodePudding user response：

// node.js app to solve the mafia dollar-bill-distribution puzzle on stackoverflow

const argv = require('yargs/yargs')(process.argv.slice(2)).argv;
const argc = argv.size;

if (!argv.money || !argv.men) {
    console.log('Not enough parameters specified. Try --money=M and --men=N where 0 < N < 11 and 0 < M < 10001');
    process.exit(-1);
}
console.log('Money: '   argv.money);
console.log('Men: '   argv.men);

try {
    if (argv.men > 10 && argv.men < 1) {
        console.log('Invalid number of --men specified!');
        console.log('-1');
        process.exit(-1);
    }
    if (argv.money > 10000 && argv.money < 0) {
        console.log('Invalid amount of --money specified!');
        console.log('-1');
        process.exit(-1);
    }
} catch (err) {
    console.error(err);
    console.log('Could not process the command line arguments. --men= and --money= must both be integers!');
}

let men = argv.men;
let money = argv.money;

// First get rid of two easy outcomes
// 1. There is not enough cash to give them even one dollar each
if (money < men) {
    console.log('Not enough money to divide between them equally!');
    console.log('-1');
    process.exit(-1);
}
// 2. They get one dollar bill each! (this could be expanded checking for money / 2 == men, for one two dollar bill each
if (money == men) {
    console.log('Each man gets one dollar bill each. Simples!');
    process.exit(0);
}

// Otherwise, its on with the show!
function distribute(ones, twos, men) {
    console.log('Trying '   ones   ' ones and '   twos   ' twos.');
    console.log( ((twos   ones) % men) );
    var distributed = ((twos   ones) % men) === 0;
    if (distributed) {
        console.log('Withdraw '   twos   ' two dollar bills and '   ones   ' one dollar bills.');
        console.log('Each man gets '   ((ones   twos) / men)   ' bills each.');
        process.exit(0);
    }
    return distributed;    
}

// Can we distribute this evenly?
let twos = Math.floor(money / 2);
let ones = money % 2;
console.log('Starting with '   twos   ' two dollar bills and '   ones   ' one dollar bills...');

while (!distribute(ones, twos, men)) {
    twos-=twos;
    ones =2;

    if(twos <= 0) {
        break;
    }
}

// We get here, we failed...
console.log('Dead man... -1');
process.exit(-1);