Не верю, что эта задача нерешаема

Я проводил две недели небольшое программерское соревнование, чисто для развлечения (http://esci.ru/kcc2), составил для него 7 задач, 5 из них — довольно стандартные задачи а ля Топкодер, максимально простые, доступные даже школьнику, одну — а ля Топкодер Марафон, на оптимизацию. И одну задачу дал довольно своеобразную, дано было несколько примеров некоторого пакета выдуманного протокола, нужно было сообразить, какая у него структура и написать парсер. Как это ни показалось мне удивительным, но эту задачу никто не смог сделать. Вот ее условие:

Мне интересно узнать, действительно ли я дал нерешаемую задачу, и до формата этого пакета догадаться никак нельзя, или же форумчане wasm.ru все же догадливее участников?

 

Sharp
-

 

Издеваешься? Откуда можно узнать, можно ли в начале пакета писать MS маленькими буквами или нет? Можно ли дополнять пакет нулями или нет? Не говоря уж о том, что по двум правильным пакетам правильно угадать способ вычисления последовательности можно только чудом.

 

Sharp

Встречная задача: найди следующее число в последовательности 23, 59, 12, 86, 33, 82, ... Подсказка: оно положительное и меньше 100.

Твоя задача имеет примерно такой же смысл. Можно без труда сочинить структуру, которая будет описывать все приведенные примеры, но практически наверняка свалится на следующем. Просто задача на "угадай мысли составителя" К сожалению многие олимпиадные задачи грешат этим.

 

Вот, что мне удалось распознать-

4D, 53 - заголовок
xx - если старший бит 1 - контрольная сумма + возможно еще что-то
если старший бит 0 - количество следующих байт блока
xx xx - какие-то коды (по два байта - слова)
00 00 - конец пакета

Далее
1)по первому пакету видно, что после пропуска неизвестных 5 байт, коды "3" и "5" присутствуют в пакете. Но второй пакет, который выводит аж 900 чисел - рубит теорию на корню, о том что коды несиправных хабов передаются последовательно словами.
2) третий пакет полностью соответсвует первому, за исключением числа "00 61" - что и привело к мысли, что первый байт последовательности включает контрольную сумму.
3) самый маразматический пример - это четвертый пакет - не дает вообще никакой информации.

Итак, подзадача -
знаем, что 81 = 00 60 00 09
и 81 <> 00 61 00 09
напишите алгоритм расчета контрольной суммы )))

Так решение скажут?

 

Ultrin Faern

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

 

Sharp
Вот из-за подобных задач на олимпиадах заваливаются вполне нормальные программеры. Во вторых какое отношения эта задача имеет к программированию? - это мат. задача.
По поводу задачи:
Как сказал Ultrin Faern 4D, 53 - заголовок, вполне возможно, на ASCII пишется как "MS".
1-й Пакет
4D 53 05 81 00 60 00 09 00 05 00 03 00 00 - предположим, что в данном случае 05 (3 байт) - это смещение от данной позиции (3) к началу данных пакета. Тогда логично будет что 00 05, 00 03 - это номера сгоревших свитчей. 00 00 - окончание пакета, хотя это тупо. 00 60 и 00 09 - хз. судя по 3-му пакету какие-то важные значения, контрольная сумма, может быть и нет, но их изменение означает битый пакет.

2-й Пакет, 900 сгоревших свитчей.
4D 53 84 00 C0 00 00
900 в HEX = 384h, число 900 с потолка не могло упасть и единственное что сдесь подходит это 4D 53 84 00 C0 00 00
Что не очень сходится с предыдущими исследованиями, где 3 байт это смещение. Предположим что C0 - это сжатие, как в DNS, но там следующий байт - ссылка на смещение от начала, здесь идет конец пакета 00 00, допустим смещение это предыдущий байт перед C0 - 00, тогда всеравно узнать откуда смещение не получается т.к. тройка от 384 просто выдрана из половины байта заголовка, ничего другое здесь не подходит.
3-й Пакет исключительно для сравнения с 1м.
4-й Пакет убит насмерть =)

P.S. Слишком замудренный протокол чтобы просто сообщить о сгоревших свитчах =)

 

im1111
4D 53 05 81 00 60 00 09 00 05 00 03 00 00

 

im1111
Исходных данных тоже явно не хватает - приведены, так сказать, экстремальные случаи - 2 и 900, а вот как будет выглядеть дамп для 3, 4 и хотя бы 5, не сказано. С точки зрения математики, задача явно на мат. индукцию, тогда должно быть достаточное кол-во вариантов для однозначного решения.
ЗЫ
Интересно, как автор топика ее решает

 

Я бы сказал что мы лишь можем подогнать под эти варианты и всё, и еслив мы угадаем это можно будет приравнять к чуду, даже имея бесконечно много пакетов на которые мы можем ваздействовать эта задача не тривиальна (попробуйте от какойнить игры сейфы разобрать), а вдруг там сжатие какоенибуть или зависит от преведущего пакета и т.п.
ЗЫ я как рас с одним фарматом разбирался (верней прогу писал уже по разобранному), так там дафига полей unknown и я как бы посмотрел и понял что там не зря unknown хрен поймешь что делают, и это при том что есть доступ к отправителю пакетов, без сорцов конешно, но есть а тут что?

 

А к чему фраза из 900 не выжел не один, скажу есчё что надо искать бит(байт, дворд) показывающий решим работы, например диапазон, перечисление.

 

Про 900 свитчей всеже непонятно, может их вообще 900 в целом и C0 - означает что не один не найден, инфа на самом деле как сказал Stiver из разряда "угадай мысли составителя". Ну может тут еще htons/htonl применить надо, тогда с контрольными суммами непонятка получится и со всеми данными целиком, ибо узнать у какого поля какой размер не удастся.

 

_

 

4D 53 05 84 00 C0 00 00 - может это версия протокола (в задании пропущена???) ?
4D 53 = MS - сигнатура
C0/60 - тип данных живой/мёртвый
или может ошибка здесь 4D 53 00 84 00 C0 00 00 или 4D 53 84 00 00 C0 00 00

 

Мне показалось очевидным, что прежде всего в пакете следует искать какие-то данные, которые должны в нем присутствовать. Например, во втором пакете должно присутствовать количество свичей, 900 = 1110000100b. В каком виде логично встретить это число, учитывая, что число свичей не больше 50000? Ничего на ум логичнее little-endian word не приходит. Дальше подсказывать?

 

Насчет того, что если если кол-во свичей входит в word то нужно word и искать. Например почитайте формат формат obj (старший бит байта указывает на то, что это word), или например кодирование символов в utf-8 (специальная битовая последовательность в начале байта указывает на размер).

Я уже начинаю думать, что последовательность "4D 53 84 00 C0 00 00"
4D - все-таки заголовок
5 - размер блока? тип блока? контрольня сумма?
384 - число "900"
00 - флаг, что не работает?
C - тип блока?
0 00 00 - конец последовательности?

но это "раскодирование" не подходит для первого примера

 

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

 

Sharp
Мне задачки Бильбо Бэггинса типа "Догадайтесь, что у меня в кармане" не шибко нравятся.

 

Значит вот здесь "84 00 C0 00" кроется число 900, интересно как?
P.S. Если бы это был "правильный протокол" то там было бы наподобе "84 03 С0 00" - вот это нормально, а тут 100% придется мат. функции применять лишние.

 

00C0h * 4 + 0084h

Но как это увязать с первым случаем? Чё эт там вдруг 05 появилось?