Логические задачи.

[crghome]

A=3 B=1

A=3+1
B=1+4
A=4-5

A=-1 B=5
so close.....

what?

A=3+1=4
B=4-1=3
A=4-3=1

result true

 

[belanga]

есть массив int[100] целых чисел от 1 до 100 (могут быть дубли), перемешиваем, задача найти 2 числа, сумма которых составит 52, ну и как обычно надо пооптимальнее

А если таких чисел тупо нет? Могут же быть дубли, так? Значит все 100 чисел могут быть 1. Интересно, думали ли об этом авторы предложенных методов?

 

[burning_LEGION]

А если таких чисел тупо нет? Могут же быть дубли, так? Значит все 100 чисел могут быть 1. Интересно, думали ли об этом авторы предложенных методов?

может и не быть таких чисел, какая разница, цель быстрый алгоритм, а не результат его работы

 

[sto2299]

Второй вариант, ещё проще.
1. Создаём масив My[100], забиваем нулями
2. Первый проход, инкрементируем в этом массиве существующие элементы. My[source]++

будут нули

 

[belanga]

Второй вариант, ещё проще.
1. Создаём масив My[100], забиваем нулями
2. Первый проход, инкрементируем в этом массиве существующие элементы. My[source]++
3. четверть прохода (1-25), ищем пару с ненулевыми My и My[52-i]
4. Если не нашли, проверяем количество чисел 26
?

Это же как проверяем? Может SQL запросом?
Это в пределе 200 проходов.

Сумма всех чисел от 1 до 100 = 5050
если из 5050 вычесть сумму перемешанных цифр, это и даст то число, которое было исключено из массива.





тут я бы глянул в направлении взвешенных/сбалансированных/бинарных деревьев.

классная задача.
кажется придумал.
1. Отсортируем список.(хотя, каежтся, нет смысла сортировать)
2. Создадим список вычетов source+source[0]-52 который опишет отклонения результатов суммирования первого элемента с каждым из остальных от 52.
3. Создадим список разностей всех исх.элементов и первого элемента. Элементы этого списка указывают на сколько отличается величина каждого элемента списка от величины первого элемента.

т.о. у нас будет 2 списка, первый из которых содержит элементы с указанием СКОЛЬКО не хватает до достижения результата при использованиии первого элемента в качестве одного из слагаемых, а второй содержит элементы, величина которых указывает сколько может добавить очередной не первый элемент, если использовать его вместо первого. Останется найти два одинаковых элемента этих массивов, и тогда индекс из первого массива укажет на индекс+1 первого слагаемого, а индекс из второго списка укажет индекс+1 второго слагаемого.

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

Cколько это операций?

 

[sto2299]

Вот очень трудная задача, не знаю может она уже давно известна всем....

Римский патриций решил организовать небольшой фуршет, для чего и подготовил 240 бочек отборного вина. К сожалению, один его недображелатель за 2 дня до пира подсыпал в одну из бочек страшный яд: любой кто попробует хотя бы каплю вина из этой бочки, умирает не более чем через 24 часа. К счастью у патриция есть 5 рабов-дегустаторов. Рабов патрицию не жалко - ими можно спокойно жертвовать. До пира всего два дня, поэтому патриций может попотчевать рабов вином, затем подождать 24 часа, посмотреть на результаты, попотчевать вином оставшихся рабов и подождать ещё 24 часа. Больше у него времени нет. Как определить, в какой бочке яд?

 

[avbua]

Это же как проверяем? Может SQL запросом?
Это в пределе 200 проходов.

if(My[26]>1) и всё, зачем 200 проходов?

будут нули

да, в My будут и нули, и 1, и 2, ..., даже 100 может быть

 

[burning_LEGION]

не то, до смерти не более 24, а не ровно 24 часа

 

[Achenar]

есть массив int[100] целых чисел от 1 до 100 (могут быть дубли), перемешиваем, задача найти 2 числа, сумма которых составит 52, ну и как обычно надо пооптимальнее

0. Дано множество A, в котором 100 целых чисел в пределах от 1 до 100.

