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

Например,

[9,10,9,8] => output: 5

Потому что рабочие места будут выделяться как [9 10 _ 9 8].
1. Во-первых, 9 нуждается в двух охлаждающих точках _ _. Итак, начнем с 9 _ _.
2. Следующее задание 10 отличается от предыдущего задания 9, поэтому мы можем выделить одно из _ _. Тогда мы будем иметь 9 10 _.
3. В-третьих, сейчас нельзя выделить 9, поскольку первое задание 9 - это то же самое задание, и оно требует времени охлаждения. 9 10 _ 9,
4. Последнее, 8 не то же самое, что и любые другие предыдущие два задания, поэтому его можно распределить сразу после 9, и, поскольку это последнее задание, ему не нужно время для охлаждения. Окончательный список 9 10 _ 9 8и ожидаемый результат равен 5, что является количеством мест (или количеством слотов)

Тестовые случаи:

[1,2,3,4,5,6,7,8,9,10] => output : 10 ([1 2 3 4 5 6 7 8 9 10])
[1,1,1] => output: 7 ([1 _ _ 1 _ _ 1])
[3,4,4,3] => output: 6 ([3 4 _ _ 4 3])
[3,4,5,3] => output: 4 ([3 4 5 3])
[3,4,3,4] => output : 5 ([3 4 _ 3 4])
[3,3,4,4] => output : 8 ([3 _ _ 3 4 _ _ 4])
[3,3,4,3] => output : 7 ([3 _ _ 3 4 _ 3])
[3,2,1,3,-4] => output : 5 ([3 2 1 3 -4])
[] => output : 0 ([])
[-1,-1] => output : 4 ([-1 _ _ -1])

Входное значение может быть любым целым числом (отрицательное, 0, положительное). Длина списка заданий составляет 0 <= длина <= 1 000 000.
Выходными данными будет целое число, общее количество слотов, которое указывается в тестовом примере как выходной. Список в скобках показывает, как будет сгенерирован вывод.

Критерий победы
код-гольф

Желе , 14 байт

ṫ-i⁹⁶ẋ⁸;;µƒ⁶L’

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

05AB1E , 22 байта

v¯R¬yQiõˆ}2£yåiˆ}yˆ}¯g

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

v           # Loop over the integers `y` of the (implicit) input-list:
 ¯R         #  Push the global_array, and reverse it
   ¬        #  Get the first item (without popping the reversed global_array itself)
    yQi  }  #  If it's equal to the integer `y`:
       õˆ   #   Add an empty string to the global_array
   2£       #  Then only leave the first 2 items of the reversed global_array
     yåi }  #  If the integer `y` is in these first 2 items:
        ˆ   #   Add the (implicit) input-list to the global_array
 yˆ         #  And push the integer `y` itself to the global_array
}¯g         # After the loop: push the global array, and then pop and push its length
            # (which is output implicitly as result)

Брахилог , 10 байт

Всегда приятно видеть проблему, где Brachylog работает лучше всего

⊆Is₃ᶠ≠ᵐ∧Il

объяснение

⊆I           # Find the minimal ordered superset of the input (and store in I) where:
   s₃ᶠ       #     each substring of length 3
      ≠ᵐ     #     has only distinct numbers
        ∧Il  # and output the length of that superset

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

R , 123 байта

`-`=nchar;x=scan(,'');while(x!=(y=gsub("([^,]+),(([^,]*,){0,1})\\1(,|$)","\\1,\\2,\\1\\4",x)))x=y;-gsub("[^,]","",y)+(-y>1)

Попробуйте онлайн - одна программа!

Попробуйте онлайн - несколько примеров!

Полная программа, которая читает разделенный запятыми список целых чисел в качестве входных данных и выводит необходимые слоты. Я уверен, что это могло бы быть еще лучше, и внедрение этого решения на основе регулярных выражений в некоторых других языках было бы более эффективным в байтах.

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

TSQL-запрос, 158 байт

Входные данные в виде таблицы.

Запрос рекурсивный, так

ВАРИАНТ (МАКСРЕКУРСИЯ 0)

необходимо, потому что список чисел может превышать 100, хотя он может обрабатывать только 32 767 рекурсий - действительно ли нужно ограничение в этой задаче?

DECLARE @ table(a int, r int identity(1,1))
INSERT @ VALUES(3),(3),(4),(4);

