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

Задача
4. Передача информации
Исследовательская группа «Распределенные центры исследований» вела серьезный проект, связанный
с обработкой большого количества информации. Любая ошибка может испортить результаты
исследования, поэтому организаторы решили повторять передачу бита K раз. Ваша задача – вывести
верную строку из «верных» битов. «Верным» считается бит, который встретился в блоке из K бит чаще
других.
Входные данные
1 ≤ K ≤ 1000 – длина блока передачи, всегда нечетный.
S – битовая строка, длиной не более 10 000 символов.
Выходные данные
Итоговая строка
Пример
3
111000111
101
5
100001110011111
011

Вот мое решение, но говорится что оно не правильное, может кто скажет в чем?

Код (Text):

1. #include <iostream>
2. #include <string>
3. using namespace std;
4. const int size_of_cc = 16;
5.  
6. int main(int argc,char **argv)
7. {
8.     string str;
9.     int k;
10.     cin >> k;
11.     cin >> str;
12.     if (k == 1)
13.     {
14.         cout << str;return 0;
15.     }
16.     int len = str.length();
17.     int i;
18.    
19.     int bit0 =0;
20.     int bit1 = 0;
21.     string res="";
22.     for (i = 0; i < len;i++)
23.     {
24.         if (str[i] == '0')
25.             bit0++;
26.         else
27.             bit1++;
28.         if ((i+1) % k == 0)
29.         {
30.             if (bit0>bit1)
31.                 res +='0';
32.             else
33.                 res += '1';
34.             bit0=0;
35.             bit1= 0;
36.         }
37.        
38.        
39.     }
40.     cout << res;
41.     return 0;
42. }

 

....

 

Вообще-то битовая строка и строка символов "0", "1" не совсем одно и тоже
И для таких вопросов есть соответсвующий раздел
Да и O2.rar имхо следует заменить на более эффективный O2.7z )

 

Y_Mur
>Вообще-то битовая строка и строка символов "0", "1" не совсем одно и тоже
Условие не я придумывал
А вопросы http://www.wasm.ru/forum/viewtopic.php?id=17088 там рассматриваются лабораторные

 

дык и я про то что в условии речь про битовые строки, а ты почему-то рассматриваешь их как символьные

и здесь тот же хлам по уровню медитации

 

Y_Mur
Вы меня совсем в тупик поставили , а как что их рассматривать?
~~~
Битовые строки — это строки которые состоят из единиц и нулей.

 

REASY
Я думаю, что Y_Mur имеет ввиду то, что
3
111000111
это не строка из 9 символов, а 2 байта в первом из которых содержится 11100011, а во в-ом 1xxxxxxx

 

символ "1" в кодировке ANSI состоит из 8 бит 00110001
если речь о передаче инфы то никто биты символами "0"/"1" заменять есно не будет ))
Стандартная работа с битами - операциями побитового сдвига и логическими операциями or, and, xor с соответствующими битовыми масками.

 

Я прикрепил условие задачи 4. Возможно при переносе условия я допустил ошибку.

 

Что-то очень слабенькие задачи для олимпиады. Скорее смахивает на лабораторные для первокурсников.

 

Вообщем, эта задача "1. Пластиковые карты" оказалась правильной,но "4. Передача информации" пишет Wrong answer on test 5

 

Atlantic
А кто говорит что они сложные?
ЗЫ: тема была создана не для оценки сложности задач.........................

 

Еще вопрос к этой задаче 3. Прикрепил ее.
Условие задачи я не очень понял, но все таки есть решение и специально для проверки написал генератор.
Решение:

Код (Text):

