Сколько времени займет Санта, чтобы доставить свои подарки?

12

Некоторое время назад я отправил этот вызов , который касается того, сколько эльфов Санта должен доставить подарки.

Из-за увеличения численности населения Санта-Клауса в этом году немного напрягает. Хотя в прошлом мы работали очень асинхронно, мы начинаем экспериментировать с синхронизацией. Итак, Санта должен знать, сколько времени ему потребуется, чтобы доставить подарки в каждый регион с заданным количеством эльфов.

Вес угля не изменился за последние два года - он все еще тяжелее, чем подарки, поэтому Санте нужно три эльфа на одного непослушного человека в доме и два эльфа на хорошего человека в доме.

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

Эльфы, которые доставляют подарки, должны тратить четыре секунды * каждая, чтобы доставить подарки, а эльфы, которые доставляют уголь, должны тратить пять секунд * каждая, доставляя его (в соответствии с правилами Администрации авиации Санта-Клауса, перчатки с угольной пылью на них должны быть сожжены немедленно после посадка на санях, что занимает некоторое время). Кроме того, дома должны посещаться в порядке, указанном на карте, слева направо, и эльфы не могут начать доставлять подарки в другие дома, пока все подарки не будут доставлены в дом, в котором они находятся в данный момент.

Если предположить, что у Санты более чем достаточно эльфов для этого региона, потребуется всего лишь столько времени, сколько потребуется, чтобы доставить подарок кому-нибудь из непослушного списка: 5 секунд на дом или 4 секунды на дом, если всем хорошо.

Тем не менее, в отличие от предыдущих сезонов, у этого наступающего Рождества Санта может не быть более чем достаточно эльфов для каждого региона, поэтому 4 секунды - это абсолютное минимальное количество времени * , которое потребуется, чтобы доставить подарки в любой дом, если только нет 0 хорошие люди и 0 непослушных людей, в этом случае это займет 0 секунд.

Кроме того, если даже в одном из домов есть кто-то из непослушного списка, Санте понадобятся как минимум три эльфа. Если, по крайней мере, в одном из домов есть кто-то из приятного списка, и ни в одном из них нет людей в непослушном списке, Санте понадобятся как минимум два эльфа. Если ни один из домов не соответствует духу Рождества, любое количество эльфов (включая 0) займет 0 секунд.

На карте Санты дом представлен как *, а каждый дом разделен на +. Санта по-прежнему использует те же карты, что и в другом задании , но я включу документацию о них здесь.

По обе стороны от дома будет цифра: слева - количество непослушных людей в доме, а справа - количество милых людей в доме. Если на одной стороне нет числа, оно интерпретируется как 0.

Я знаю, это может звучать безумно, но некоторые люди "не любят Рождество", поэтому иногда в доме может не быть номера по обе стороны от него.

Одна из карт Санты может выглядеть примерно так.

1*3+2*+*5+*+4*7

Скажем, у Санты девять сугробов в санях.

  1. (0s) В первом доме 1 озорной и 3 приятных человека. Три эльфа доставляют уголь за пять секунд, а шесть - за четыре секунды. Через пять секунд сани Санты движутся к следующему дому.

  2. (5с) Второй дом имеет 2 непослушных и 0 хороших людей. Шесть эльфов доставляют уголь, занимая пять секунд. Через пять секунд сани Санты движутся к следующему дому.

  3. (10сек) В третьем доме 0 непослушных и 5 хороших людей. Восемь эльфов отправляют четыре подарка (оставленный не может доставить подарок). Через четыре секунды все эльфы вернулись, и двое из них пошли доставить другой подарок (сани должны подождать, пока эльфы вернутся, прежде чем идти в следующий дом), что займет еще четыре секунды

  4. (18-е) Четвертый дом не в духе Рождества, поэтому имеет 0 непослушных и 0 хороших людей, и пропускается

  5. (18-е годы) В пятом доме 4 непослушных и 7 милых людей. Это становится немного сложнее ...

    I. Все девять эльфов идут, чтобы доставить три дара угля (оставьте t + 0, верните t + 5 с) II. Через 5 секунд они все возвращаются на санях, и трое из них идут, чтобы доставить последний подарок угля (оставьте t + 5s, верните t + 10s), в то время как остальные шесть из них отправят три хороших подарка (оставьте t + 5 с, возврат т + 9 с).

    III. Через четыре секунды шесть эльфов вернулись и пошли доставить еще три хороших подарка (оставьте t + 9 с, верните t + 13 с).

    Внутривенно Через одну секунду после того, как они уходят, три эльфа, которые доставляли уголь, возвращаются, и двое из них уходят, чтобы доставить последний хороший подарок (оставьте + 10 с, верните t + 14 с)

  6. (18 + 14 = 32 секунды ) Санта закончил доставку подарков в этот регион.

