Алгоритм вопроса (Google code jam 2011, Аравия 2011)

Question

Существует пул чисел, которые являются произвольными десятичными дробями из интервала (0, 1). В первом раунде игры средняя треть интервала исчезает, а числа из этого интервала удаляются из пула. В следующих раундах средние трети каждого из оставшихся интервалов исчезают. В первом раунде интервал [1/3, 2/3] исключен, а во втором раунде два интервала [1/9, 2/9] и [7/9, 8/9] исключены, и поэтому на. Конечные точки каждого удаленного интервала также удаляются.

Ваша роль состоит в сортировке пула чисел в порядке их исключения. Если некоторые цифры никогда не удаляются, перечислите их последними. В случае ничьей сначала перечислите меньшие числа.

int getRound(double lb, double ub, double val){
double lb2 = (2*lb + ub)/3.0;
double ub2 = (lb +2*ub)/3.0;
if((lb2<=val)&&(val<=ub2)) return 1;
else if (val<lb2){
    return 1+getRound(lb,lb2,val);
}
else return getRound(ub2,ub,val)+1;

}

int main(){
    int N;
    cin >> N;

    vector <pair<int,double> > vp;
    for(int j=0;j<N;j++){           
        double x;
        cin >> x;
        int r = getRound(0,1.0,x);
        //if(r>25) r = 25;
        pair <int,double> pid;
        pid.first = r;
        pid.second = x;
        vp.push_back(pid);
    }
    sort(vp.begin(),vp.end());
    for(int j=0;j<vp.size();j++){
        cout << vp[j].second << endl;
    }
}

Позвольте мне немного пояснить приведенный выше код. Целое число N - длина тестового массива.

Может кто-нибудь помочь мне проверить вышеуказанный код? Или дайте мне какие-то особые случаи, которые не работают в приведенном выше коде? Я верю, что существуют особые случаи.

Спасибо

Answer 1

Ваша логика выглядит правильно, но я бы обеспокоен тем, что могут быть случаи, когда getRound может зайти в бесконечный цикл. Я также вернул бы 1, если ub - lb < 0.1**12. Это предотвратит попадание ошибок с плавающей запятой в бесконечный цикл. Однако у вас есть жестко закодированная константа.

Вместо этого я мог бы пойти по пути взятия val и умножения на 3 в каждом раунде, затем вычитая 1, а затем проверяя, находится ли он в диапазоне 0 < val < 1. Если вы сделаете это, то захотите ограничить количество раундов, которые вы можете пройти. Преимущество этого состоит в том, что вы избегаете ошибок округления при делении на 3, что может привести к логическим ошибкам при обработке чисел, которые вы можете представить. При умножении на 3 единственно возможные логические ошибки связаны с округлением при создании стартового номера.