2

I had this test in my neuroscience laboratory, and we had all sort of brain tissue spread in front of us. Each one had multiple needles attached to it with numbers on them (marking places I needed to answer how they are called). So apparently the lab only had certain needles with certain numbers, and they tried really hard that every tissue will have consecutive numbers on them, but failed really hard...

My question is as follow: You get $N$ needles with numbers on them (an array sized $N$ of ints). The needles are given to you in an unordered way (they come in a box). You get $Q$ pieces of brain tissue and each of them needs a certain number of needles on them (an array sized $Q$ of ints).

Question number 1: What is the maximum number of brain tissue you can fill with needles with all consecutive numbers. (2,3,4,5 in a brain tissue with 4 needles needed).

Question number 2: What is the maximum number of consecutive numbers you can get ( 2,3,5,6 in a brain tissue with 4 needles needed is 2 consecutive numbers — 3, 6).

Epiousios
  • 3,194
Ido Kessler
  • 131
  • I do not understand. What makes using consecutive numbers hard here? Can you give an example, maybe a tricky one? – M. Winter Sep 19 '17 at 14:04
  • lets say you have this pack of needles with numbers: 1x2 2x1 3x2 4x2

    and you have two brains, one that requires 2 consecutive numbers and one that requires 3.

    I have a 0 mistakes solution here: 1: 3,4 2: 1,2,3

    but I can mess this up if I don't take in the first one 3,4. (because the brain that requires three needle has to take the needle with the 2).

     – Ido Kessler Sep 19 '17 at 17:35
  • Ok. I understand. Now, the answer to e.g. Question 1 highly depends on the amount and the exact numbering of the needles. I can imagine that someone might give an algorithm (brute force?), but I do no think there is a closed formula. Or do you mean that the $N$ needles are numbered with all consecutive numbers, e.g. $1,2,3,...,N$? Then the answer $\lfloor N/4\rfloor$. – M. Winter Sep 20 '17 at 07:56

0 Answers0