ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Вес Хэмминга: реализация и некоторые вопросы.
25 сообщений из 59, страница 2 из 3
  2  все
Вес Хэмминга: реализация и некоторые вопросы.
    #38990276
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
Dima T, у тебя цикл неправильный

у правильного в конце х = 34179892637
...
Рейтинг: 0 / 0
23.06.2015, 08:27
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990277
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Это хорошо. Но даже если мы будем складывать 10^9 единиц в цикле, нам не хватит одной секунды
...
Рейтинг: 0 / 0
23.06.2015, 08:28
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990285
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
SashaMercuryBarlone,

IDE такой функции не знает. У меня 64 битная платформа.не сильно большая проблема
__popcnt64 = __popcnt32 + __popcnt32
...
Рейтинг: 0 / 0
23.06.2015, 08:38
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990286
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
m_SlaSashaMercuryBarlone,

IDE такой функции не знает. У меня 64 битная платформа.не сильно большая проблема
__popcnt64 = __popcnt32 + __popcnt32

а аргумент у функций правой части какой ?)
...
Рейтинг: 0 / 0
23.06.2015, 08:42
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990287
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
m_SlaDima T, у тебя цикл неправильный

у правильного в конце х = 34179892637
Неправильно условия почитал, думал результат не более 2*10^9

Поправил цикл
Код: plaintext
1.
2.
3.
4.
	long long x = 1;
	for(int i = 0; i < 2000000000; i++) {
		x += popcount3(x);
	}


Результатx=34179892637 time: 9053 ms
В норматив по времени не укладывается :(

 
popcount3(long long x)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
int popcount3(long long x)
{
	static int table[256] ={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,
							2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
							2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
							4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
							2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
							3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
							4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

    union{
        unsigned long long i;
        unsigned char c[8];
    }u;

    u.i = x;

    int res;

    return table[ u.c[0] ]
		+ table[ u.c[1] ]
		+ table[ u.c[2] ]
		+ table[ u.c[3] ]
		+ table[ u.c[4] ]
		+ table[ u.c[5] ]
		+ table[ u.c[6] ]
		+ table[ u.c[7] ];

    return res;

}

...
Рейтинг: 0 / 0
23.06.2015, 08:43
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990292
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
SashaMercurym_Slaпропущено...
не сильно большая проблема
__popcnt64 = __popcnt32 + __popcnt32

а аргумент у функций правой части какой ?)
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
union MY_LARGE_INTEGER
{
    struct
    {
        uint32_t uint32_low;
        uint32_t uint32_high;
    };
    uint64_t uint64;
};

MY_LARGE_INTEGER x;
    x.uint64 = 1;
    popcount32( x.uint32_high ) + popcount32( x.uint32_low )

...
Рейтинг: 0 / 0
23.06.2015, 08:50
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990296
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИМХУ невозможно за секунду посчитать 2 млрд. итераций: частота самого быстрого проца 4 ГГц, считаем что за один такт выполняется 1 команда, получается надо чтобы одна итерация была не более 2 команд.

Надо либо параллелить (хз как), либо искать алгоритм который посчитает без перебора.

Саша, зашли на проверку вариант с таблицей, может проскочит :)
...
Рейтинг: 0 / 0
23.06.2015, 08:58
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990307
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
Dima TИМХУ невозможно за секунду посчитать 2 млрд. итераций: частота самого быстрого проца 4 ГГц, считаем что за один такт выполняется 1 команда, получается надо чтобы одна итерация была не более 2 команд.

Надо либо параллелить (хз как), либо искать алгоритм который посчитает без перебора.

Саша, зашли на проверку вариант с таблицей, может проскочит :)Соглашусь.
Или есть некая закономерность в ряду или использовать заранее просчитанные значения.
...
Рейтинг: 0 / 0
23.06.2015, 09:08
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990312
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Возможно этот теоретический порог можно поднять если заюзать архитектуру с MCMA .
Но стоит ли так сильно оптимизировать? Кто в состоянии так быстро инициализировать такой объем?
Не получим-ли мы очередной "Стебелёк" который внутри себя демострируют потрясающие индексы
перформанса хотя практически непонятно как их с пользой применить.
...
Рейтинг: 0 / 0
23.06.2015, 09:11
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990329
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TИМХУ невозможно за секунду посчитать 2 млрд. итераций: частота самого быстрого проца 4 ГГц, считаем что за один такт выполняется 1 команда, получается надо чтобы одна итерация была не более 2 команд.

