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

C4 в ЕГЭ по информатике
Автор math, 13 лет назад, По-русски

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

Условие.

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

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

6

А+B

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

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

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

А+В

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

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

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

А+В 2

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

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

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

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

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

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

»
13 лет назад, # |
← Rev. 4   Проголосовать: нравится -15 Проголосовать: не нравится 
include <iostream>
include <map>
include <string>
using namespace std;
int main()
{
 string problem;
 map<string,int> mymap;
 int n;
 cin >> n;
 for(int p = 0; p < n; p++)
 {
  getline(cin,problem);
  ++mymap[problem];
 }
 multimap<int,string> mymultimap2;
 for(map<string,int>::iterator pnt = mymap.begin(); pnt != mymap.end(); ++pnt)
 {
   mymultimap2[pnt->second] = pnt->first;
 }
 multimap<int,string>::iterator pntmymap = --mymultimap2.end();
 int size = mymultimap2.size();
 for(int i = 0; i < min (size,3); i++)
 {
   cout <<  pntmymap->second " " << pntmymap->first << "\n";
   --pntmymap;
 }
 return 0;
}

p.s. только я это не компилил. p.s.s. сорри, у меня раздвоение личности, я сам создаю тему и сам отвечаю :(

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    multimap<> не поддерживает operator []. А также код будет некорректно работать в случае, если несколько задач имеют одинаковую популярность.

    → Ответить
»
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится 
#include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>

using namespace std;
int n;
string s;

int main() {
 map <string,int> m;//структура, сопоставляющая строке число
 map <string,int> :: iterator it;
 scanf("%d\n",&n);
 for (int i=0; i<n; i++)
 {
  getline(cin,s);
  m[s]++;//увеличиваем счётчик данной строки
 }
 multimap <int,string> mm; //структура, сопоставляющая числу строку (может быть одному и тому же несколько строк)
 multimap <int,string> :: reverse_iterator mit;
 for (it=m.begin();it!=m.end();it++)
  mm.insert(make_pair(it->second,it->first));//помещаем в multimap готовую пару <число, строка>
 int step = 0; int prev = -1;
 
 for (mit=mm.rbegin(); mit!=mm.rend(); mit++)//идём по всем элементам multimap
 {
  if (step == 3) break;//уже было 3 различных
  if (mit->first != prev) step++;//если не равен предудущему, то переходим к следующему месту по популярности
  prev = mit->first;
  cout << mit->second << " " << mit->first << endl;//вывод :)
 }
 return 0;
}
→ Ответить
  • »
    »
    13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Выводит в конце лишние " 1"

    Можете еще прокомментировать код, если не очень трудно?

    З.Ы. Это ни грамму не домашнее задание или что то подобное, это чисто для себя, ибо в школе объясняют только часть А и Б

    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Предыдущий пост топикстартера намекает, что перед нами очередной петросян/педобир

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

      Откуда лишние "1"? Может быть из-за того, что в вашем примере "B" в 1 месте латинская, а в другом — кириллица? :0)
      Прокомментировал код (хотя нечего комментировать, почитай раз два).
      ИМХО: Вообще на ЕГЭ всё-таки не стоит так выпендриваться, напиши сортировку пар <строка,число> и хватит :)
      UPD: что-то я разошёлся, разбирайся сам уже :D

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

        Спасибо

        А сортировка пары <строка, число> как будет выглядеть в коде?

        map работает не быстрее?

        В основе map'а ведь сбалансированное двоичное дерево? А в парах что?

        → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Теоретически у нас есть N строк и мы их N раз вставляем в map за log(n)*length(string), т. е. асимптотика O(N*log(N)*SUM), где SUM — сумма длин всех строк(к тому же это всё делается 2 раза). Но у нас всего 11 различных строк, зато N — может быть очень большим, может быть гораздо проще хранить максимум 11 пар <число,строка>, при добавлении новой строки плюсуем её вхождения, если она была, иначе — добавляем пару <1,текущая строка>. O(11*N*SUM) — > O(N*SUM). Потом сортируем 11 пар и выводим.

          → Ответить
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Дожили, на Codeforces обсуждают ЕГЭ по информатике...

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Предлагаете stackoverflow? :)

    Я, конечно, вопрос не изучал, но где еще?

    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится

      Предлагаю не опускать Codeforces до сайта, где помогают школьникам с решением ЕГЭ. Для этого есть контактик/мейл-ру-ответы/егэ-форумы/репетиторы.

      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Замечу что вопрос сформулирован правильно, да и легенда задачи тут к месту. Не надо быть таким предвзятым.

        → Ответить