Баг в решении RCC Round 1

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

№	Пользователь	Вклад
1	Um_nik	164
2	-is-this-fft-	161
3	maomao90	160
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

Задача C в первом раунде Russian Code Cup была скорее математической, чем программистской, поэтому получить WA #3 по ней было вдвойне неприятно и обидно. Решение задачи сводилось к тому, чтобы вывести двойку, возведенную в определенную степень. Несколько раз прочесав весь код и перепроверив корректность доказательства, бага в решении мне найти не удалось. В конце концов единственное, что пришло мне в голову — это заменить вызов функции pow(2, ...) на pow(2ll, ...) (функция long long pow(long long a, long long b) возвращала (a ^ b) % 1000000007). Казалось бы, аргументы функции все равно имеют тип long long, поэтому эта двойка должна была так или иначе к long long'у привестись. Каково же было мое удивление, когда новая посылка получила accepted! На контесте ни времени, ни желания разбираться не было, а сегодня я послал в тренировку на Codeforces два решения, отличающиеся только в вызове функции pow от аргумента 2 или 2ll соответственно (на контесте я делал в программе ещё какие-то изменения и это теоретически могло как-то повлиять на результат). Решения все так же получили разные вердикты:

Полное решение: 3553225

http://pastebin.com/XbnmRAis

WA #3: 3553222

http://pastebin.com/pF7UVj17

Собственно, вопрос: почему две программы ведут себя по-разному?

UPD. Вопрос закрыт

template<class _Ty1, class _Ty2> inline typename _STD enable_if< _STD _Is_numeric<_Ty1>::value && _STD _Is_numeric<_Ty2>::value, typename _STD _Common_float_type<_Ty1, _Ty2>::type>::type pow(const _Ty1 _Left, const _Ty2 _Right) { // bring mixed types to a common type typedef typename _STD _Common_float_type<_Ty1, _Ty2>::type type; return (_CSTD pow(type(_Left), type(_Right))); }

Комментарии (8)

Написать комментарий?

Zlobober

11 лет назад, # |

← Rev. 2 →

+18

Леш, а ты уверен, что в первом варианте вообще вызывается твоя функция pow, а не библиотечная, работающая с дробной арифметикой? Попробуй вставить отладочный вывод в ~~первый~~ второй (WA'шащийся) вариант — хоть один вывод происходит?

→ Ответить

Copymaster

11 лет назад, # ^ |

Сейчас проверил, вызывается моя функция в обоих случаях.

+16

Я скомпилировал WA'шащийся код g++ 4.7.2 с ключами -O2 и -g. Лично у меня происходит вызов не твоей написанной функции pow, а std::pow<int, long long>, которая, естественно, переполняется. Если ты уверен, что у тебя вызывается локально твоя функция, возьми третий тест, да продебажь на нём — показывающейся части теста достаточно, у тебя уже десятое число отличается.

Видимо у меня компилятор более старый, у меня локально в обоих случаях работает одинаково. Тесты в тренировке почему-то недоступны. Спасибо)

andreyv

Точно? http://ideone.com/64FRbV

Jacob

+13

Функция pow есть в стандартной библиотеке C++. Я подозреваю, что по какой-то причине у вас вызвалась именно она.

Похоже, что в C++11 это шаблонная функция. В VC++ определение такое:

Сейчас проверил через запуск, на сервере действительно в первом случае вызывается стандартная функция, у меня локально в обоих случаях вызывается моя. Видимо разные версии компиляторов. Спасибо)

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