Надо либо параллелить (хз как), либо искать алгоритм который посчитает без перебора.

Саша, зашли на проверку вариант с таблицей, может проскочит :)

Может быть. Сейчас попробую
...
Рейтинг: 0 / 0
23.06.2015, 09:37
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990340
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Дмитрий, на 13 тесте Time limit exceeded
...
Рейтинг: 0 / 0
23.06.2015, 09:47
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990347
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДмитрий, на 13 тесте Time limit exceeded
Значит надо изобретать алгоритм без перебора. Искать какие-то зависимости у этой последовательности.
...
Рейтинг: 0 / 0
23.06.2015, 09:56
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990411
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
закономерность есть, похоже ряды от произвольных чисел вливаются в ряд от 1
 
ряд от 1

1, 2, 3, 5, 7, 10, 12, 14, 17, 19, 22, 25, 28, 31, 36, 38, 41, 44, 47, 52, 55, 60, 64, 65, 67, 70, 73, 76, 79, 84, 87, 92, 96, 98, 101, 105, 109, 114, 118, 123, 129, 131, 134, 137, 140, 143, 148, 151, 156, 160, 162, 165, 169, 173, 178, 182, 187, 193, 196, 199, 204
 

begin time key(time)
1 2000000000 34179892637
2 2000000000 34179892659
3 2000000000 34179892681
4 2000000000 34179892681
5 2000000000 34179892702
6 2000000000 34179892702
7 2000000000 34179892725
8 2000000000 34179892725
9 2000000000 34179892748
10 2000000000 34179892748
11 2000000000 34179892767
12 2000000000 34179892767
13 2000000000 34179892767
14 2000000000 34179892789
15 2000000000 34179892810
16 2000000000 34179892789
17 2000000000 34179892810
18 2000000000 34179892810
19 2000000000 34179892830

begin time key(time)
100 2000000000 34179893341
101 2000000000 34179893362
102 2000000000 34179893362
103 2000000000 34179893362
104 2000000000 34179893362
105 2000000000 34179893382
106 2000000000 34179893382
107 2000000000 34179893382
108 2000000000 34179893382
109 2000000000 34179893401
110 2000000000 34179893401
111 2000000000 34179893442
112 2000000000 34179893401
113 2000000000 34179893442
114 2000000000 34179893421
115 2000000000 34179893421
116 2000000000 34179893421
117 2000000000 34179893461
118 2000000000 34179893442
119 2000000000 34179893461
...
Рейтинг: 0 / 0
23.06.2015, 10:53
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990452
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
m_Slaзакономерность есть, похоже ряды от произвольных чисел вливаются в ряд от 1
опередил :)

 
я тоже самое заметил
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
	long long x;

	for(long long k = 1; k < 100000; k++) {
		x = k;
		while(x < 100000) {
			x += popcount3(x);
		}
		printf("k=%llu  x=%llu  time: %d ms\n", k, x, clock());
		if(x != 100009) break;
	}


результат...
k=99799 x=100009 time: 6469 ms
k=99800 x=100007 time: 6469 ms

Дальше таблицу контрольных точек и по выходу на точку расчет по таблице.
...
Рейтинг: 0 / 0
23.06.2015, 11:22
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38990625
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
с заранее рассчитанными значениями считает за 0,6-0,7 сек
...
Рейтинг: 0 / 0
23.06.2015, 13:41
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991197
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вы говорите, что начиная с какого-то шага h любая последовательность (n,k) будет совпадать с последовательностью (1, k+m). Всегда ли это будет так ? Я не был уверен, потому предлагал хранить слой точек через интервалы. Но допустим так. Допустимый интервал решений от 2 до 20*10^9. Пусть контрольные точки будут расположены каждые 10^8. Т.е. потребуется хранить 200 точек a[i],i=0..199. Пусть n находится в интервале (a[i],a[i+1]). Можно ли быть уверенным что (n,k) будет пересекаться с (1, k+m) в точке a[i+1]. Не обязательно. А с a[i+2] ? Тоже не обязательно. А с a[i+3] ?
Метод с использованием слоёв более трудоёмок с точки зрения предварительных вычислений, но зато обоснован. Этот метод не представляется таким, тем не менее попробую его реализовать
...
Рейтинг: 0 / 0
24.06.2015, 02:32
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991211
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Число точек я завысил конечно. Программу написал, пока аналогично TLE. Сейчас ещё раз протестирую и выложу. Кстати, странно, но в этой функции
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
void get_auxilary_data(FILE* out)
{
	long long x = 1;
	for (long long i = 1; i <= 20000000000; i+=100000000){ //20*1000000000
		x = do_set_cycles(x, 100000000, out);
		fprintf(out, "%lli\n", x);
	}
}