WITH k as(SELECT null b,null c,1p
UNION ALL
SELECT iif(a in(b,c),null,a),b,p+iif(a in(b,c),0,1)FROM @,k
WHERE p=r)SELECT sum(1)-1FROM k
OPTION(MAXRECURSION 0) 

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

R , 81 70 байт

sum(l<-rle(s<-scan())$l*3-3,1-l%/%6,((r=rle(diff(s,2)))$l+1)%/%2*!r$v)

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

После нескольких неудачных попыток код стал довольно уродливым и не таким коротким, но, по крайней мере, теперь он работает ...

Сначала мы оцениваем длины последовательных прогонов одной и той же работы. Например, 3, 3, 4, 3это дает:

Run Length Encoding
  lengths: int [1:3] 2 1 1
  values : num [1:3] 3 4 3

Каждый из этих прогонов производит (len - 1) * 3 + 1шаги ( + 1обрабатывается отдельно).

Затем мы обрабатываем вхождения одной и той же работы в двух местах, например:, x, y, xиспользуя diff(s, lag=2). Полученный вектор также разбивается на последовательные функции run ( r) по rleфункциям. Теперь из-за различных чередующихся чередований нам нужно добавить ceiling(r$len/2)шаги для всех серий нулей. Например:

x y x(длина 1) и x y x y(длина 2) оба требуют 1 дополнительный шаг:x y _ x (y)

x y x y x(длина 3) и x y x y x y(длина 4) оба требуют 2 дополнительных шага:x y _ x y _ x (y)

Наконец, нам нужно компенсировать возникновение этих чередований в середине долгого периода выполнения одной и той же работы: x, x, x, x...следовательно, 1-l%/%6вместо простого 1.

Python 2 , 67 байт

r=[]
for x in input():
 while x in r[-2:]:r+=r,
 r+=x,
print len(r)

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

Реализует задачу в буквальном смысле. Использует копии самого списка в качестве «пробелов», так как они не могут равняться любому числу.

Древесный уголь , 27 23 байта

Ｆθ«Ｗ№✂υ±²¦¦¦ι⊞υω⊞υι»ＩＬυ

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Ｆθ«

Цикл работы.

Ｗ№✂υ±²¦¦¦ι⊞υω

Добавьте места охлаждения, пока задание является одним из двух последних в результате.

⊞υι»

Добавьте текущую работу к результату.

ＩＬυ

Распечатать количество пятен.

R , 74 68 байт

length(Reduce(function(x,y)c(y,rep("",match(y,x[2:1],0)),x),scan()))

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

Создает рабочий массив (в обратном порядке), затем принимает длину. Чуть короче, чем ответ Кирилла Л. , поэтому иногда наивный подход довольно хорош. РЕДАКТИРОВАТЬ: снова короче! Я также позаимствовал тестовый шаблон Кирилла.

-6 байт max(0,which(y==x[2:1])) с заменой наmatch(y,x,0) .

Perl 6 , 98 байт

{($!=$,|$_ Z$_ Z .[1..*+1])>>.repeated.squish(:with({$+^=[*] $! ne$^a ne$^b,$b==($!=$a)})).sum+$_}

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

Блерг, должен быть лучший способ сделать это. Я не уверен на 100%, что это полностью правильно, хотя и проходит все крайние случаи, о которых я мог подумать.

По сути, это начинается с группировки всех триплетов входного списка с заполнением в любую сторону. Например, [1,2,1,2]становится (Any,1,2), (1,2,1), (2,1,2), (1,2,Nil). Мы получаем repeatedэлементы в каждом триплете, становясь(), (1), (2), () .

Затем он squishполучает последовательные элементы, которые не являются одним и тем же списком, но имеют одинаковый размер (чтобы не сжимать что-то подобное [1,1,1]), и первый элемент не равен элементу перед ним (потому что мы не можем объединить часы [1,1,2,2]), и наконец, элемент ранее также не был сжат ( [1,2,1,2,1,2]). Таким образом, (1), (2)в приведенном выше примере будут сжаты вместе.

Наконец, мы получаем sumвсе длины этого списка, которые представляют наши вставленные часы, и добавляем длину исходного списка.

Например:

