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

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

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

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

Задача:

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

Моё решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 написать?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .

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

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

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

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

Решение