1. #include <iostream>
2. #include <string>
3. #include <cmath>
4. using namespace std;
5.  
6. const int magic_offset = 0x40;
7. int bin2dec(char *array);
8. int main(int argc,char **argv)
9. {
10.     int width,height,len;
11.     cin >> width;
12.     cin >> height;
13.     cin >> len;
14.     if (len == 0)
15.         return 0;
16.     int size_buf = len*2*5;
17.     char bf[8] = "\00";
18.     cin.get();
19.     char *buf = new char[size_buf];
20.     cin.getline(buf,size_buf);
21.     int len_buf = strlen(buf);
22.     char *mask_str = new char[len+1];
23.     int i,k = 0, m = 0;
24.     int temp;
25.     for (i = 0; i < len_buf;i+=2)
26.     {
27.  
28.         bf[k] = buf[i];
29.         k++;
30.         if (k == 5)
31.         {
32.             temp = bin2dec(bf);
33.             if (temp == -1)
34.                 mask_str[m] = 0x20;
35.             else
36.                 mask_str[m] = char(temp+magic_offset);
37.             m++;
38.             k = 0;
39.             memset(bf,0x00,7);
40.         }
41.     }
42.     mask_str[m] = 0x00;
43.     cout << mask_str;
44.    
45.     return 0;
46. }
47. int bin2dec(char *array)
48. {
49.     int res = 0;
50.     if (!strcmp(array,"00001"))
51.     {
52.         res = -1;
53.         return res;
54.     }
55.    
56.     int i,k = 0;
57.     int len = strlen(array);
58.     for (i = len-1;i >=0; i--)
59.     {
60.         if (array[i] == '0')
61.         {
62.             k++;
63.             continue;
64.         }
65.         res += pow(2,(double)k) * (array[i] - 0x30);
66.         k++;
67.     }
68.     return res-1;
69. }

Генератор принимает строку символов, алфавит "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"(_ - это пробел[0x20]), на выходе кодированные символы в bin используя 5 бит.

Код (Text):

1. #include <iostream>
2. #include <string>
3. #include <cmath>
4. using namespace std;
5. string templ[] = {
6.                     "0 0 0 0 1","0 0 0 1 0","0 0 0 1 1","0 0 1 0 0",
7.                     "0 0 1 0 1","0 0 1 1 0","0 0 1 1 1","0 1 0 0 0",
8.                     "0 1 0 0 1","0 1 0 1 0","0 1 0 1 1","0 1 1 0 0",
9.                     "0 1 1 0 1","0 1 1 1 0","0 1 1 1 1","1 0 0 0 0",
10.                     "1 0 0 0 1","1 0 0 1 0","1 0 0 1 1","1 0 1 0 0",
11.                     "1 0 1 0 1","1 0 1 1 0","1 0 1 1 1","1 1 0 0 0",
12.                     "1 1 0 0 1","1 1 0 1 0","1 1 0 1 1","1 1 1 0 0",
13.                     "1 1 1 0 1","1 1 1 1 0","1 1 1 1 1"
14.                 };
15. const int magic_offset = 0x40;
16. int bin2dec(char *array);
17. int main(int argc,char **argv)
18. {
19.     string res;
20.     char buf[4] = "\00";
21.     int hex[512];
22.     char str[512];
23.     cin.getline(str,512);
24.     int len = strlen(str);
25.     int i;
26.     int k;
27.     for (i = 0; i < len; i++)
28.     {
29.         if (str[i] == 0x20)
30.         {hex[i] = 1;continue;}
31.         itoa((int)(str[i]-0x3F),buf,10);
32.         hex[i] = atoi(buf);
33.  
34.     }
35.     for (i = 0; i < len; i++)
36.     {
37.         res += templ[hex[i]-1];
38.         if (i != len - 1)
39.             res += ' ';
40.     }
41.     cout << strlen(str) << endl <<  res;
42.     return 0;
43. }

Входные параметры для примера:
10 10
18
0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

Мда.... Оказалось я не так понял условие задачи 3. Оказывается коды символов в десятичной системе. Решение прикрепил, хотя кому интересно? )

 