(1,1,1) => (Any,1,1),(1,1,1),(1,1,Nil) => (1),(1,1),(1) => (no squishes) => 4+3 = 7
(1,2,1,2,1,2) => (Any,1,2), (1,2,1), (2,1,2), (1,2,1), (2,1,2), (1,2,Nil) => (),(1),(2),(1),(2),() => squish (1),(2) and (1),(2) => 2+6 = 8

JavaScript (ES6), 57 байт

f=([x,...a],p,q)=>1/x?1+f(x!=p&x!=q?a:[x,...a,x=f],x,p):0

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

комментарии

f = (             // f is a recursive function taking:
  [x,             //   x   = next job
      ...a],      //   a[] = array of remaining jobs
  p,              //   p   = previous job, initially undefined
  q               //   q   = penultimate job, initially undefined
) =>              //
  1 / x ?         // if x is defined and numeric:
    1 +           //   add 1 to the grand total
    f(            //   and do a recursive call to f:
      x != p &    //     if x is different from the previous job
      x != q ?    //     and different from the penultimate job:
        a         //       just pass the remaining jobs
      :           //     else:
        [ x,      //       pass x, which can't be assigned yet
          ...a,   //       pass the remaining jobs
          x = f   //       set x to a non-numeric value
        ],        //
      x,          //     previous job = x
      p           //     penultimate job = previous job
    )             //   end of recursive call
  :               // else:
    0             //   stop recursion

C (gcc) , 69 байтов

f(j,l)int*j;{j=l>1?(*j-*++j?j[-1]==j[l>2]?j++,l--,3:1:3)+f(j,l-1):l;}

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

Простая рекурсия.

f(j,l)int*j;{               //Jobs, (array) Length
    j=l>1                   //if l > 1, do a recursion:
        ? (*j-*++j          // check if first and second elements are equal (j++)
            ? j[-1]==       //  1st!=2nd; check if first and third are equal
                j[l>2]      //  (first and second if l==2, but we already know 1st!=2nd)
                ? j++,l--,3 //   1st==3rd (j++,l--) return 3+f(j+2,l-2)
                : 1         //   1st!=3rd (or l==2) return 1+f(j+1,l-1)
            : 3             //  1st==2nd            return 3+f(j+1,l-1)
          )+f(j,l-1)        // j and l were modified as needed
        : l;                // nothing more needed  return l
}

Perl 6 , 48 байт

{$!=0;.map:{{$_=($!=$!+1 max$_)+3}((%){$_})};$!}

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

45 байт, если список содержит хотя бы два элемента:

+*.reduce:{$^b,|(*xx 3-(|$^a,*,$b...$b)),|$a}

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

Smalltalk, 125 байт

c:=0.n:=q size.1to:n-2do:[:i|(j:=q at:i)=(k:=q at:i+1)ifTrue:[c:=c+2].j=(m:=q at:i+2)ifTrue:[c:=c+1]].k=m ifTrue:[c:=c+1].c+n

объяснение

c : accumulator of proximity penalty
q : input array.
n := q length
i : iteration index from 1 to: n-2 (arrays are 1-based in Smalltalk).
j := memory for element i, saves some few bytes when reused
k := similar to j but for i+1.
m := similar to k but for i+2.

Perl 5 -pl , 42 40 байт