1. Создаем множество B на 51 элемент, в нем все нули. Первый элемент B[0].

2. Проходим по множеству A и увеличиваем соответствующее значение в B на 1. Таким образом мы будем знать, сколько каких чисел у нас есть. Значения 52 и выше опускаем.

4. Если B[25] > 1, то у нас не меньше 2 чисел 26 и давай до свидания.

5. Перебираем 25 пар B[0] + B[50], B[1] + B[49]... B[24] + B[26], если в обоих числах пары не нули, то мы нашли ответ.


Можно еще ускорить за счет дополнительной информации в B (если увеличили B[40], тут же выставить в B[10] "я очень жду сюда число" и когда будет увеличено B[10], сразу выдать ответ). Но спорно, все-таки дополнительные операции.


Пример.

A = [1, 45, 67, 22, 55, 89, 7, 26, 13, 17, 58]

B[0] = B[44] = B[21] = B[6] = B[25] = B[12] = B[16] = 1

B[25] меньше двух, не получилось

B[0] и B[50] не устраивают.
B[1] и B[49] не устраивают.
....
B[6] > 0 и B[44] > 0. Ура, товарищи, есть числа 7 и 45, они - ответ.



O(3N), наверное.

 

[belanga]

if(My[26]>1)

Это поиск количества элементов равных 26 ?

Вот очень трудная задача, не знаю может она уже давно известна всем....

Римский патриций решил организовать небольшой фуршет, для чего и подготовил 240 бочек отборного вина. К сожалению, один его недображелатель за 2 дня до пира подсыпал в одну из бочек страшный яд: любой кто попробует хотя бы каплю вина из этой бочки, умирает не более чем через 24 часа. К счастью у патриция есть 5 рабов-дегустаторов. Рабов патрицию не жалко - ими можно спокойно жертвовать. До пира всего два дня, поэтому патриций может попотчевать рабов вином, затем подождать 24 часа, посмотреть на результаты, попотчевать вином оставшихся рабов и подождать ещё 24 часа. Больше у него времени нет. Как определить, в какой бочке яд?

5! * 2 = 240
5 * 5*6 * 2 = 240
Работаем с матрицами 5*6, формируя 5 кружек со смесями из 11 бочек по диагоналям. Рабы-камикадзе позвоялют за 2прохода однозначно идентифицировать йад.

 

[Achenar]

Рабы-камикадзе позвоялют за 2прохода однозначно идентифицировать йад.

Скажите, Вы учли при этом, что часть камикадзе погибнет при первом проходе?

 

[avbua]

Это поиск количества элементов равных 26 ?

это определение есть ли у нас пара чисел 26

0. Дано множество A, в котором 100 целых чисел в пределах от 1 до 100.

1. Создаем множество B на 51 элемент, в нем все нули. Первый элемент B[0].

2. Проходим по множеству A и увеличиваем соответствующее значение в B на 1. Таким образом мы будем знать, сколько каких чисел у нас есть. Значения 52 и выше опускаем.

4. Если B[25] > 1, то у нас не меньше 2 чисел 26 и давай до свидания.

5. Перебираем 25 пар B[0] + B[50], B[1] + B[49]... B[24] + B[26], если в обоих числах пары не нули, то мы нашли ответ.

я уже дал точно такое решение

Вот очень трудная задача, не знаю может она уже давно известна всем....

Римский патриций решил организовать небольшой фуршет, для чего и подготовил 240 бочек отборного вина. К сожалению, один его недображелатель за 2 дня до пира подсыпал в одну из бочек страшный яд: любой кто попробует хотя бы каплю вина из этой бочки, умирает не более чем через 24 часа. К счастью у патриция есть 5 рабов-дегустаторов. Рабов патрицию не жалко - ими можно спокойно жертвовать. До пира всего два дня, поэтому патриций может попотчевать рабов вином, затем подождать 24 часа, посмотреть на результаты, попотчевать вином оставшихся рабов и подождать ещё 24 часа. Больше у него времени нет. Как определить, в какой бочке яд?

