Здравствуйте, kfmn, Вы писали:

V>>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
K>Уникальные, значит различные?

Именно.


K>nikov про это в условии не писал

Об этом моё замечание.


K>и любое определение fusible numbers открой — там этого нет.

Открыл — есть:
http://googology.wikia.com/wiki/Fusible_number

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


K>>>К тому же по условию ноль содержится в S.
V>>При условии уникальности p и q — да.
V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.
K>Откуда это?

Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.

Тогда принадлежность к нему определяется элементарно (ответил сразу же):

Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.

Итого, решение:

bool isFusible(uint numerator, uint denominator) {
    assert(denominator);
    uint a = numerator, b = denominator;
    while(a!=b) if(a>b) a-=b; else b-=a;
    if(a) denominator/=a;
    return !(denominator&(denominator-1));
}

Здравствуйте, kfmn, Вы писали:

V>>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
K>Уникальные, значит различные?

Именно.


K>nikov про это в условии не писал

Об этом моё замечание.


K>и любое определение fusible numbers открой — там этого нет.

Открыл — есть:
http://googology.wikia.com/wiki/Fusible_number

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


K>>>К тому же по условию ноль содержится в S.
V>>При условии уникальности p и q — да.
V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.
K>Откуда это?

Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.

Тогда принадлежность к нему определяется элементарно (ответил сразу же):

Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.

Итого, решение:
UPD (сравнить с 0-лем и с нижней границей 1/2):

bool isFusible(uint numerator, uint denominator) {
    assert(denominator);

    if(!numerator) return true;
    if(numerator*2<denominator) return false;

    uint a = numerator, b = denominator;
    while(a!=b) if(a>b) a-=b; else b-=a;
    if(a) denominator/=a;
    return !(denominator&(denominator-1));
}