Подгонка решения задачи под тесты Timus Online Judge, С++

@Logumanov · Регистрация: 06.03.2014

Author24 — интернет-сервис помощи студентам

На Timus Online Judge столкнулся с довольно простой задачей, с которой у меня возникли некоторые проблемы.

Задача:

Программист Денис c детства мечтал побывать в Антарктиде, но почему-то регулярных рейсов туда нет. Поэтому Денис все лето изучал Антарктиду с помощью соседнего кинотеатра. Теперь он знает, что в Антарктиде водится несколько видов пингвинов: Императорские пингвины (Emperor Penguins) — любители петь; Малые пингвины (Little Penguins) — любители потанцевать; Пингвины Макарони (Macaroni Penguins) — любители сёрфинга.
К сожалению, в мультфильмах не было сказано, какой вид пингвинов самый многочисленный. Денис решил выяснить это: он посмотрел эти мультфильмы еще раз, и каждый раз, когда видел пингвина, записывал в блокнот название его вида. Сейчас Денис дал вам блокнот с просьбой выяснить, какой вид пингвинов самый многочисленный.
Исходные данные:
В первой строке записано целое число n — количество записей в блокноте (1 ≤ n ≤ 1000). В каждой из следующих nстрок записано по одному виду пингвинов. Среди видов встречаются только «Emperor Penguin», «Little Penguin» и «Macaroni Penguin».
Результат:
Выведите самый популярный вид пингвинов. Гарантируется, что такой вид только один.

Моё решение:

C++

#include <string>
#include <iostream>
#include <map>
 
using namespace std;
 
int main()
{
    int n;
    scanf("%d\n",&n);
    map<char,int> peng;
    peng['E']=0;
    peng['M']=0;
    peng['L']=0;
    
    string tmp="";
    
    for(int i=0;i<n;i++) {
        getline(cin,tmp);
        if(tmp[0]=='E' || tmp[0]=='M' || tmp[0]=='L') peng[tmp[0]]++;
    }
    map<char,int>::reverse_iterator rit = peng.rbegin();
    switch(rit->first) {
    case 'E': cout<<"Emperor Penguin"<<endl;break;
    case 'M': cout<<"Macaroni Penguin"<<endl;break;
    case 'L': cout<<"Little Penguin"<<endl;
    }
    return 0;
}

Это решение выдает WA на втором тесте, в чем может быть ошибка?

@salam · 06.03.2014, 21:28

<map> упорядочивает по первому значению, но не по второму.

ValeryS · 06.03.2014, 21:39

Сообщение от Logumanov

Это решение выдает WA на втором тесте, в чем может быть ошибка?

Сообщение от Logumanov

map<char,int>::reverse_iterator rit = peng.rbegin();

как думаешь это быстрая операция или нет?

вообще откажись от map
и действуй примерно так

C++

int Q[3]={0,0,0};
for(int i=0;i<n;i++) 
{
getline(cin,tmp);
  if(tmp[0]=='E')
       Q[0]++;
  if(tmp[0]=='M')
      Q[1]++; 
  if( tmp[0]=='L')
      Q[2]++;
}
if(Q[0]>Q[1] && Q[0]>Q[2])
 cout<<"Emperor Penguin"<<endl;
if(Q[1]>Q[0] && Q[1]>Q[2])
 cout<<"Macaroni Penguin"<<endl;
if(Q[2]>Q[0] && Q[2]>Q[1])
 cout<<"Little Penguin"<<endl;

@salam · 06.03.2014, 22:03

Вроде в мапе всего 3 эл-та лежит - наверно не очень заметна разница в скорости?

Добавлено через 48 секунд
Мне почему-то кажется, что в обоих случаях константа.

ValeryS · 06.03.2014, 22:10

Сообщение от salam

Вроде в мапе всего 3 эл-та лежит - наверно не очень заметна разница в скорости?

сортировка знаете ли

могу еще убыстрить
ветвление при чтении выбросить
и сравнение изменить
но будет не так наглядно

C++

int Q[256]={0};
for(int i=0;i<n;i++) 
{
getline(cin,tmp);
  Q[tmp[0]]++;
}
if(Q['E']>Q['M'])
   {
     if( Q['E']>Q['L'])
      cout<<"Emperor Penguin"<<endl;
    else
      cout<<"Little Penguin"<<endl; 
  }
else
 {
 if( Q['M']>Q['L'])
   cout<<"Macaroni Penguin"<<endl;
else
   cout<<"Little Penguin"<<endl;
}

@Lesyonok · 19.03.2022, 22:39

Добрый вечер
А как эту же задачу но только на Python написать?

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	06.03.2014, 21:28	2
	<map> упорядочивает по первому значению, но не по второму. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	06.03.2014, 22:03	4
	Вроде в мапе всего 3 эл-та лежит - наверно не очень заметна разница в скорости? Добавлено через 48 секунд Мне почему-то кажется, что в обоих случаях константа. 0

@Lesyonok 0 / 0 / 1 Регистрация: 14.06.2016 Сообщений: 7
	19.03.2022, 22:39	6
	Добрый вечер А как эту же задачу но только на Python написать? 0

Подгонка решения задачи под тесты Timus Online Judge, С++

Решение