$a{$_}=~s/.*/$\=$&if++$\<$&;$\+3/e}{$_=0

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

Пакет, 184 байта

@echo off
@set l=-
@set p=-
@set n=0
@for %%j in (%*)do @call:c %%j
@exit/b%n%
:c
@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1
@set p=%l%&set l=%1&set/an+=1

Ввод осуществляется через аргументы командной строки, а вывод - через код выхода. Объяснение:

@set l=-
@set p=-

Отслеживайте последние две работы.

@set n=0

Инициализируйте счет.

@for %%j in (%*)do @call:c %%j

Обработайте каждую работу.

@exit/b%n%

Выведите итоговый счет.

:c

Для каждой работы:

@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1

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

@set p=%l%&set l=%1&set/an+=1

Обновите последние две вакансии и выделите место для этой работы.

Swift, 114 байт

func t(a:[Int]){
var s=1
for i in 1...a.count-1{s = a[i-1]==a[i] ? s+3:i>1&&a[i-2]==a[i] ? s+2:s+1}
print("\(s)")}

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

Python 3 , 79 75 байт

-3 байта благодаря mypetlion
-1 байт благодаря Саре J

f=lambda a,b=[]:a and f(*[a[1:],a,a[:1]+b,[b]+b][a[0]in b[:2]::2])or len(b)

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

Java (JDK) , 110 байт

j->{int p,q;for(p=q=j.length;p-->1;q+=j[p]==j[p-1]?2:(p>1&&j[p]==j[p-2]&(p<3||j[p-1]!=j[p-3]))?1:0);return q;}

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

Ungolfed прокомментировал код:

j -> {
    int p, q = j.length; // Run all jobs
    for (p = q; p-- > 1;) { // reverse iterate
        q += j[p] == j[p - 1] ? 2 : // add 2 if prev same
        (p > 1 && j[p] == j[p - 2] & // 1 if 2prev same
        (p < 3 || j[p - 1] != j[p - 3]) // except already done
        ) ? 1 : 0; // otherwise 0
    }
    return q;
}

Желе , 20 байт

ṫ-i⁹⁶x;
⁶;ç³Ṫ¤¥¥³¿L’

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

Хотя это довольно похоже на более короткий ответ @ EriktheOutgolfer , я написал его, не видя его. В любом случае его лучше!

объяснение

Вспомогательная диадическая ссылка, принимает текущий список в качестве левого элемента и следующий элемент в качестве правого

ṫ-            | take the last two items in the list
  i⁹          | find the index of the new item
    ⁶x        | that many space characters
      ;       | prepend to new item

Основная монадическая ссылка, принимает список целых чисел в качестве входных данных

⁶             | start with a single space
 ;            | append...
  ç³Ṫ¤¥       | the helper link called with the current list
              | as left item and the next input item as right
       ¥³¿    | loop the last two as a dyad until the input is empty
          L   | take the length
           ’  | subtract one for the original space

Python 2 , 75 байт

lambda a:len(reduce(lambda b,c:b+[c]*-~((c in b[-2:])+(c in b[-1:])),a,[]))

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

JavaScript (Node.js) , 52 байта

(a,i=0,h={})=>a.map(n=>h[n]=3+(i=h[n]>++i?h[n]:i))|i

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

APL (Dyalog Classic) , 22 байта

≢∊(⊢,⍨⊣,# #↓⍨⍳⍨)/⍵,⊂⍬⍬

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

JavaScript (V8), 101 байт

f=a=>for(var c=0,i=0;i<a.length;i++,c++)a[i-1]==a[i]?c+=2:a[i-2]==a[i]&&(c++,a[i-1]=void 0)
return c}

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

Распакованный код выглядит следующим образом:

function f(a)
{
    var c = 0;
    for (var i = 0; i < a.length; i++, c++)
    {
        if (a[i - 1] == a[i])
            c+=2;
        else if (a[i - 2] == a[i])
            c++,a[i-1]=undefined;
    }

    return c;
}

Моя первая попытка кода-гольфа, вероятно, может быть значительно оптимизирована путем сокращения массива и его рекурсивной передачи.

Zsh , 66 60 байтов

-6 байт из неявного "$@"

for j
{((i=$a[(I)$j]))&&a=
a=("$a[-1]" $j)
((x+=i+1))}
<<<$x

Попробуйте онлайн! Я настоятельно рекомендую добавить set -xв начало, чтобы вы могли следовать.

for j                   # Implicit "$@"
{                       # Use '{' '}' instead of 'do' 'done'
    (( i=$a[(I)$j] )) \ # (see below)
        && a=           # if the previous returned true, empty a
    a=( "$a[-1]" $j )   # set the array to its last element and the new job
    (( x += i + 1 ))    # add number of slots we advanced
}
<<<$x                   # echo back our total

((i=$a[(I)$j]))
    $a[     ]           # Array lookup
       (I)$j            # Get highest index matched by $j, or 0 if not found
  i=                    # Set to i
((           ))         # If i was set nonzero, return true

a всегда содержит последние два задания, поэтому, если поиск находит подходящее задание в a[2] , мы увеличиваем его на три (поскольку слоты заданий будут [... 3 _ _ 3 ...]).

Если aне установлено, поиск не удастся, и арифметическое расширение возвратит ошибку, но это происходит только на первом задании и не является фатальным.

Мы можем сохранить еще один байт, если будем использовать $[x+=i+1]вместо него, и в системе пользователей нет команд, состоящих полностью из цифр.

К (нгн / к) , 27 байтов

{#2_``{y,#[0|2-x?y;`],x}/x}

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