Перевести число из двоичной системы в системы с основанием 8, 10, 16. 2) Перевести число из восьмеричной системы в системы с основанием 2, 10, 16.
3) Перевести число из десятичной системы в системы с основанием 2, 8, 16.
4) Перевести число из шестнадцатеричной системы в системы с основанием 2, 8, 10.
5) Сложить двоичные числа.
6) Вычесть двоичные числа.

Компьютер — самый необычный инструмент из всех придуманных человеком. Он используется не в материальной, а в умственной, интеллектуальной деятельности людей разных профессий: экономистов, конструкторов, переводчиков, психологов, физиков, художников...

Возможности своего интеллектуального человек постоянно старается расширить. Для этого не только совершенствуется оборудование, «железо» компьютера, но и создаются новые компьютерные программы, программные средства. Эти программы составляются программистами — специалистами в области информатики.


Зачем нужны компьютерные программы? Компьютер часто называют «умной» машиной, однако он не обладает человеческим разумом. Человек действует, когда захочет этого сам, или по заданию других людей. Компьютер ничего не делает «по собственному хотению». Все действия он выполняет только по заданию человека. Для управления действиями компьютера и предназначены компьютерные программы.

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

 Может ли человек, не изучавший информатику, рассказать о своей работе, учебе или любимой игре? Наверное, да. Но одно дело, когда рассказ предназначен для другого человека, и совсем другое, когда сведения нужны для создания компьютерной программы. Объясняя что-то людям, мы можем не вдаваться в какие-то подробности, полагаясь на их опыт, знания, сообразительность. В описаниях, которые составляются при создании компьютерных программ, не должно быть ничего лишнего, но в то же время они не могут полагаться на чей-то опыт или смекалку.

 И еще: эти описания нужно представить не в форме устного рассказа или повести, а в виде наглядных и компактных схем, таблиц, списков. Составлению таких «компьютерных» описаний нужно специально учиться — изучать информатику. Полученные знания и умения можно использовать не только при создании компьютерных программ. Они пригодятся всем, кому приходится составлять описания, инструкции, объяснения. А ведь делать это приходится практически каждому человеку — в любом возрасте и в самых различных ситуациях. 

Алгоритм. Отсортируем массив за O(nlogn). Запустим цикл по всем k, в теле цикла будем искать индексы i <= j, такие, что A[i] + A[j] = -A[k]. Понятно, что этот поиск надо делать за O(n), чтобы общее время работы было квадратичным.

Искать будем с двух указателей. Рассмотрим кусок массива, в котором ищем ответ A[l..r] (первоначально l = 1, r = n). Посмотрим на A[l] + A[r]. Если эта сумма больше, чем нужно, уменьшим на 1 число r, если меньше - увеличим на 1 число l, если равно -A[k] - победа, выводим ответ (l, r, k). Будем повторять это в цикле, пока l не станет больше r.

Если после выполнения цикла по k искомая тройка так и не нашлась, пишем "нет".

Корректность. Пусть в какой-то момент A[l] + A[r] < -A[k]. Тогда, чтобы иметь возможность получить A[i] + A[j] = -A[k], надо сумму увеличить. A[l] оказалось настолько мало, что даже если прибавить к нему самое большое возможное число (а это как раз A[r] - массив-то отсортирован!), то всё равно получается слишком мало. Значит, A[l] в ответе не будет, и можно безбоязненно выкинуть его из рассмотрения. Аналогично будет и в случае, когда A[l] + A[r] > -A[k].
Осталось показать, что если такая тройка индексов существует, то наш алгоритм не выдаст неверный ответ "нет". Но это очевидно: если ответ (I, J, K), то уж при k = K алгоритм что-нибудь да найдёт.

Время работы. Внутренний цикл выдает ответ не более чем за линейное время: всякий раз размер массива уменьшается на 1, всего элементов в массиве n, а на каждом шаге тратится константное время; пусть время выполнения внутреннего цикла T'(n) < an. Тогда все n проходов внешнего цикла затратят время T1(n) <= n T'(n) < an^2.
Сортировку можно сделать за время T2(n) < b nlogn < bn^2
Общее время работы T(n) = T1(n) + T2(n) < an^2 + bn^2 = cn^2