Помогите с олимпиадой

Y_Mur
При всём уважении ну никак не похожа Ваша версия на правду. Топикстартер вполне правильно понял условие задачи.

А вообще условие задачи оставляет желать лучшего: во-первых, каким идиотам придёт в голову обрабатывать большое количество информации, увеличивая её размеры вдвое, втрое, впятеро... Но это не суть. Во-вторых, за каким хреном указывать, что всегда нечетное K меньше ЛИБО РАВНО тысячи? В-третьих, про нечетность K сказано, а вот про то, что длина S всегда кратна K, умалчивается. И как в случае некратности себя вести, неизвестно. Возможно, следует обрабатывать оставшиеся "биты" в строке, чего не делает пример из первого поста. Но тогда неизвестно, что делать, если число оставшихся "бит" чётно.

 

l_inc

этот широко применяемый приём называется сэмплирование , когда из каждого принимаемого бита делается несколько выборок на более высокой частоте чем частота смены бит в сигнале. Есно при передаче информация не удваивается, упятеряется и т.п., а просто снижается частота передачи до получения хорошего приёма в условиях помех. Тысяча сэмпллов конечно круто но при сильной зашумлённости может и пригодиться нечетное количество сэмплов для того чтобы исключить случай равенства нулей и единиц, при сотнях и тысячах сэмплов это уже не очень принципиально , а когда их 3,5,7, то 0 или 1 всегда перевесят, а если К = 4 то получишь 2 нуля + 2 единицы и гадай что это было?
При сэмплировании полученный сигнал не может получиться не кратным К, поскольку К задаёт приёмник и если передатчик немного недопередаст то приёмник примет в этом "хвосте" нули + помехи.

ЗЫ: А вот передавать символы вместо бит - это действительно только в нарочно не придумаешь )

 

Y_Mur

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

Это очевидно. Я о том и говорю, что о нечетности сказано, поэтому здесь двусмысленность исключена.

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

 

l_inc
про повторную "усиленную" передачу речи и не было Просто входной сигнал для приёмника с сэмплированием выглядит именно как "куча повторяющихся данных. и нужно решить, какие из них все-таки правильные." И сотовая связь тут ни при чём - этот приём (а никакой не стандарт) и в проводных передачах рулит
Конечно согласен - условие составлено шибко мутновато, но если отсеять помехи, возникшие из-за сумбура мыслей составителя задачи то логично будет дополнить пустой хвост нулями, означающими окончание передачи информации или случайными битами имитирующими помехи

Кстати если твоя "посимвольная" трактовка условия задачи верна, то в решении ТС я не вижу ошибок, из-за которых его могли забраковать, или я не внимательно смотрел?

 

Y_Mur

О сотовой связи - это было фигуральное выражение. Сотовая связь в данном случае - то, что не имеет отношения к теме.

Вот чего ни в коем случае нельзя делать, так это дополнять пустой хвост. Это не техническая задача, где требуется решить, как принимать данные в условиях помех. И вообще все, что сказано про «Распределенные центры исследований» - это всего-лишь преамбула, не несущая в себе никакой полезной информации. Можно составить задачу, так: "У Маши три яблока, а у Пети два. Сколько всего яблок они стащили с кухни?" А можно так: "Сколько будет два плюс три?"
В таких задачах составляется условие таким образом, чтобы придумать тест позаковыристее, который не пройдет невнимательный кодер. И трактовка тут может быть только посимвольная, т.к. примеры ввода-вывода даны в условии.
А насчет ошибок... ну я тоже не вижу, если считать, что длина S всегда кратна K.

 

DEEP
Браво, очень интересная идея. У меня только зародилась мысль делить прямоугольник HxW пополам с начала по оси oX,затем по оси оУ(прямые с координатами (H/2;0) - (H/2;W) и (0;W/2) - (H,W/2)) и так делить, пока не останется одна точка(мысль не могу выразить).
Или другая, находить самую нижнюю точку, и соединять ее с самой левой точкой(относительно текущей точки).
Для примера.
Берем точку 2(она самая нижняя). Проведем перпендикуляр к оси оХ, продолжим перпендикуляр и вверх,разбив прямоугольник на 2 плоскости,слева остались 3 точки - 6,4,1. Самой левой относительно точки 2 будет точка 1.
PS: надеюсь будет понятно, если что, могу нарисовать

 

l_inc
Y_Mur
Я задал жюри такой вопрос:
"Длина строки всегда кратна К(len mod K == 0)?Если нет, то возможен случай, когда длина введенной строки меньше K?
Если да,то что делать в таком случае,т.к. возможен случай,когда длина может быть четной,а кол-во бит0 равно бит1"
Жду ответа

 

REASY
тогда уж и про биты\символы уточни

