1 Востаннє редагувалося Yola (02.12.2015 11:08:38)

Тема: Задача про конференцію з обміну досвідом

Уявіть собі, що вам випала честь відповідати за розселення гостей на конференції з обміну досвідом. Кожен гість представляє одну галузь знань, і кожну галузь можуть представляти декілька гостей. Всі гості жадають отримати якомога більше знань з інших галузей. Ваше завдання поселити гостей так, щоб гості з однієї галузі знань не проживали поруч. Наприклад,

Вхід: aaabc
Вихід: abaca

Вхід: aa
Вихід: Немає розв'язку

2

Re: Задача про конференцію з обміну досвідом

0. Перевіряємо, чи гостей якоїсь галузі не більше, ніж половина. Якщо більше - немає розв'язку.
1. Сортуємо гостей за кількістю (щоб виходило cccaab). Можна скористатися сортуванням підрахунком, це тут оптимально.
2. Розставляємо першу половину на парні місця, решту на непарні.
Оскільки сортування підрахунком складається з двох фаз, першу можна сумістити з п.0, другу - з п. 2. Тобто просто модифікуємо сортування підрахунком і все.

Подякували: Yola1

3

Re: Задача про конференцію з обміну досвідом

І що складного? селити на різних поверхах.

4 Востаннє редагувалося Yola (02.12.2015 12:03:40)

Re: Задача про конференцію з обміну досвідом

koala написав:

0. Перевіряємо, чи гостей якоїсь галузі не більше, ніж половина. Якщо більше - немає розв'язку.
1. Сортуємо гостей за кількістю (щоб виходило cccaab). Можна скористатися сортуванням підрахунком, це тут оптимально.
2. Розставляємо першу половину на парні місця, решту на непарні.
Оскільки сортування підрахунком складається з двох фаз, першу можна сумістити з п.0, другу - з п. 2. Тобто просто модифікуємо сортування підрахунком і все.

Мені знов соромно за себе, я хотів використовувати купу, і на кожному кроці вибирати елемент з того, якого найбільше залишилось.

5

Re: Задача про конференцію з обміну досвідом

koala написав:

0. Перевіряємо, чи гостей якоїсь галузі не більше, ніж половина. Якщо більше - немає розв'язку.
1. Сортуємо гостей за кількістю (щоб виходило cccaab). Можна скористатися сортуванням підрахунком, це тут оптимально.
2. Розставляємо першу половину на парні місця, решту на непарні.
Оскільки сортування підрахунком складається з двох фаз, першу можна сумістити з п.0, другу - з п. 2. Тобто просто модифікуємо сортування підрахунком і все.

По духу задачі краще було б модифікувати другий пункт:
2. Розставляємо першу третину на місця, що діляться без остачі на 3, другу - на місця, що дають остачу 1, а третю - на місця, що дають остачу 2.
Учасники краще поставляться до схеми abcabcabcabc, ніж до ababacacbcbc.

Але це якщо змінити завдання на "задовольніть найбільше учасників".

6

Re: Задача про конференцію з обміну досвідом

Але це за умови, що це можливо. Інакше доведеться шукати спершу розміщення для елементів a (частину - через 2, частину - через 1), потім - для елементів b...

7

Re: Задача про конференцію з обміну досвідом

Я не можу зрозуміти поки що, про який випадок ви говорите. Якщо найбільша група більша за n/3 + 1, то розміщення з унікальними сусідами немає, а в іншому випадку алгоритм працює. Чи ні?

8

Re: Задача про конференцію з обміну досвідом

Розміщення немає, але може бути наближення, краще за перший алгоритм. Скажімо, для набору aaaabbbcc варіант abcabcaba виглядає привабливішим за ababacacb.

9 Востаннє редагувалося coder (02.12.2015 16:35:27)

Re: Задача про конференцію з обміну досвідом

А якщо крісла у конференцзалі стоять не в 1 ряд а є багатовимірним масивом? Припустимо що в один ряд по 4 крісла і тоді ababacacbcbc перетвориться в:
abab
acac
bcbc

Тепер виходить що а сидить ззаду за a, с за с і т.д.

10

Re: Задача про конференцію з обміну досвідом

Вийшло таке..

$input = 'aaaabbcccff';
//переторюємо рядок в масив та в новий масив типу
// 'буква'=>'її кількість'
$acv = array_count_values(str_split($input));
//сортуємо його по кількості від більшого до меншого
arsort($acv);
//новий масив
$arr = [];
//перебираємо масив acv за ключем і значенням
foreach($acv as $key=>$value)
//пишемо в масив вкладені масиви, які
//складаються з кількості символів типу 3 - (a,a,a)
$arr[] = str_split(str_repeat($key, $value));
//далі з кожного масиву беремо по черзі один елемент
$out = null;
for($i=0; $i<count($arr[0]); $i++)
  for($j=0; $j<count($arr); $j++)
    $out.= isset($arr[$j][$i]) ? $arr[$j][$i] : null;

echo 'Input: '.$input.PHP_EOL.'Out: '.$out;

Результат: http://ideone.com/7PU9VB