Как мы видим, Санта доставляет подарки в этот регион всего за 32 секунды . Хотя это была упрощенная версия одной из карт Санты. Обычно карты Санты состоят из нескольких строк и имеют квадратную форму, чтобы лучше соответствовать его списку. Карта нормалей может выглядеть примерно так ( \nв конце каждой строки)

1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*

С 26 эльфами (или любой более высокой суммой) у Санты будет 71 секунда .
С 20 эльфами это займет у Санты 76 секунд .
С 15 эльфами это займет у Санты 80 секунд .
С 3 эльфами это займет у Санты 288 секунд .
С 2 эльфами (или с любым меньшим количеством) это было бы невозможно.

Да, и еще одна вещь - порядок, в котором эльфы доставляют подарки, имеет значение (из-за разницы во времени доставки подарков непослушным / приятным людям), поэтому ваш код должен всегда выводить наименьшее количество времени, которое эльфы могут доставить, доставляя подарки.

Вызов

Помогите Санте определить, сколько времени потребуется определенному количеству эльфов, чтобы доставить подарки.

дома

  • Дом представлен *
  • Дома делятся на +
  • Число слева от дома символизирует количество непослушных людей (число не означает 0)
  • Число справа символизирует количество приятных людей (без цифры означает 0)
  • Во \nвходе могут быть символы новой строки ( ), которые также должны обрабатываться как разделение

Эльфы

  • Санта нуждается в помощи трех эльфов для непослушных людей (уголь намного тяжелее подарков), и этим эльфам потребуется пять секунд *, чтобы доставить подарки
  • Санта нуждается в помощи двух эльфов для хороших людей, и этим эльфам потребуется четыре секунды *, чтобы доставить подарки
  • Если по обе стороны дома нет номера, Санта не будет посещать этот дом, и поэтому это не займет времени (люди, не имеющие духа Рождества, даже не заслуживают угля)

Санта

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

Что делать

Учитывая карту домов и количество эльфов, напечатайте, сколько времени займет Санта, чтобы доставить подарки домам на карте.

* (Я не могу делиться количеством времени, которое требуется эльфам для доставки подарков. Я не могу ни подтвердить, ни опровергнуть, что время, указанное в этом испытании, является правильным)

правила

  • Есть два входа - карта и количество эльфов. Входные данные могут быть либо взяты в качестве аргументов функции, либо из STDIN, либо эквивалентными. Если на вашем языке невозможно получить два ввода, тогда и только тогда вы можете принять два ввода как одну строку ввода, ограниченную каким-либо символом, обычно не входящим во вход (не один из +*\nили 0-9- строка ввода не может быть неоднозначной) например ,.
  • Количество эльфов всегда будет неотрицательным целым числом (0 допустимо)
  • Вывод может быть либо возвращаемым значением функции, либо распечатан в STDOUT или эквивалентный. Если Санта не может доставить подарки в данный регион с заданным количеством эльфов, вы должны вывести последовательное отрицательное число или непротиворечивое сообщение без каких-либо цифр в нем.
  • Все данные, напечатанные в STDERR, будут игнорироваться, поэтому вы не сможете распечатать результат или сообщение об ошибке в STDERR.
  • Ваша программа не может завершиться сбоем, учитывая недопустимое количество эльфов для региона
  • Выводом должно быть только общее количество времени, которое понадобится Санте, чтобы доставить подарки с заданным количеством эльфов.
  • Результатом всегда должно быть наименьшее количество времени, которое требуется эльфам для доставки подарков.
  • Вход будет содержать только цифры, +, *и новой строки \n(если не указан другой символ , который вход будет включать в себя , если ваш язык не может принимать два входа (вид на первом правиле) )
  • Применяются стандартные лазейки

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