5 рабов это 32 комбинации дегустационных комиссий. Самая малочисленная первая комиссия не имеет рабов вообще, самая многочисленная последняя имеет 5 рабов.
Делим 240 бочек на 32 группы:
Если яд в первой группе, то выживут все рабы и туда можно включить 32 бочки для отгадывания во второй день.
Если яд в следующих пяти группах где по одному дегустирующему, то выживут 4 раба и в эти группы можно включить по 16 бочек.
Если яд в следующих десяти группах где по два дегустирующего, то выживут 3 раба и в эти группы можно включить по 8 бочек.
Если яд в следующих десяти группах где по три дегустирующего, то выживут 2 раба и в эти группы можно включить по 4 бочек.
Если яд в следующих пяти группах где по четыре дегустирующего, то выживет 1 раб и в эти группы можно включить по 2 бочки.
И в последней группе не выживет никто, там оставляем одну бочку.

Если всё помножить и сложить, то получится 243 бочки, даже с запасом.
Со вторым днём думаю всё ясно.

 

[belanga]

Скажите, Вы учли при этом, что часть камикадзе погибнет при первом проходе?

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

if(My[26]>1) - это определение есть ли у нас пара чисел 26
На каком это языке? 26 - это индекс массива, не?

э
Делим 240 бочек на 32 группы:

240/32 = 7,5
Как именно производим деление?

 

[avbua]

if(My[26]>1) - это определение есть ли у нас пара чисел 26
На каком это языке? 26 - это индекс массива, не?

В 26-ой ячейке массива My находится количество чисел 26 в массиве source

Как именно производим деление?

После двоетичия и расписывается как производим деление

 

[belanga]

Первый проход, инкрементируем в этом массиве существующие элементы. My[source]++

Ах, так это надо понимать как "инкрементируем в новом массиве элемент индекс которого есть исходном массиве". Ну чтобы получить в каждом элементе нового массива число, равное количеству вхождений индекса в исходный массив.
Тогда код неверный.

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

Имеем 3 раба, 1 день и 80 бочек. Что дальше?

 

[avbua]

Имеем 3 раба, 1 день и 80 бочек. Что дальше?

имеем 8 бочек, в те группы, которые дегустировали по два раба мы включили по 8 бочек

Первый проход, инкрементируем в этом массиве существующие элементы. My[source]++

Ах, так это надо понимать как "инкрементируем в новом массиве элемент индекс которого есть исходном массиве". Ну чтобы получить в каждом элементе нового массива число, равное количеству вхождений индекса в исходный массив.
Тогда код неверный.

В каком месте, если число 5 в source встречается 7 раз, то My[5]=7

 

[belanga]

В каком месте, если число 5 в source встречается 7 раз, то My[5]=7

в этом

В 26-ой ячейке массива My находится количество чисел 26 в массиве source

 

[avbua]

в этом

Конкретно, что не правильно и как должно быть?

 

[Achenar]

240/32 = 7,5
Как именно производим деление?

Если я правильно понял мысль avbua.

Группа 0 - 32 бочки, из нее не пьет никто.
Группа 1 - 16 бочек, из нее пьет первый раб. (00001)
Группа 2 - 16 бочек, из нее пьет второй раб. (00010)
Группа 3 - 8 бочек, из нее пьет первый и второй раб. (00011)
Группа 4 - 16 бочек, из нее пьет третий раб. (00100)
...
Группа 7 - 4 бочки, из нее не пьют четвертый и пятый (00111)
...
Группа 15 - 2 бочки, из нее пьют все, кроме пятого раба (01111)
...
Группа 31 - 1 бочка, и из нее пьют все. (11111)

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

А вот если умер только третий раб (00100), то это 4-я группа, в ней 16 бочек, у нас осталось 4 раба, этого хватит, чтобы разобраться.

Поскольку 5 рабов за два прохода позволяют однозначно выяснить отравленную бочку из 3^5 = 243, то можно просто вычесть 3 из нулевой группы. По условию задачи рабов не жалко.

 

[avbua]

Если я правильно понял мысль avbua.

совершенно верно, у меня только группы чуток не в том порядке шли, но это не принципиально