Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The Situation:

Several (M) dwarves have found a goblin's chest with N gold coins and have to divide them. Due to ancient rules governing the allocation of loot to pirates in order of seniority, the oldest dwarf should get one coin more than the next oldest dwarf, and so on, so that the youngest dwarf gets M-1 fewer coins than the oldest dwarf. Additionally, no dwarf has to pitch in any coins (ie no negative coins to any dwarfs)

Help the dwarves to divide the coins in this way, or tell them that this is impossible.

Winner's code must always answer correctly (this challenge is deterministic) and follow the general rules.

Input

You are given an integer N (3 ≤ N ≤ 1000) for number of coins and an integer M (3 ≤ M ≤ N) for number of dwarves, space-separated.

Output

If it is impossible to divide the coins in the way that dwarves want, print -1 (minus one). Otherwise, print the numbers of coins that each dwarf will receive, from oldest to youngest. Separate the numbers with spaces.

Samples:

input

3 3

output

2 1 0

input

9 3

output

4 3 2

input

7 3

output

-1

input

6 4

output

3 2 1 0
share|improve this question
3  
You missed a "pirate". –  Rawling Apr 4 at 9:30
6  
relevant –  Raystafarian Apr 4 at 14:20
3  
Good find, @Raystafarian. Perhaps when the teacher gets a general solver for M dwarves instead of just 3, s/he will recognize that the user crowdsourced the answer :) -- especially if that solver is in J. –  ProgrammerDan Apr 4 at 14:41
    
Homework or not, its a Smurfing good question! –  steveverrill Apr 5 at 5:40
add comment

18 Answers 18

J - 32 29 28 25

Not shorter than other J solution, but and uses a different idea

(]{.[:i:-:@-.@]-%)/ ::_1:

The answer for the number of coins the highest rank gnome is getting is simply N/M+(M-1)/2 (if it's an integer), we construct the negative of this -:@-.@]-%. Then i: makes an array like that 2 1 0 _1 _2 for argument _2 and we take M elements from it.

share|improve this answer
1  
+1 for a brilliant usage of i:. You can save another three char by writing % instead of [%], and by using -.@] instead of (1-]). –  algorithmshark Apr 4 at 16:34
    
@algorithmshark Thanks fellow J enthusiast! –  swish Apr 4 at 17:06
1  
Can't +1 as @swish seems to be with the gnomes we just robbed. ;) –  TheConstructor Apr 5 at 5:42
add comment

J - 30 char

Very fun to golf. A lot of things worked out neatly.

