ЗадАЧА 2.3. Кодове
Дефинираме разстоянието dH(X, Y) между два стринга, с равна дължина X и Y като стандартното разстояние Хаминг, т.е. броят на позициите, в които X и Y се различават.
Например, dH(1001, 0010)=3 и dH(1001111, 0010101)=4.
Нека n ≥ 1 и нека C = W1, W2, . . . , WM е списък от M на брой двоични стрингове, с дължина n.
Разглеждаме C като цикличен списък и дефинираме разстоянието dC(Wi , Wj) между два стринга Wi и Wj в списъка като dC(Wi , Wj) = min{abs(i–j), M–abs(i–j)}.
Нека k удовлетворява 1 ≤ k < n. Ще казваме, че C е цикличен код с дължина n и ширина k, ако за всяко i, j 1 ≤ i, j ≤ M е изпълнено:
(1) Ако dC(Wi , Wj) ≤ k, то dH(Wi , Wj) = dC(Wi , Wj);
(2) Ако dC(Wi , Wj) > k, то dH(Wi , Wj) > k.
Основният проблем в изучаването на цикличните кодове е да се определи максималният брой стрингове в цикличен код с дължина n и ширина k. Точният брой е известен само за някои малки стойности на параметрите n и k. Вашата задача е да генерирате цикличен код с колкото може повече стрингове за дадена двойка n, k.
|
Тест # |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
n |
5 |
6 |
6 |
7 |
7 |
8 |
8 |
9 |
10 |
10 |
|
k |
1 |
1 |
2 |
1 |
2 |
1 |
2 |
2 |
2 |
3 |
|
Вие трябва да предадете 10 файла, съдържащи вашите кодове с параметрите от таблицата по-горе. Не предавайте програма! Първият ред във файла трябва да съдържа: #FILE code t където t е номерът на теста. Следващите M реда трябва да съдържат последователните стрингове от генерирания код с дължина n и ширина k. За всеки тестов пример най-доброто решение, дадено от състезател, ще получи 10 точки. Ако най-доброто решение е код с B стринга, а Вие сте предали вярно решение с M стринга, Вашият резултат ще бъде 10M/B. Той ще бъде закръглен до първата цифра след десетичната точка за всеки пример. Крайният резултат ще бъде закръглен до най-близкото цяло число. |
ПРИМЕР
|