"1*1", 5 elves => 5
"1*1", 3 elves => 9
"1*2", 7 elves => 5
"1*2", 5 elves => 10
"1*2", 3 elves => 13
"2*1", 8 elves => 5
"2*1", 5 elves => 9
"2*1", 3 elves => 14
"1*" , 3 elves => 5
"1*" , 2 elves => (error message)
"*1" , 2 elves => 4
"*1" , 0 elves => (error message)
"*"  , 0 elves => 0

"1*1+1*1",   5 elves => 10
"1*1+1*1",   3 elves => 18
"1*1+*+1*1", 3 elves => 18
"1*2+2*1",   8 elves => 10
"1*2+2*1",   7 elves => 14
"1*2+2*1",   6 elves => 18
"1*2+2*1",   3 elves => 27
"1*2+2*1",   2 elves => (error message)
"*+*+*+*",   2 elves => 0
"*+*+*+*",   0 elves => 0

"1*3+2*+*5+*+4*7", 9 elves => 32

(надеюсь, я все понял правильно)

счет

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

Leaderboard

Это фрагмент стека, который генерирует как таблицу лидеров, так и обзор победителей по языкам.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки.

## Language Name, N bytes

Где N - размер вашего сообщения в байтах

Если вы хотите включить в свой заголовок несколько чисел (например, пролистать старые результаты или включить флаги в число байтов), просто убедитесь, что фактический результат является последним числом в вашем заголовке.

## Language Name, <s>K</s> X + 2 = N bytes

Показать фрагмент кода

code-golf string Jojodmo
источник
Я думаю, что 288 следует читать 281 : (1+0+0+1+2+3+1+0+0+0+4+1+0+0+1+2+3+2+0+0)*5+(2+0+4+0+4+0+6+0+0+0+2+1+4+3+0+3+10+0+5+0)*4=21*5+44*4=105+176=281(хотя я должен сказать, что я не прочитал целое «эссе»!)
Джонатан Аллан
@JonathanAllan Да ... я случайно потратил слишком много времени на написание задания ... упс ... В любом случае, главное, чего не хватает, так это тому, что сани Санты должны ждать, пока все эльфы вернутся на борт, прежде чем перейти к следующий дом, так что, хотя сложение всех чисел и умножение их может работать в некоторых случаях, в большинстве случаев это не работает. Например, с 9 эльфами дом 4*7занимает 14 секунд (это покрыто примерно половиной в «эссе», непосредственно перед представлением 2D-карты), но (4 * 5) + (7 * 4) = 48
Jojodmo
Значение 288 для примера с 3 эльфами, так что им всегда придется выполнять полный удар naughty*5+nice*4в каждом доме, верно? (обратите внимание, что нет 4*7в этом примере)
Джонатан Аллан
Всегда ли эльфы всегда убирают уголь с дороги (как в вашем примере) или они планируют эффективно? Например, если бы на карте были 5*15и были 9эльфы, потребовалось бы (минимум) 20 секунд или 22 секунды? Посмотрите эти текстовые представления, чтобы увидеть иллюстрацию этого примера.
Джонатан Аллан
РЕДАКТИРОВАТЬ выше 5*15должен прочитать 4*15.
Джонатан Аллан

Ответы:

4

Рубин , 433 400 байт

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

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

->e,h{h.split(/\+|\n/).map{|h|n,g=h.split(?*).map(&:to_i)+[0,0];return-1if(g>0&&e<2)||(n>0&&e<3);([[3,5]]*n+[[2,4]]*g).permutation.map{|j|c=[0]*e;j.map{|q|w,y=q;k=l=0;r=c.map{|x|a=b=0;c[k..e].map{|r|r<=x ?a+=1:break};(t=k+=1).times{c[t-=1]<=x ?b+=1:break};[a,b]};d=r.inject([]){|v,x|v<<l if x[0]>=w;l+=1;v}.min{|a,b|c[a]<=>c[b]};b=d-r[d][1]+1;z=c[d]+y;(b..(b+w-1)).map{|x|c[x]=z}};c.max}.min||0}.sum}

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

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