((+/@s~i.[){ ::_1:s=.+/&i.&-)/

Explanation:

  • / - Take the space-separated integers as argument, and slip the function between them. That is to say, consider N the left argument to the function in the brackets (...) and M the right argument.

  • i.&- - Negate (-) and then take integers (i.). Normally, when you do something like i.5 you get 0 1 2 3 4. Whenever i. receives a negative number, however, it reverses that output list. So e.g. i._5 will give 4 3 2 1 0.

  • s=.+/& - Perform the above action on each argument (&) and then make an addition table (+/) out of these arrays. We now have a table where each row is a possible coin distribution to M dwarves, though maybe not when there's N coins. Finally, this table-making verb is so useful we're going to call it s and use it again later.

  • +/@s~ - Now, we use s again, but we swap (~) the order of the arguments, so that we transpose the table. This is a golfy way of taking the sum of each row after creating the table (+/@), having to do with the way J sums multidimensional lists.

  • i.[ - In this list of sums, we search for the left argument to the verb, i.e. N. If N is an item, we get that index: else we get the length of the list, which notably is an invalid index.

  • { ::_1: - Now we try to use the index to pull out a row from table in s. { will throw a domain error if the index was invalid, so in that case we catch the error (::) and return -1 (_1:). This handles everything. Since we use i.&- previously, the coin distribution will be in descending order, as was required.

Usage:

   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 9 3
4 3 2
   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 7 3
_1
   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 6 4
3 2 1 0
   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 204 17
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
share|improve this answer
    
Input 9 3 should return 4 3 2, not -1. Seems there is a transposition in your example usage? –  ProgrammerDan Apr 3 at 18:59
    
@ProgrammerDan Thanks, didn't catch that. I typed up the examples wrong. 9 3 gives 4 3 2 and 7 3 gives _1, as expected. –  algorithmshark Apr 3 at 19:03
    
Saw the fix and +1'd appropriately :D. I should look into J, looks nifty. –  ProgrammerDan Apr 3 at 19:04
add comment

R - 71 70 67 66 65 chars

s=scan();m=s[2];x=s[1]-sum(1:m);cat(if(x%%m|-m>x)-1 else x/m+m:1)

Ungolfed:

s = scan()    # Reads N and M by stdin.
m = s[2]
x = s[1] - m*(m-1)/2
cat(if (x %% m | x < -m) -1 else x/m + m:1)

Solution:

If M the number of dwarfs, then the sequence of paid gold can be decomposed to two singular series. First a series ending in zero: M-1, ..., 2, 1, 0 and a constant series of c, c, ..., c. The sum of the first series is always M*(M-1)/2. So if the remainder (x = N - M*(M-1)/2) could be divided without remainder (modulo equal 0), each dwarf gets x/M plus the part of the decreasing series.

Usage:

> s=scan()
1: 10 4
3: 
Read 2 items
> m=s[2]
> x = s[1] - m*(m-1)/2
> cat(if (x %% m || x<0) -1 else x/m + (m-1):0)
4 3 2 1
share|improve this answer
    
-1, the question requires to write a complete program and not a function. See meta.codegolf.stackexchange.com/a/1146/8766 –  user80551 Apr 4 at 6:26
    
@user80551 You are right. Now I corrected the snippet: now it takes the space-separated input; the output also does not show anymore the '[1]'. –  lambruscoAcido Apr 4 at 7:12
1  
You can save another character replacing m*(m+1)/2 with sum(1:m) –  Brian Diggs Apr 4 at 20:18
    
@Brian Thx, I will modify my code! –  lambruscoAcido Apr 5 at 15:50
add comment

PHP (187)

It's my first attempt at golfing, and I know it could be better, but still :)

Golfed:

<?php
$b=fgets(STDIN);list($c,$d)=explode(' ',$b);if((($d&1)AND($c%$d==0))OR($c%$d==$d/2)){for($e=floor($c/$d)+floor($d/2);$e>floor($c/$d)-round($d/2);$e--){echo"$e ";}}else{die('-1');}?>

Ungolfed:

<?php
$a = fgets(STDIN);
list($coins, $dwarves) = explode(' ', $a);
if ((($dwarves & 1) AND ($coins % $dwarves == 0)) OR ($coins % $dwarves == $dwarves / 2)) {
    for (
        $i = floor($coins / $dwarves) + floor($dwarves / 2);
        $i > floor($coins / $dwarves) - round($dwarves / 2);
        $i--
    ) {
        echo "$i ";
    }
}
else { 
  die('-1');
}
?>

Execute in a shell

Basic idea:

Coins can be separated by these rules, if one of these is true:

  1. The dwarves are odd number, and the coins are divisible by the dwarves with no remains
  2. The dwarves are even number, and the coins remaining after dividing coins / dwarves is equal to half of the dwarves number

If so, we take for base the average coins per dwarf (ACPD). But we have to start from the highest and output until we reach the lowest. So we make a loop with counter starting from ACPD + the count of the rest of the dwarves towards the higher end, and go on until we reach the ACPD - the count of the rest of the dwarves towards the lower end.

It's basically the same if the dwarves are odd (i.e. 5 dwarves - the middle one is 3, and in both ends there remain 2), but not if they are even - which is why we rely on floor AND round.

Problems so far: Works with too low coins number, which means some dwarves will be smacked down and robbed of their precious earnings. And this is sad. Or at least if you like dwarves.

Solution:

  1. Think of a way to calculate the lowest amount of coins so the calculation doesn't end up with dwarves in the dust.
  2. Design not-so-greedy dwarves.

Smarter solution:

Coins are metal. Make the dwarves melt them all, and then cast them in smaller/larger amount of coins, so they are divisible in any case.

Smartest solution:

Steal their mountain, rename yourself to Smaug and keep it all for yourself. After all, why do you have to bother with grumpy dwarves?

share|improve this answer
add comment

Python 3 (100)

Using the same idea as @Geobits but conforming to the input and output requirements.

n,m=map(int,input().split())
κ,ρ=divmod(n-m*(m-1)//2,m)
x=[-1]if ρ else range(κ,κ+m)[::-1]
print(*x)
share|improve this answer
    
Thanks for the heads-up. Didn't notice the space-separation added to the input reqs. –  Geobits Apr 3 at 22:46
add comment

Python 3 - 109 107 103 102 90 94

Using the same idea as Evpok, but with a number of improvements.

n,m=map(int,input().split())
k=n/m+m/2
a=int(k)
print(*(range(a,a-m,-1),[-1])[k-a-.5or~a>-m])

The improvements are:

  1. Eliminating the space after else and before ' '. 1 character
  2. Eliminating the ' ' inside split(), because splitting on spaces is a default. 3 characters
  3. Lowering x by 1 changing the -1 to +1 inside divmod, and then changing the range function to use the range's reversed order option. 3 characters.
  4. EDIT: ... if ... else ... changed to ... and ... or ... 2 characters.
  5. EDIT: Divmod made explicit, r removed. 4 characters.
  6. EDIT: x removed, m//n used explicitly. 1 character
  7. EDIT: used starred expressions instead of ' '.join(map(str,...)), added x to avoid repeating print(). 12 characters.
  8. EDIT: I realized that I was allowing negative numbers of coins to be given to the Dwarves. I changed the code to avoid this.
share|improve this answer
    
Well done, it was instructive :) I changed my answer to strip the unnecessary space, but your trick to save the [::-1] is better than my solution. +1 –  Evpok Apr 4 at 8:24
add comment

Python 3 - 114

n,m=map(int,input().split(' '))
r=range(m);n-=sum(r)
if n%m<1:
 for x in r:print(m-x+n//m-1,end=' ')
else:print -1

Works by checking if N-(M*(M-1)/2) is evenly divisible by M. New to python, so any tips appreciated.

Ideone.com example

Input:
735 30
Output:
39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
share|improve this answer
add comment

C# - 322

using System;using System.Linq;namespace D{class P{static void Main(string[]args){int n=Convert.ToInt16(args[0]);int m=Convert.ToInt16(args[1]);bool b=false;int q=n/2+1;g:b=!b;int[]z=new int[m];for(int i=0;i<m;i++){z[i]=q-i;}if(z.Sum()==n)foreach(int p in z)Console.Write(p+" ");else{q--;if(b)goto g;Console.Write(-1);}}}}

Horrible score but I took a different approach and got to use goto :)

I will shorten it later.

share|improve this answer
    
You can definitely shorten all of those Convert.ToInt16 calls to just int.Parse. You can declare any pre-assigned variable with var (instead of e.g. int[]). Your command-line params don't need to be called args. And you can alias frequently-used types like using C = Console. I also think that for a solution this long, it's better to present with line spacing intact rather than saving just a couple of characters. Oh, and I'm not really sure why goto is better than alternatives here, either... –  Aaronaught Apr 5 at 13:34
add comment

R: 77 73 chars

a=scan();r=a[2]:1-1;while(sum(r)<a[1])r=r+1;cat(if(sum(r)>a[1])-1 else r)

Create a vector going from (M-1) to 0 and adds 1 to each number until the sum is no longer inferior to N. If it is superior, output -1 else output the vector.

Indented:

a=scan()   #Reads in stdin (by default numeric, space-separated)
r=a[2]:1-1 #Creates vector (M-1) to 0
while(sum(r)<a[1])r=r+1 #Increments all member of vector by 1 until sum is not inferior to N
cat( #Outputs to stdout
    if(sum(r)>a[1]){ #If superior to N: impossible, returns -1
        -1
    }else{
        r
    })

Example usage:

> a=scan();r=a[2]:1-1;while(sum(r)<a[1])r=r+1;cat(if(sum(r)>a[1])-1 else r)
1: 9 3
3: 
Read 2 items
4 3 2
> a=scan();r=a[2]:1-1;while(sum(r)<a[1])r=r+1;cat(if(sum(r)>a[1])-1 else r)
1: 7 3
3: 
Read 2 items
-1
> a=scan();r=a[2]:1-1;while(sum(r)<a[1])r=r+1;cat(if(sum(r)>a[1])-1 else r)
1: 204 17
3: 
Read 2 items
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
share|improve this answer
add comment

Java 210

class A { public static void main(String[] a){int d=Integer.parseInt(a[0]),c=Integer.parseInt(a[1]);if (2*c%d==0) for (int i=0;i<d;i++) System.out.print((((1+(2*c/d)-d)/2)+i)+" "); else System.out.print(-1);}}
share|improve this answer
2  
Welcome to PPCG, I see you have a lot of whitespace which can be removed. –  ace Apr 4 at 14:21
    
You can strip out a lot more spaces to golf your answer a bit further -- for instance, class A{public static void main(String[]a) is valid, and saves you 3 characters. After each if, and around each for, remove the whitespace ... etc. –  ProgrammerDan Apr 4 at 14:21
    
It's crazy that the "public static void main(S" part is as long as that entire J solution :) –  Robert Grant Apr 30 at 14:12
add comment

Julia, 45

f(n,m)=(x=n/m-m/2+1/2;x%1==0?[x+m-1:-1:x]:-1)
julia> f(6,4)'
1x4 Array{Float64,2}:
 3.0  2.0  1.0  0.0

Just a bit of algebra, took me way longer than it should have.

share|improve this answer
add comment

JavaScript - 76

Observe that k + (k - 1) + ... + (k - (M - 1)) = M(k - (M - 1)/2) Setting this equal to N gives k = N/M + (M-1)/2 for the highest amount. If this is integer, then k % 1 == 0 and the amounts we are looking for are k, k - 1, ..., k - (M - 1).

I could probably have written this shorter in another language, but there was no JS solution yet so here it is:

N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Run in the console.

Example input:

N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Output:

3
2
1 

Input:

N=6;M=4;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Output:

3
2
1
0

Input:

N=7;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

Output: -1

Too bad console.log is so long to spell :) Unfortunately declaring l=console.log.bind(console) does not make it any shorter, and just l=console.log does not work.

Input:

"N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)".length

Output:

76
share|improve this answer
    
You can use c=console and c.log() to shorten it. –  user2428118 Apr 5 at 23:39
add comment

Golfscript, 35

~:M.(*2/-.M%{;-1}{M/M+,-1%M<' '*}if

How it works

In the following example, the input is 9 3.

          # STACK: "9 3"
~         # Interpret the input string.
          # STACK: 9 3
:M        # Store the top of the stack (number of dwarves) in variable `M'.
.         # Duplicate the top of the stack.
          # STACK: 9 3 3
(         # Decrement the top of the stack.
          # STACK: 9 3 2
*         # Multiply the topmost elements of the stack.
          # STACK: 9 6
2/        # Divide the top of the stack by `2'.
          # STACK: 9 3
          # So far, we've transformed `M' into `M*(M-1)/2', which is the minimum amount of
          # coins all dwarves together will get. This number comes from the fact that the
          # youngest dwarf will get at least 0 coins, the next at least 1 coin, etc., and
          # 0 + 1 + ... + (M - 1) = M*(M-1)/2.
-         # Subtract the topmost elements of the stack.
          # STACK: 6
          # The remaining coins have to get reparted evenly to all dwarves.
.         # Duplicate the top of the stack.
          # STACK: 6 6
M%        # Calculate the top of the stack modulus `M'.
          # STACK: 6 0
{         # If the modulus is positive, the remaining coins cannot get reparted evenly.
    ;-1   # Replace the top of the stack by `-1'.
}
{         # If the modulus is zero, the remaining coins can get reparted evenly.
    M/    # Divide the top of the stack by `M'.
          # STACK: 2
          # This is the number of coins all dwarves will get after giving 1 to the second
          # youngest, etc.
    M+    # Add `M' to the top of the stack.
          # STACK: 5
    ,     # Replace the top of the stack by an array of that many elements.
          # STACK: [ 0 1 2 3 4 ]
          # The rightmost element is the number of coins the oldest dwarf will get.
    -1%   # Reverse the array.
          # STACK: [ 4 3 2 1 0 ]
    M<    # Keep the leftmost `M' elements.
          # STACK: [ 4 3 2 ]
          # There are only `M' dwarves.
    ' '*  # Join the array, separating by spaces.
          # STACK: "4 3 2"
}if
share|improve this answer
add comment

Delphi XE3 (176)

uses SysUtils;var d,c,i:integer;begin read(c,d);for I:=1to d-1do c:=c-i;if c mod d>0then writeln(-1)else begin c:=c div d;for I:=d-1downto 0do write(IntToStr(i+c)+' ');end;end.

How it works.

Reads 2 integers, coins and dwarves.
Substracts the difference per dwarf.
If the remainder mod dwarves>0 its impossible.
Else get equal share per dwarf in a loop of dwarves-1 to 0 and prints dwarfIndex+equal share

Ungolfed

uses SysUtils;
var
  d,c,i:integer;
begin
  read(c,d);
  for I:=1to d-1do
    c:=c-i;
  if c mod d>0then
    writeln(-1)
  else
  begin
    c:=c div d;
    for I:=d-1downto 0do
      write(IntToStr(i+c)+' ');
  end;
end.
share|improve this answer
add comment

Mathematica 65

The function, g, generates all the increasing-by-one sequences, of length m, from 0 to n and checks whether any of them sum to m. If successful, the sequence is returned; otherwise, -1 is returned.

The sequences are made by Partitioning the list {0,1,2,3… m} into all possible sublists of n contiguous integers.

There are, of course, more efficient ways to achieve the same effect, but those that I have found require more code.

n_~g~m_:=If[(s=Select[Partition[0~Range~n,m,1],Tr@#==n&])=={},-1,s]

Examples

g[9, 3]

{{2, 3, 4}}


g[3, 3]

{{0, 1, 2}}


g[7, 3]

-1


g[705, 3]

{{234, 235, 236}}


g[840, 16]

{{45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60}}


g[839, 16]

-1

share|improve this answer
add comment

C 131

#include <edk.h>
main(int a,char **v){int j=atoi(*++v),k=atoi(*++v)-j*(j-1)/2;k<0||k%j?j=1,k=-1:k/=j;while(j--)printf("%d ",k+j);}

Ungolfed

#include <edk.h> //Shortest standard header including stdio.h and stdlib.h
main(int a,char **v)
{
    int j=atoi(*++v),k=atoi(*++v)-j*(j-1)/2;

    k<0||k%j?j=1,k=-1:k/=j;  // If youngest dwarf gets < 0 or amount not equally divisible then set values such that ...

    while(j--)printf("%d ",k+j); // ... loop prints out correct values
}

This compiles with a warning because main has no type. If this is not valid in the rules of golf, I would have to add five characters.

share|improve this answer
add comment

Cobra - 198

Cobra Website

class P
    def main
        x,y=Console.readLine.split
        a,b=x to int,y to int
        l=[]
        t=n=0
        for i in b,t+=i
        while (t+=b)<=a,n+=1
        for i in b,l.insert(0,i+n)
        print if(t-b<>a,-1,l.join(" "))

Explained:

class P
    def main

Required for the code to run

        x,y=Console.readLine.split
        a,b=x to int,y to int

Takes input and stores it as a and b

        l=[]
        t=n=0

Initializes the output list l, and initializes the total required money t and number of coins to add to each dwarves pile n

        for i in b,t+=i

Finds the lowest possible money value that will result in all dwarves having an allowable number of coins in their pile

        while (t+=b)<=a,n+=1

Determines how many coins to add to each pile so that the total required money is >= to the total available money

        for i in b,l.insert(0,i+n)

Fills the list with the different sized piles of money

        print if(t-b<>a,-1,l.join(" "))

Outputs either -1 or l depending whether the total required money is equal to the total available money

share|improve this answer
add comment

Python (100 96 94):

A nice, round-scoring answer. Not any more, but it IS shorter now.

def f(n,m):a=range(m)[::-1];b=n-sum(a);c=b/m;d=[i+c for i in a];return(d,-1)[-1in d or c*m!=b]

Ungolfed:

def f(n,m):
 a = range(m)[::-1]
 b = sum(a)
 c = (n-b)/m
 if c * m != n-b: return -1
 d = [i+c for i in a]
 return (d,-1)[-1 in d or c!=n-b]
 if -d in d or c*m!=n-b:
  return -1
 return d

Output:

def f(n,m):a=range(m)[::-1];b=sum(a);c=(n-b)/m;d=[i+c for i in a];return (d,-1)[-1 in d or c*m!=n-b]

f(3,3)
Out[2]: [2, 1, 0]

f(9,3)
Out[3]: [4, 3, 2]

f(7,3)
Out[4]: -1

f(6,4)
Out[5]: [3, 2, 1, 0]
share|improve this answer
2  
This doesn't follow the input requirement. –  Austin Henley Apr 3 at 22:52
    
-1, the question requires to write a complete program and not a function. See meta.codegolf.stackexchange.com/a/1146/8766 –  user80551 Apr 4 at 6:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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