ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1197. Один в поле воин

Low memory solution
Послано Xel 24 май 2011 03:03
Bring to your attention solution, that based on logical operations and shifts.
It use only 3 bytes memory :-) (2 bytes when use h to storage result (need more checks)).

If used GCC bit count can be replacement to __builtin_popcount and 1-byte instruction in SSE4.





scanf("%c%c\n",&h,&v);
r = 0xFF;
switch(h){
    case 'a': r &= 0x17;break;
    case 'b': r &= 0x3F;break;
    case 'g': r &= 0xFC;break;
    case 'h': r &= 0xE8;break;
}
switch(v){
    case '1': r &= 0x71;break;
    case '2': r &= 0xF3;break;
    case '7': r &= 0xCF;break;
    case '8': r &= 0x8E;break;
}
r -= ((r >> 1) & 0x55);
r = (r & 0x33) + ((r >> 2) & 0x33);
r = r + (r >> 4) & 0x0F;
printf("%d\n", r);
Re: Low memory solution
Послано AterLux 24 май 2011 18:09
Your solution is too big ;) Here low-memory, no-branch, single-line solution (Pascal):

var
  a, b: Char;

...
  ReadLn(a, b);
  WriteLn(((Ord(a) and 15) * (9 - (Ord(a) and 15)) div 9 + 2) * ((Ord(b) and 15) * (9 - (Ord(b) and 15)) div 9 + 2) div 2);
Re: Low memory solution
Послано Xel 24 май 2011 20:58
your solution uses division and multiplication - not good for optimization race =)
but single line is cool )

Edited by author 24.05.2011 20:59

Edited by author 24.05.2011 21:00
Re: Low memory solution
Послано AterLux 25 май 2011 13:29
Even in modern processors unpredictable code-branch will lead pipeline to flush and can take several clock cycles. Often better preffered to use some more calculations than make one code-branch.

Mul and div operations are quick enough, in addition it can be pipelined.

Edited by author 25.05.2011 17:01
Re: Low memory solution
Послано snhih 22 июл 2011 15:23
How did you get this formula? It's perfect!
Re: Low memory solution
Послано Freddy 13 авг 2011 16:18
omg вот это да)) вы бы выиграли чемпионат по самому запутанному коду=)