elyalvarado
источник
2
Добро пожаловать в PPCG! Вы определенно выбрали трудную задачу для своего первого ответа
Джо Кинг,
2

Java (OpenJDK 8) , 344 байта

График работы с эльфами сложнее, чем я думал, так что это заняло немного времени и довольно долго.

Несмотря на это, это определенно было моим любимым испытанием для игры в гольф! 

(e,d)->{int r=0,x,y,c,p,b,g,m;for(String h:d[0].split("\\+")){d=h.split("\\*",-1);b=new Byte("0"+d[0]);g=new Byte("0"+d[1]);m=-1>>>1;for(y=1;y<=e/3&(x=(e-y*3)/2)>0;c=b/y+(b%y++<1?0:1),p=g/x+(g%x<1?0:1),x=c*5>p*4?c*5:p*4,m=x<m?x:m);for(y=0;b+g>0;b-=c,g-=p){c=e/3<b?e/3:b;x=(e-c*3)/2;p=x<g?x:g;if(c+p<1)return-1;y+=c>0?5:4;}r+=m<y?m:y;}return r;}

Попробуйте онлайн (со всеми тестами)!

Объяснение;

Готовьтесь: это долго

    int r=0,x,y,c,p,b,g,m;               // Define all the variables I need

    for(String h:d[0].split("\\+")){     // Split houses on '+' and loop through them

        d=h.split("\\*",-1);             // Split the current house on '*' using the limit
                                         // to preserve empty strings.

        b=new Byte("0"+d[0]);            // Parse the naughty (b) and nice (g) people
        g=new Byte("0"+d[1]);

        m=-1>>>1;                        // Initialise minimum time as max integer using
                                         // overflow

        for(y=1;y<=e/3&(x=(e-y*3)/2)>0;  // For each number of elves that can concurrently
                                         // deliver coal, and still leave enough elves to
                                         // deliver presents

            c=b/y+(b%y++<1?0:1),         // Determine the number of runs needed to deliver
                                         // all coal using this number of elves

            p=g/x+(g%x<1?0:1),           // Determine the number of runs needed to deliver
                                         // all presents using this number of elves

            x=c*5>p*4?c*5:p*4,           // Get the maximum time required for the
                                         // delivery of coal or presents

            m=x<m?x:m);                  // If this is less than the current minimum time,
                                         // set it as the minimum time


        for(y=0;b+g>0;b-=c,g-=p){        // While there are still people to deliver to;

            c=e/3<b?e/3:b;               // Determine the max amount of coal to deliver

            x=(e-c*3)/2;                 // Determine how many presents can be
                                         // delivered with the remaining elves.

            p=x<g?x:g;                   // If this number is more than nice people
                                         // remaining, just use the nice people remaining

            if(c+p<1)return-1;           // If no presents can be delivered, return the
                                         // error code (-1)

            y+=c>0?5:4;                  // Increase the time by 5 if coal was
                                         // delivered, and 4 if only presents

        }                                // At the end of each loop (see above)
                                         // remove the presents and coal delivered
                                         // from the number of naughty and nice houses

        r+=m<y?m:y;                      // Increment the total time by which ever
                                         // is smaller of the calculated times
    }
    return r;                            // Return the total time

NB. Этот ответ зависит от того, насколько точны мои исправления в тестовых случаях.

Люк Стивенс
источник
Я думаю (e-y*3)/2-> e-y*3>>1сохраняет байт. (Скорее всего, также применимо к (e-c*3)/2.)
Джонатан Фрех
runTest("1*4",5,12);терпит неудачу (вы понимаете "1*4", 5 elves => 13 FAILED. Я был поражен тем, как ваш алгоритм был настолько хорош, чтобы планировать в стольких байтах, поэтому я проверил его по всем возможным комбинациям от 0 до 7 (эльфы, непослушные и милые) и нашел только несколько, где он не в состоянии дать оптимальное время. Это наименьшая комбинация, если она терпит неудачу. Кстати, удивительная логика для планирования, долгое время я не представлял, как ты это сделал.
elyalvarado