Блог пользователя Scorpy

Баги с floating point арифметикой на TopCoder?
Автор Scorpy, 13 лет назад, По-русски

Вот код задачи 500 с SRM 400 (Условие) :

http://pastebin.com/SxWex824 (см. актуальную версию ниже)

В Visual Studio ответ на тест "999999874000003969" правильный, а на Арене выдает в ответ пустой вектор. Насколько я знаю на ТопКодере используется g++ компилятор.

В чем тут может быть проблема?

UPD: После исправления ошибки, на которую указал RiaD-WaW получилось так:

http://pastebin.com/jvZNYk79

Это всё ещё работает в Visual Studio и все ещё не работает в Арене.


  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

for( int i = 2; i <= sqrt(double(a)); i++ )

Для a = n* n sqrt может вернуть что-то типа (n-1).99999999 и a будет считаться простым.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    После исправления ничего не поменялось (см. исправленную версию в посте).
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    а написать  for( int i = 2; i*1LL*i <= a; i++ ) не судьба?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      С этим исправлением всё равно не работает.
      → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

if(i==2)
                  cout<<abs( round(num)-num );

1.16415e-10

const ld eps = 1e-9;

Correct Return Value: Yes

Execution Time: 0.000s

Return Value:
{999999937, 2}


PS: упало на другом тесте из-за того что наоборот что-то нашлось, когда не надо
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Да, так я уже пробовал. Попробуй запустить сис.тесты. На тест {"26293188972239280"} у меня возвращает пустой вектор, а у них нет.
    P.S. И что тогда делать? все возможные варианты eps исчерпаны... :-(
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Все же, кажется, наоборот, у вас - не пустой.
      Можно попробовать eps обратно чуток изменить, например поставить 2*e-10, но это вряд ли зайдет, все же чуток можно изменить логику(см.ниже)
      → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

На самом деле может быть имеет смысл сделать так: привести то что получилось к целому и возвести это в степень обратно.Если сошлось - хорошо

UPD: да, код зашел
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, большое! Заработало вот так:
    if( round( pow( ld( round(num) ), i ) ) == N )
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Что бы уж вообще избавиться от чисел, отличных от целых, можно бин.поиском корень извлекать попробовать
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, имеет смысл указывать кроме номера SRM еще и дивизион, если хотите на задачу указать
→ Ответить