Есть две функции

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

Если не знаешь, как решить подобную задачу, добро пожаловать под кат. Там я расскажу про квантовые алгоритмы и покажу как их эмулировать на самом народном языке — на Python.
 

I’ve come to talk with you again

Давайте чуть более формально поставим задачу о двух функциях. Пусть дана булева функция и о ней априорно известно, что она или константна, то есть для любого из своих аргументов всегда возвращает либо 0, либо 1, или сбалансирована, то есть ровно на половине своих аргументов возвращает 0, а ровно на половине 1. Требуется определить, константна функция или сбалансирована. При этом считается, что время вызова функции несоизмеримо больше любых других операций, поэтому сложность алгоритма определяется количеством вызовов функции.