[Algorytm] Unikalne sumy

[dex19]

Cześć,
Mam listę zdarzeń i każdemu z nich nadaję ID (integer).
Te ID po wystąpieniu zdarzenia są sumowane w jednym polu (to jest wymagane i tego nie jestem w tanie zmienić).
Na podstawie tej sumy muszę określić jaka kombinacja zdarzeń wystąpiła.

Jak można zapewnić unikalność tych sum?

W tej chwili ID są z zakresu \(\displaystyle{ 100-300}\), następnie przepuszczone przez \(\displaystyle{ \left( \log \left( x \right) \cdot 10000 \right)}\)


pozdrawiam
dex

[M Maciejewski]

Nie do końca rozumiem, o co chodzi, ale jeśli za ID będziesz brać kolejne potęgi dwójki, to powinno być ok.
Dla przykładu: Masz 5 zdarzeń. Mają one następujące ID: 1,2,4,8,16. Wybierasz zdarzenia pierwsze i trzecie, czyli zdarzenia o ID równym 1 i 4. Po zsumowaniu masz liczbę 5, która w systemie dwójkowym ma zapis 000000101 (najmłodszy bajt). Można bez problemu określić, że wybrane są dwa zdarzenia: pierwszy i trzeci.

[Afish]

Jeżeli zdarzenia mogą się powtarzać dowolnie wiele razy, to nie da się odzyskać wszystkich informacji mając tylko sumę. Przyjęcie kolejnych potęg jakiejś liczby za identyfikatory zadziała, gdy zdarzenia nie powtórzą się zbyt często.

[dex19]

Dzięki za odpowiedzi.

Mam mechanizm który zapewnia mi to, że zliczane jest tylko pojedyncze wystąpienia.
Zdarzenia moga wystąpić dowolną ilość razy, to nie jest problem.

Z tymi potęgami dwójki może być problem - zdarzeń jest około 150 (w tej chwili) - 2^150 to trochę za dużo w środowisku w którym to robię.

[Medea 2]

Artlandia i Zenodia były w stanie wojny. Wywiad Artlandii odkrył, że w pewnym
mieście w Zenodii wielce prawdopodobnie produkowana jest śmiercionośna broń. W
mieście tym było 12 fabryk i wiadomo było, że co najwyżej w trzech z nich może
być wytwarzana ta broń. Artlandia wysłała więc swojego szpiega do Zenodii z
zadaniem, by ten zdobył i przesłał szyfrem do centrali wywiadu informację, w
których z tych 12 fabryk wytwarza się tę broń. Zawczasu uzgodniono, że
informacja ta zakodowana będzie za pomocą jednej liczby, która jednoznacznie
określi, jakie trzy (lub dwie, lub jedna, lub żadna) z 12 fabryk produkują tę
broń i przez to mają być zbombardowane. Szyfr został ustalony w następujący
sposób: wpierw każdej fabryce przypisano odpowiednią liczbę naturalną,
następnie posiadający ten zestaw szpieg miał w szyfrogramie przesłać sumę
liczb odpowiadających namierzonym fabrykom, ewentualnie sumę dwóch z nich
(jeśliby tylko dwie produkowały broń) lub liczbę równą tej jednej, lub po
prostu zero (gdyby żadna z fabryk nie produkowała broni). Oczywiście ta jedna
ostateczna liczba-suma musiała być absolutnie jednoznaczna. Dla przykładu
przypuśćmy, że do zakodowania są maksymalnie trzy obiekty. Można im
przydzielić odpowiednio liczby 10, 11, 12. Teraz każda suma jednoznacznie
określi, o jaki zbiór nam chodzi. 21 wskaże na 10+11, 22 na 10+12, 33 na
10+11+12 itd. Każda suma oznacza po prostu inny zbiór. Oczywiście zadanie dla
szpiega byłoby bardzo łatwe, gdyby mógł przypisać dowolnie duże liczby
kolejnym fabrykom, np. 10, 100, 1000, 10000 itd. Ale rzecz w tym, żeby
największa możliwa suma, jaką ma przekazać do Arlandii, była jak najmniejsza i
to z wielu powodów, choćby zminimalizowania zagrożenia przechwycenia i
rozszyfrowania wiadomości przez kryptologów Zenodii.

Jaki zestaw 12 liczb naturalnych, dzięki któremu możliwe było jednoznaczne
zakodowanie w powyżej opisany sposób trzech z dwunastu fabryk produkujących
broń, opracowali szyfrolodzy Artlandii biorąc pod uwagę, że największa suma
trzech liczb z tego zbioru była najmniejsza z możliwych?

W rozwiązaniu podaj po prostu największą sumę, jaka może widnieć w
szyfrogramie szpiega z Artlandii.

Ukryta treść:    

2
4
8
16
32
60
73
116
207
230
341
452

[dex19]

fabryk mamy 150 , broń może być produkowana od 1 do ~7 fabryk...