-2
$\begingroup$

There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is difficult for me to think through. Can someone suggest an algorithm? Similar questions exist on this site, but I could not find an answer that solves this problem, though it is possible that I overlooked something.

EDIT:

The sticks are all homogeneous, the same in every respect. What I mean by "as evenly as possible" is that if there are 6 sticks and 3 boys, the division algorithm should output 2-2-2. If there are 5 sticks among 3 boys, it should output 1-2-2. The disparity between the minimum stick holder and maximum stick holder should be no greater than 1. Ordering does not matter (e.g. 1-2-2 is the same as 2-1-2).

$\endgroup$
  • $\begingroup$ What do you mean by "as equally as possible"? Are the sticks of different lengths/weights? Do you have a link to this problem somewhere? This description seems filled with ambiguity. $\endgroup$ – ryan May 9 '17 at 21:18
  • $\begingroup$ @ryan clarified above. $\endgroup$ – user_1_1_1 May 9 '17 at 21:46
  • $\begingroup$ You tag "optimization", but what do you want to optimize? Giving everybody nothing it perfectly equal. See here for a more interesting variant. $\endgroup$ – Raphael May 9 '17 at 22:57
  • $\begingroup$ OK, strictly speaking, essentially everything is an algorithm. But you just need to do division, here. $\endgroup$ – David Richerby May 10 '17 at 19:28
3
$\begingroup$

Give some of the boys $\lfloor N/M \rfloor$ sticks (i.e., divide and round down), and some of them $\lceil N/M \rceil$ sticks (divide and round up). Once you fix those two numbers, that uniquely determines how many boys get $\lfloor N/M \rfloor$ sticks and how many get $\lceil N/M \rceil$ sticks -- do some simple arithmetic, try a few examples, use the fact that $\lceil N/M \rceil = \lfloor N/M \rfloor + 1$ if $M$ doesn't evenly divide into $N$, and you'll work out the general formula.

$\endgroup$
0
$\begingroup$

Give them $\lfloor\frac{N}{M}\rfloor$ sticks and then distribute the rest of sticks ($N-\lfloor\frac{N}{M}\rfloor$) among them by giving one stick to each boy until there are no more sticks. By solving it this way, the time complexity will be $\max(\lfloor\frac{N}{M}\rfloor, N \bmod M)$ .

$\endgroup$
  • $\begingroup$ What do you mean by "$[N/M]$"? That's not a notation I've seen before. $\endgroup$ – David Richerby May 10 '17 at 21:30
  • $\begingroup$ It means the integer part of [N/M] $\endgroup$ – Sardor Gulyamov May 14 '17 at 12:17
  • $\begingroup$ Oh, and I have made a mistake about time complexity $\endgroup$ – Sardor Gulyamov May 14 '17 at 12:17
  • $\begingroup$ OK. That's usually written $\lfloor N/M\rfloor$ (\lfloor ... \rfloor in LaTeX). $\endgroup$ – David Richerby May 14 '17 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.