l_inc

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

 

REASY
Тогда сюда же еще стоит уточнить по поводу задачи про приёмники-передатчики:
1) Где в условии сказано, что многоугольник, образованный передатчиками, должен быть выпуклым, либо площадь "экспериментального поля" должна быть максимальна, либо количество передатчиков должно быть минимальным? Без одного из этих условий задача не имеет однозначного решения.
2) В условии написано, что объекты (не передатчики, а именно объекты!) не могут лежать на одной прямой. В какой это геометрии точки (из примера) с координатами (10,3) (3,3) (7,3) не лежат на одной прямой?
3) Кто сказал, что т.н. "линии связи" должны быть отрезками прямых? (придираюсь, конечно, но строгость условия нарушена)

 

Вот что ответил мне по поводу

>"K всегда нечетный. А длина строки всегда кратна K."

 

А он им так или иначе будет. Та точка, что образует "невыпуклость" - и есть приёмник, лежащий внутри поля передатчиков.

А вот про "не лежат на прямой" - это да, пропустил как-то.

 

DEEP

Это Ваша догадка. Из условия это не следует.

 

l_inc
Хм. Ну дык тогда получается, что передатчиками являются все объекты, так как из любого конечного набора точек можно составить невыпуклый многоугольник! А это лишает задачу смысла.

REASY
Т.е. вы поняли мою идею? Иихххаааа, я не безнадёжен в объяснениях! =)
Тогда я завязываю с написанием примера - а то запарился тут уже консольный ввод-вывод вспоминать... =(
Блин, вот ведь прежде чем приступишь к написанию собственно кода - нужно ещё понаделать дофига костылей для связи с внешним миром.

 

Y_Mur
Если

, то получается что эти символы нужно рассматривать как биты(как я решил)?

 

REASY
Нет из этого ничего не следует. Это условие применимо и к битам и к символам.
Если задача действительно про передачу инфы по зашумлённому каналу связи, то однозначно следует работать с битами, а если это некий тестовый пример "от фонаря" то есно может иметься в виду что угодно
Требуй дальнейших уточнений.

 

DEEP
Я так понял, надо применять ур-е прямой и после смотрить принадлежность точки к прямой.
(Х - Х1) (У-У1)
------- = -------, где Х1,У1 и Х2,У2 - координаты точек
(Х2-Х1) (У2-У1)

приводить его к виду Ах+Bу+С = 0, подставлять значение точки в это ур-е, и смотреть, если получившееся значение < 0, то точка находится слева, если > справа, если 0, то точка находится на прямой

 

DEEP
А как вы относитесь к

Этот вариант верен?

 

DEEP
Мне вообще то нужен пример на cpp/c, так что необязательно мучится с асм.
Я не сильно понял вашу идею, вот формула у вас такая вроде получается:
А(Х1,У1),В(Х2,У2),С(Х3,У3). А,В - координаты начала и конца прямой. С - точка на плоскости.
edi = Х3 - Х1
esi = У2 - У1
esi = edi * esi

edi = Х2-Х1
eax = У1 - У3
eax = eax*edi
то что делаете с помощью SETG AL не очень понятно, более привычнее видеть
bool d = (A > B)
MOV AX, A
CMP AX, B
SETG BL

 

Y_Mur
Мой вопрос им:" Вопрос к задаче 4. В условии написано, что S - битовая строка. В примере 1, строку 111000111 нужно рассматривать как последовательность бит(1,0) или последовательность символов "1","0"(символ "1" в кодировке ANSI состоит из 8 бит 00110001,"0" - 00110000)".
ответ: символы"0" и "1"

l_inc

Ответ:
1. выпуклость вытекает из условия задачи (см. информацию о расположении передатчиков)
2. Все объекты не могут лежать на одной прямой. Замечание по поводу строгости задания - учтем.

 

DEEP

Вот я и пишу:

REASY

Никак выпуклость не вытекает из условия задачи. Даже приаттачил пример (на основе официального примера к задаче). Какое из условий задачи нарушено обведенным невыпуклым многоугольником?

Как вариант решения задачи: ищем максимальные углы.
1) Первая точка - любая точка, одна из координат которой минимальна/максимальна. Такая точка всегда будет принадлежать конечному выпуклому многоугольнику.
2) Попарно перебираем все оставшиеся и находим те, с которыми найденная точка, как вершина, образует максимальный угол (если искать на основе скалярного произведения, то ищем минимальный косинус). Одна из найденных точек - следующая точка, принадлежащая конечному выпуклому многоугольнику.
3) Одна из найденных в п.2 точек выбрана на предыдущем шаге. Если другая - НЕ та, которая выбрана на первом шаге, то переходим к п.2. Иначе все передатчики найдены.