Доброго времени суток, CF. Возник вопрос — просьба. Может ли кто нибудь написать решение задачи С4 из ЕГЭ по информатике на C++ используя map, прокомментировав основные шаги в своем решении? Желательно, чтобы при этом сложность алгоритма была оптимальной, насколько это возможно с map'ом.

Условие.

В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.

Пример входных данных:

6

А+B

Крестики-Нолики

Прямоугольник

Простой делитель

А+В

Простой делитель

Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести. __

Пример выходных данных для приведённого выше примера входных данных:

А+В 2

Простой делитель 2

Крестики-Нолики 1

Прямоугольник 1

Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс. © 2012 Федеральная служба по надзору в сфере образования и науки Российской Федерации

Заранее спасибо =)

Предлагаю выкладывать сюда интересные математические задачи пронумерованно, а в обсуждении писать решения под спойлером с указанием номера задачи. Должно получиться структурированно и интересно.

1) В загоне имеется 101 кролик. Если забрать любого одного, то оставшихся можно разделить на 2 загона по пятьдесят кроликов в каждом, так что суммарный вес первого загона равен суммарному весу другого загона. Докажите, что все крольчата весят одинаково.         (Решена)

Cсылка на обсуждение задачи №1

2) Есть множество из n несовпадающих точек. Известно, что для любых двух точек из этого множества найдется третья из этого множества, лежащая с ними на одной прямой. Нужно доказать, что все точки лежат на одной прямой. 

Ссылка на обсуждение задачи №2

3) Имеется семь одинаковых банок краски, на 9/10 заполненных краской одного из цветов радуги (в каждой банке – свой цвет и цвета разные). Можно ли, переливая краски из банки в банку (и равномерно размешивая содержимое), получить хотя бы в одной банке колер, в котором все цвета смешаны в равной пропорции?

Ссылка на обсуждение задачи №3

4) Существует ли многочлен от двух переменных, принимающий все положительные значения, но нигде не обращающийся в ноль?         (Решена)

Ссылка на обсуждение задачи №4

5) К чему бы вы просуммировали натуральный ряд?         (Решена)

Ссылка на обсуждение задачи №5

6) Рассмотрим лабиринт, комнаты которого занумерованы натуральными числами. Из комнаты с номером 2n можно ходить в комнату с номером n, а из комнаты с номером 2n+1 можно ходить в комнаты с номером 6n+4 и 6n+2. Заметим, что 1 - практически тупик, поскольку ходы 1->4->2->1 или 1->2->1. Заметим также, что в комнаты с номерами вида 3n нет ни одного входа.
а) докажите, что из любой комнаты с нечетным номером, кроме 1, можно попасть в комнату 5.
б) докажите или опровергните, что в любую комнату, номер которой не делится на 3, можно попасть из комнаты номер 5.
в) докажите или опровергните, что для любого n существует х такой, что из 5 можно попасть в x, но при этом обязательно посетить комнату с номером больше, чем n*x.

Ссылка на обсуждение задачи №6

7) Тиран собрал мудрецов и сказал: завтра я вас соберу снова и надену на каждого белую или чёрную шапку - так, что вы увидите шапки других, но не свою. Затем по свистку вы все, не сговариваясь, поднимете левую или правую руку - при этом люди в белых шапках должны поднять одну руку, а в чёрных - другую. И ушёл. Мудрецы погоревали, но потом придумали простой способ сделать требуемое. Какой?          (Решена)

Ссылка на обсуждение задачи №7

8) Есть 9 монет. Среди них одна фальшивая. При чем неизвестно легче она или тяжелее. За какое минимальное число взвешиваний на чашечных весах без гирь ее можно определить.          (Решена)

Ссылка на обсуждение задачи №8

8.1) Аналогично задачи №8, но для 13 монет.          (Решена)

Ссылка на обсуждение задачи №8.1

9) Посчитать преобразование Фурье функции f(x) = sin(x)^2/(x*(x^2+1))

Ссылка на обсуждение задачи №9

10) Известно, что a^2+b^2=9, c^2+d^2=16. Найти сумму всех целых значений, которые может принимать выражение (a-c)^2+(b-d)^2?          (Решена)

Ссылка на обсуждение задачи №10

11) Доказать что если f(f(f(f...f(x)))...)))=x (f(x)-повторено 2011 раз) имеет решение, то и решение будет иметь уравнение f(x)=x. f(x)-непрерывна и задана на всей числовой прямой.          (Решена)

Ссылка на обсуждение задачи №11

12) 1-x+root(3)((x^3)/(3+x))=0   //Кубический корень из дроби x^3/(3+x)

Ссылка на обсуждение задачи №12

13) Семья ночью подошла к мосту. Папа может перейти его за 1 минуту, мама — за 2, малыш — за 5, а бабушка — за 10 минут. У них есть один фонарик. Мост выдерживает только двоих. (Если переходят двое, то они идут с меньшей из их скоростей. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя.).

1) Найдите минимальное время перехода через мост.

2) Приведите последовательность  (стратегию) перехода через мост при условиях, данных в задаче.

Ссылка на обсуждение задачи №13

14) Не отрывая карандаша от бумаги, проведите через 9 точек, расположенных в виде квадрата, 4 отрезка. В исходную точку возвращаться не обязательно.          (Решена)

* * *

* * *

* * *

Ссылка на обсуждение задачи №14

14.1) 16 точек, 6 отрезков, конец ломаной должен совпадать с началом и по каждой точке ровно один раз проходим. (Опираясь на условие предыдущей задачи)

Ссылка на обсуждение задачи №14.1

15) Найти все конечные числовые множества M, удолетворяющие трем условиям:

Пост обновляется по мере поступления новых задач.