20000000000 нужно писать именно так, если я пишу 20*1000000000 то цикл не выполняется. Видимо переполнение. Позже разберусь, пока нужно понять почему TLE и сейчас.
...
Рейтинг: 0 / 0
24.06.2015, 04:37
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991214
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
засчитали задачу
быстродействие на грани фола
первый раз отправил 1,184 сек - не приняли
второй раз (ни чего не менял) 0,858 - приняли :)
...
Рейтинг: 0 / 0
24.06.2015, 05:51
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991215
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
m_Sla, шаг сетки 10^8 ^
...
Рейтинг: 0 / 0
24.06.2015, 06:02
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991216
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
m_Slaзасчитали задачу
быстродействие на грани фола
первый раз отправил 1,184 сек - не приняли
второй раз (ни чего не менял) 0,858 - приняли :)

поздравляю C:
...
Рейтинг: 0 / 0
24.06.2015, 06:02
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991219
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
вроде сдал, пять минут
...
Рейтинг: 0 / 0
24.06.2015, 06:11
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991222
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
m_Sla, тоже сдал, но с шагом 5*10^7
...
Рейтинг: 0 / 0
24.06.2015, 06:19
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991224
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
#include <fstream>

using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");

long long p(long long x)
{
	static int t[256] ={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,
							2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
							2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
							4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
							2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
							3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
							4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

    union{
        unsigned long long i;
        unsigned char c[8];
    }u;

    u.i = x;

    return t[ u.c[0] ]
		+ t[ u.c[1] ]
		+ t[ u.c[2] ]
		+ t[ u.c[3] ]
		+ t[ u.c[4] ]
		+ t[ u.c[5] ]
		+ t[ u.c[6] ]
		+ t[ u.c[7] ];
}

long long k[] = {     1, 708317451, 1469980682, 2262110904, 3043866212, 3862449390, 4668805409, 5470537697,
                        6304910373, 7130085732, 7993963848, 8843341559, 9642632564, 10462457837, 11294354943, 12147801091,
                        13027785740, 13866220876, 14738125641, 15620496693, 16528261375, 17414010602, 18210846386, 19030163466,
                        19866094009, 20716233325, 21598491427, 22434485955, 23305273534, 24189801396, 25096174497, 26001121902,
                        26851772374, 27723118090, 28602397046, 29520182534, 30427698867, 31328121968, 32270214646, 33203913310,
                        34179892637, 34987847882, 35795799216, 999999999999
                  };

int main()
{
    long long v, t;

    cin >> v >> t;

    int i = 0;
    while(v >= k[i+1])
    {
        i++;
    }

    while( t )
    {
        if(v==k[i] ) break;
        if(v==k[i+1]) { i++; break; }

        v += p(v);
        t--;
    }

    while( t >= 50000000)
    {
        i++;
        v = k[i];
        t -= 50000000;
    }

    while(t)
    {
        v += p(v);
        t--;
    }

    cout << v;

    return 0;
}

...
Рейтинг: 0 / 0
24.06.2015, 06:31
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991226
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
#include <stdio.h>
#include <stdlib.h>

#define STEP  50000000

long long a[201] = {1, 708317451, 1469980682, 2262110904, 3043866212, 3862449390, 4668805409, 5470537697, 6304910373, 7130085732, 7993963848, 8843341559, 9642632564, 10462457837, 
11294354943, 12147801091, 13027785740, 13866220876, 14738125641, 15620496693, 16528261375, 17414010602, 18210846386, 19030163466, 19866094009, 20716233325, 21598491427, 22434485955,
23305273534, 24189801396, 25096174497, 26001121902, 26851772374, 27723118090, 28602397046, 29520182534, 30427698867, 31328121968, 32270214646, 33203913310, 34179892637, 34987847882,
35795799216, 36638581537, 37474898933, 38346063129, 39197471652};


int popcount(long long x)
{
	static int table[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4,
		2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
		4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };

	union{
		unsigned long long i;
		unsigned char c[8];
	}u;

	u.i = x;

	int res;

	return table[u.c[0]]
		+ table[u.c[1]]
		+ table[u.c[2]]
		+ table[u.c[3]]
		+ table[u.c[4]]
		+ table[u.c[5]]
		+ table[u.c[6]]
		+ table[u.c[7]];

	return res;

}


long long do_set_cycles(long long x, long long count, FILE* out)
{
	for (long long i = 0; i < count; ++i){
		x = x + popcount(x);
	}
	return x;
}


int main()
{
	FILE* in = fopen("input.txt", "r");
	long long n,k;
	fscanf(in, "%I64d %I64d", &n, &k);
	fclose(in);
	//MAIN ALGORITHM
	FILE* out = fopen("output.txt", "w");
	long long res = n;                    
	if (k > STEP)
	{
		int i = 0;
		while (res != a[i]){
			k -= 1;
			res = res + popcount(res);
			if (res > a[i]) i += 1;
		}	
		int shift = k / STEP;
		res = a[i + shift];
		k -= shift*STEP;

	}
	res = do_set_cycles(res, k, out);
	fprintf(out, "%I64d\n", res);
	fclose(out);
	return 0; 
}

...
Рейтинг: 0 / 0
24.06.2015, 06:36
| Ответить | Цитировать | Написать  
Вес Хэмминга: реализация и некоторые вопросы.
    #38991227
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Только заметил что popcount не совсем корректно написана. Исправил.

 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
#include <stdio.h>

#define STEP  50000000

long long a[201] = {1, 708317451, 1469980682, 2262110904, 3043866212, 3862449390, 4668805409, 5470537697, 6304910373, 7130085732, 7993963848, 8843341559, 9642632564, 10462457837, 
11294354943, 12147801091, 13027785740, 13866220876, 14738125641, 15620496693, 16528261375, 17414010602, 18210846386, 19030163466, 19866094009, 20716233325, 21598491427, 22434485955,
23305273534, 24189801396, 25096174497, 26001121902, 26851772374, 27723118090, 28602397046, 29520182534, 30427698867, 31328121968, 32270214646, 33203913310, 34179892637, 34987847882,
35795799216, 36638581537, 37474898933, 38346063129, 39197471652};


int popcount(long long x)
{
	static int t[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4,
		2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
		4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };

	union{
		unsigned long long i;
		unsigned char c[8];
	}u;

	u.i = x;
	return t[u.c[0]] + t[u.c[1]] + t[u.c[2]] + t[u.c[3]] + t[u.c[4]] + t[u.c[5]] + t[u.c[6]] + t[u.c[7]];
}


long long do_set_cycles(long long x, long long count, FILE* out)
{
	for (long long i = 0; i < count; ++i){
		x = x + popcount(x);
	}
	return x;
}


int main()
{
	FILE* in = fopen("input.txt", "r");
	long long n,k;
	fscanf(in, "%I64d %I64d", &n, &k);
	fclose(in);
	//MAIN ALGORITHM
	FILE* out = fopen("output.txt", "w");
	long long res = n;                    
	if (k > STEP)
	{
		int i = 0;
		while (res != a[i]){
			k -= 1;
			res = res + popcount(res);
			if (res > a[i]) i += 1;
		}	
		int shift = k / STEP;
		res = a[i + shift];
		k -= shift*STEP;

	}
	res = do_set_cycles(res, k, out);
	fprintf(out, "%I64d\n", res);
	fclose(out);
	return 0; 
}

...
Рейтинг: 0 / 0
24.06.2015, 06:45
| Ответить | Цитировать | Написать  
25 сообщений из 59, страница 2 из 3
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Вес Хэмминга: реализация и некоторые вопросы.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]