Y_Mur
Так вы можете продолжить вашу мысль, а то я ничего нового не могу придумать... И каким способом она поможет решить данную задачу?(Как применить то, о чем вы написали выше)

 

REASY
Первоначальный ход мысли у тебя хоть и дилетантски реализован, но в целом верен, только нужно перейти от символов к битам
маски:
Bit7 = 0x80
Bit6 = 0x40
Bit5 = 0x20
Bit4 = 0x10
Bit3 = 0x08
Bit2 = 0x04
Bit1 = 0x02
Bit0 = 0x01
логическое and символа с соответсвующей маской и проверка результата на 0 дадут состояние соответсвующего бита в символе
можно последовательно прогнать все маски, а можно проверять только старший или младший бит сдвигая байт(символ) влево/вправо.
погугли - инфы и учебников по теме море.

угу задачка далеко не дзенная

 

Y_Mur
Про работу с битам я вроде чуть мыслю, вот даже кусок кода(сам писал), который выводит битовое представления числа от 0-255

Код (Text):

1. void printByte(unsigned char value)
2. {
3.     int i;
4.     unsigned char j=0x80;
5.     for(i=7; i >= 0; i--)
6.         {
7.         cout << bool(j & value);
8.         j=j >> 1;
9.         }
10. }

Прощу вас показать на пальцах что мне сделать со строкой из первого примера:
Длина блока передачи - 3.
Затем сама битовая строка 111000111.

 

Вот еще одна задача, она мне показалось более сложной. У меня нет даже предположений как начать ее решать(может только пошаманить с координатами,хотя,я думаю, само решение и будет работа с координатами).
Задача также прикреплена.

 

Вот ее графическое решение. Тоже прикрепил.

 

REASY

Мне решение представляется так.

Проходимся по массиву вот этим:

Код (Text):

1. FindSemiplane proc;
2.   PUSH ESI;
3.   PUSH EDI;
4.  
5.   MOV EDI, DWORD PTR [ECX];
6.   SUB EDI, DWORD PTR [EAX];
7.   MOV ESI, DWORD PTR [EDX+4];
8.   SUB ESI, DWORD PTR [EAX+4];
9.   IMUL ESI, EDI;
10.  
11.   MOV EDI, DWORD PTR [EDX];
12.   SUB EDI, DWORD PTR [EAX];
13.   MOV EAX, DWORD PTR [EAX+4];
14.   SUB EAX, DWORD PTR [ECX+4];
15.   IMUL EAX, EDI;
16.  
17.   ADD EAX, ESI;
18.   JE @exit;
19.   SETG AL;
20.   MOVZX EAX, AL;
21.   ADD EAX, 1;
22.   @exit:
23.  
24.   POP EDI;
25.   POP ESI;
26.   RET;
27. FindSemiplane endp;

Если все остальные точки, кроме уже входящих в "контур передатчиков", лежат по одну сторону от проверяемого вектора, добавляем его в контур, и начинаем проверку для вектора "конечная точка контура -> следующая в списке". Если точки (кроме уже добавленных - их можно не проверять) есть с обеих сторон, берём следующую и делаем её концом вектора. Если получилось, она становится началом.

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

PS. Данной функции нужно в EAX, EDX и ЕСХ скормить указатели на структуры, содержащие по 2 DWORD каждая - первые два это соответственно начало и конец вектора, третий - это точка, для которой определяем её позицию. На выход подаётся либо 1, либо 2, либо 0. Первое означает, что точка лежит в левой полуплоскости при данном векторе как разделителе, второе - что в правой, третье - на границе раздела.

PPS. Проверку можно считать не пройденной, когда найден хотя бы один объект, лежащий по другую сторону, нежели ранее найденные. Останавливаем и переходим к следующей точке.

[+]: Кстати да. "Нужная" сторона, по которую должны лежать все точки, определяется при первом найденном векторе, и далее не меняется!

Извините что сумбурно и непонятно. Щас разберу на примере. Вот только реализацию допишу...