7
\$\begingroup\$

Dina loves most numbers. In fact, she loves every number that is not a multiple of n (she really hates the number n). For her friends’ birthdays this year, Dina has decided to draw each of them a sequence of n−1 flowers. Each of the flowers will contain between 1 and n−1 flower petals (inclusive). Because of her hatred of multiples of n, the total number of petals in any non-empty contiguous subsequence of flowers cannot be a multiple of n. For example, if n=5, then the top two paintings are valid, while the bottom painting is not valid since the second, third and fourth flowers have a total of 10 petals. (The top two images are Sample Input 3 and 4.)enter image description here

Dina wants her paintings to be unique, so no two paintings will have the same sequence of flowers. To keep track of this, Dina recorded each painting as a sequence of n−1 numbers specifying the number of petals in each flower from left to right. She has written down all valid sequences of length n−1 in lexicographical order. A sequence a1,a2,…,a(n−1) is lexicographically smaller than b1,b2,…,bn−1 if there exists an index k such that ai=bi for i < k and ak < bk.

What is the kth sequence on Dina’s list?

Input The input consists of a single line containing two integers n (2≤n≤1000), which is Dina’s hated number, and k (1≤k≤1018), which is the index of the valid sequence in question if all valid sequences were ordered lexicographically. It is guaranteed that there exist at least k valid sequences for this value of n.

Output Display the kth sequence on Dina’s list.

Sample Input 1
4 3    
Sample Output 1
2 1 2

Sample Input 2
2 1    
Sample Output 2
1

Sample Input 3
5 22   
Sample Output 3
4 3 4 2

Sample Input 4
5 16  
Sample Output 4
3 3 3 3
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG. Nice first question. \$\endgroup\$ – ElPedro Nov 10 '18 at 12:21
  • \$\begingroup\$ Did you write this question or is it from another source? \$\endgroup\$ – Peter Taylor Nov 10 '18 at 17:23
1
\$\begingroup\$

Haskell, 87 bytes

n#k=[d|d<-mapM id$[1..n]<$[2..n],all(\x->mod x n>0)$p d]!!k
p(x:y)=scanl(+)x<>p$y
p x=x

Uses 0-based indexing. Needs the latest version of Prelude which is not installed on TIO, hence an additional import.

Try it online!

   d|d<-mapM id$[1..n]<$[2..n]    -- keep all 'd' from the lists of numbers [1..n] of
                                  -- length n-1
     , all(\x->      )            -- where all elements 'x' from
                       p d        -- the sums of the subsequences of 'd'
               mod x n>0          -- are not a multiple of n
 [                           ]!!k -- pick the 'k'th element

p(x:y)=scanl(+)x<>p$y             -- the sums of subsequences are calculated by
                                  -- prepending the cumulative sums of the list to
                                  -- a recursive call with the tail of the list
p x=x                             -- base case for recursion: empty list
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Jelly, 12 bytes

’ṗ`Ẇ§%ẠʋƇ⁸ị@

A dyadic Link accepting n on the left and k on the right.

Try it online! (no way this will work for large n, but would in theory)

How?

’ṗ`Ẇ§%ẠʋƇ⁸ị@ - Link: integer n, integer k
’            - decrement n -> n-1
  `          - use for both arguments of:
 ṗ           -   Cartesian power (all (n-1)^2 flower sequences - lex order)
         ⁸   - chain's left argument, n (as right argument for...)
        Ƈ    - filter keep those (sequences) which are truthy under:
       ʋ     -   last four links as a dyad (f(sequence, n)):
   Ẇ         -     all ((n-1)n/2) contiguous sublists (of the sequence)
    §        -     sum each
     %       -     modulo (n)
      Ạ      -     all? (all non-zero?)
           @ - with swapped arguments (i.e. f(k, listOfValidSequences)
          ị  -   index into (1-based)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 74 68 bytes

{([X] (1..^$^a)xx$a-1).grep(!*[^*X.. ^*].grep:{$_&.sum%%$a})[$^b-1]}

Try it online!

Anonymous code block that returns a list of numbers, or an integer in the case of \$n=2\$.

Explanation:

{([X] (1..^$^a)xx$a-1).grep(!*[^*X.. ^*].grep:{$_&.sum%%$a})[$^b-1]}
{                                                                  }  # Anonymous code block
 ([X] (1..^$^a)xx$a-1)  # From all n length sequences of 1 to n-1
                      .grep(                               )   # Filter by
                            !           .grep:{          }  # None of
                             *[^*X.. ^*]    # All partitions (including empty lists)
                                               $_    # Are non-empty
                                                 &.sum%%$a  # And the sum is divisible by n
                                                            [$^b-1]  # Get the kth index of the list
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 35 bytes

NθI↨§Φ…Xθ⁻θ²Xθ⊖θ¬ΦθΦλ¬﹪Σ✂↨ιθνλ¹θ⊖ηθ

Try it online! Link is to verbose version of code. Works by taking the range \$ n^{n-2} \ldots n^{n-1}-1 \$ in base \$ n \$ and filtering out illegal sequences (including ones with zero digits). Explanation:

N                                   Input `n` as a number
 θ                                  Save in variable
        θ                           `n`
       X                            To the power
          θ                         `n`
         ⁻                          Minus
           ²                        2
      …                             Ranged up to
             θ                      `n`
            X                       To the power
               θ                    `n`
              ⊖                     Decremented
     Φ                              Filtered `i` by
                ¬                   Not
                  θ                 Implicit range `0` .. `n-1`
                 Φ                  Filtered `l` by
                    λ               Implicit range `0` .. `l`
                   Φ                Filtered `m` by
                     ¬              Not
                       Σ            Sum
                          ι         `i`
                         ↨          Converted to base
                           θ        `q`
                        ✂           Sliced
                            ν       From `m`
                             λ      To `l`
                              ¹     Step 1
                      ﹪             Modulo
                               θ    `n`
    §                               Indexed by
                                 η  Second input `k`
                                ⊖   Decremented
   ↨                                Converted to base
                                  θ `n`
  I                                 Cast to string
                                    Implicitly printed
| improve this answer | |
\$\endgroup\$

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.