Конденсаторы известны тем, что изготавливаются с высокими допусками. Это приемлемо во многих случаях, но иногда требуется емкость с жесткими допусками. Обычной стратегией для получения емкости с точным требуемым значением является параллельное использование двух тщательно измеренных конденсаторов, чтобы их емкость достигала необходимого диапазона.

Цель в этой задаче состоит в том, чтобы, учитывая (несколько) набор емкостей, соединить конденсаторы так, чтобы общая емкость каждой пары находилась в заданном диапазоне. Вам также нужно найти наилучший набор пар, то есть набор пар, чтобы было найдено как можно больше пар.

Ограничения

1. Вход содержит в формате выбора
   • неупорядоченный список емкостей, представляющих (несколько) набор конденсаторов у вас есть
   • пара мощностей, представляющих нижнюю и верхнюю границы целевого диапазона (включительно)
2. все емкости на входе являются положительными целыми числами, меньшими чем 2 ³⁰ , единица измерения - pF (не это имеет значение).
3. В дополнение к списку емкостей на входе, набор конденсаторов также содержит бесконечное количество конденсаторов со значением 0 пФ.
4. Выходные данные содержат в выбранном формате список пар мощностей, так что сумма каждой пары находится в указанном целевом диапазоне . Не указан ни порядок пар, ни порядок мощностей в паре.
5. Емкость на выходе не может появляться чаще, чем в наборе конденсаторов . Другими словами: пары, которые вы выводите, не должны перекрываться.
6. Не должно быть возможных выходных данных, удовлетворяющих условиям 4 и 5, которые содержат больше пар мощностей, чем выходные данные, создаваемые вашей программой.
7. Ваша программа должна завершиться через O ( n !), Где n - длина списка, представляющего набор конденсаторов, который у вас есть
8. Лазейки не должны быть использованы
9. Целевой диапазон не должен быть пустым

счет

Ваша оценка - это длина вашего решения в октетах. Если вашему решению удается решить эту проблему за полиномиальное время O ( n ^k ) для некоторого k , разделите ваш счет на 10. Я не знаю, возможно ли это на самом деле.

Пример ввода

• диапазон от 100 до 100, входной массив 100 100 100, допустимый вывод:

  0 100
  0 100
  0 100
  

• диапазон от 100 до 120, входной массив 20 80 100, допустимый выход:

  0 100
  20 80
  

  вывод 20 100неверен

• диапазон от 90 до 100, входной массив 50 20 40 90 80 30 60 70 40, допустимый вывод:

  0 90
  20 80
  30 70
  40 60
  40 50
  

• диапазон от 90 до 90, входной массив 20 30 40 40 50 60 70 80 90, допустимый вывод:

  0 90
  20 70
  30 60
  40 50
  

• диапазон от 90 до 110, входной массив 40 60 50, допустимый выход:

  40 60
  

CJam, 5,6

Это прямая повторная реализация алгоритма в ответе orlp . Если вы проголосуете за мой ответ, пожалуйста, убедитесь, что вы также проголосовали за этот ответ . Я также предполагаю, что ответ с оригинальным алгоритмом принят, потому что я очень сомневаюсь, что я бы понял, как решить это элегантно в O (n * log (n)).

l~_,0a*+${(\)@_2$+4$~2$\>{;;\;\+}{<{;+}{oSop}?}?_,1>}g;;

Попробуйте онлайн

Пример ввода:

[90 100] [50 20 40 90 80 30 60 70 40]

Объяснение:

l~      Get and interpret input.
_,      Get length of resistor list.
0a*+    Append the same number of 0 values.
$       Sort the list.
{       Loop until less than 2 entries in list.
  (       Pop off first value.
  \)      Pop off last value.
  @_      Pull first value to top, and copy it.
  2$      Copy last value to top.
  +       Add first and last value.
  4$~     Copy specified range to top, and unwrap the two values.
  2$      Copy sum to top.
  \>      Swap and compare for sum to be higher than top of range.
  {       It's higher.
    ;;\;    Some stack cleanup.
    \+      Put first value back to start of resistor list.
  }
  {       Not higher, so two cases left: value is in range, or lower.
    <       Compare if sum is lower than bottom of range.
    {       It's lower.
      ;+      Clean up stack and put last value back to end of resistor list.
    }
    {       Inside range, time to produce some output.
      o       Output first value.
      So      Output space.
      p       Output second value and newline.
    }?      Ternary operator for comparison with lower limit.
  }?      Ternary operator for comparison with upper limit.
  _,      Get length of remaining resistor list.
  1>      Check if greater 1.
}g      End of while loop for processing resistor list.
;;      Clean up stack, output was generated on the fly.

Python 2, 11,5

Питон гольф на этот раз:

(a,b),l=input()
l=[0]*len(l)+sorted(l)
while l:
 e=l[0]+l[-1]
 if a<=e<=b:print l[0],l[-1]
 l=l[e<=b:len(l)-(a<=e)]

Я добавляю один конденсатор емкостью 0 пФ для каждого обычного конденсатора, который больше не нужен. Затем мы сортируем конденсаторы и продолжаем сопряжение самого низкого и самого высокого конденсатора. Если сумма находится в допустимом диапазоне, мы печатаем ее, если она выше диапазона, мы отбрасываем самый высокий, если она ниже, отбрасываем самый низкий.

Пример ввода / вывода:

[[90,100], [20,30,40,40,50,60,70,80,90]]

0 90
20 80
30 70
40 60
40 50