Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Logumanov
 Аватар для Logumanov
15 / 11 / 2
Регистрация: 06.03.2014
Сообщений: 71
06.03.2014, 15:44     Подгонка решения задачи под тесты Timus Online Judge, С++ #1
На 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 на втором тесте, в чем может быть ошибка?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
06.03.2014, 21:28     Подгонка решения задачи под тесты Timus Online Judge, С++ #2
<map> упорядочивает по первому значению, но не по второму.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
06.03.2014, 21:39     Подгонка решения задачи под тесты Timus Online Judge, С++ #3
Цитата Сообщение от 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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
06.03.2014, 22:03     Подгонка решения задачи под тесты Timus Online Judge, С++ #4
Вроде в мапе всего 3 эл-та лежит - наверно не очень заметна разница в скорости?

Добавлено через 48 секунд
Мне почему-то кажется, что в обоих случаях константа.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
06.03.2014, 22:10     Подгонка решения задачи под тесты Timus Online Judge, С++ #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от 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;
}
Yandex
Объявления
06.03.2014, 22:10     Подгонка решения задачи под тесты Timus Online Judge, С++
Ответ Создать тему
Опции темы

Текущее время: 21:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru