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

Ошибка в программе или алгоритме (Задача Океанариум) - C++

Восстановить пароль Регистрация
 
Bohes_
4 / 4 / 0
Регистрация: 18.06.2013
Сообщений: 51
03.08.2013, 16:27     Ошибка в программе или алгоритме (Задача Океанариум) #1
Помогите,пожайлуста, найти неточности\ошибку в программе или в ее алгоритме.

Условие
Петя часто ходит в Океанариум — особенно ему там нравится один большой аквариум, в котором плавают разнообразные маленькие рыбки. Пете очень интересно, сколько всего рыбок в аквариуме, но часть из них всё время скрывается за камнями и водорослями. Поэтому каждый раз, когда Петя подходил к аквариуму, он выписывал на листок названия всех рыбок, которые были ему видны.
Всего у Пети скопилось N таких листков. Требуется написать программу, которая по Петиным записям определит минимально возможное количество рыбок в аквариуме.
Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста, а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.
Рекомендуется рассмотреть частичные решения
N = 1,
каждый листок содержит ровно одно название рыбки.
Формат входного файла
Первая строка входного файла содержит число N. Далее следует последовательность из N описаний листков. В первой строке каждого описания содержится число рыбок Ki, в последующих Ki строках — названия рыбок.
Формат выходного файла
Выходной файл должен содержать единственное число — минимальное количество рыбок.
Ограничения
1 ≤ N, Ki ≤ 50, длина названий не превосходит 255 символов.
Мой код:
C++ (Qt)
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <fstream>
#include <string>
using namespace std;
 
 
struct Fish
{
    string Name;
    unsigned char count; //минимально возможное число рыбок
    unsigned char count2; //количество рыбок на данном листке
};
int main()
{
    int i,j,a,b,N=-1; //a -- количество листков, b --число рыбок на данном листке
    int sum = 0;
    string tempName="";
    Fish * Aquarium = new Fish[51];
    ifstream f ("input.txt");
    
    for (i = 0; i < 51; ++ i)
        {
            Aquarium[i].Name = "";
            Aquarium[i].count = 0;
            Aquarium[i].count2 = 0;
        }
    
    
    f>>a;
    for (i = 1; i <= a; ++i)
    {
        
        f>>b;
        for (j=1; j <= b; ++j)
        {
            getline(f,tempName);
            bool isFind=false;
            char FindNumber = -1;
            for (int k = 0; k <= N; k++) //Поиск по названию рабки
                {
                    if (Aquarium[k].Name == tempName) {isFind = 1; FindNumber = k;}
                }
            if (isFind) 
                {
                    Aquarium[FindNumber].count2++;
                }
                else
                {
                    N++;
                    Aquarium[N].Name = tempName;
                    Aquarium[N].count2 ++; 
                }
                
        }
        
        for (int k =0; k <= N; ++k)
         {
            if (Aquarium[k].count < Aquarium[k].count2) {Aquarium[k].count = Aquarium[k].count2;}
            Aquarium[k].count2 = 0;
         }
        
    }
    
    ofstream o ("output.txt");
    
    for (int k=0; k <=N; ++k)
        sum +=Aquarium[k].count;
        
    o << sum;
    
        
    delete[] Aquarium;
    
    return 0;
}
Входной файл
3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead
Выходной
8
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.08.2013, 16:27     Ошибка в программе или алгоритме (Задача Океанариум)
Посмотрите здесь:

C++ Ошибка в алгоритме
функции. (ошибка в алгоритме) C++
Ошибка в алгоритме слияние массивов C++
Ошибка в алгоритме сортировки C++
Ошибка в алгоритме со строками C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
03.08.2013, 17:26     Ошибка в программе или алгоритме (Задача Океанариум) #2
На мой взгляд основная проблема - линейный поиск по массиву рыб при считывании каждого названия. Это совсем не оптимально. Я бы сделал так:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_map>
 
using namespace std;
typedef std::unordered_map< std::string, unsigned > Fishes;
 
int main()
{
    ifstream f( "input.txt" );
    Fishes result;
    
    unsigned a = 0;
    f >> a;
    for( unsigned i = 1; i <= a; ++i )
    {
        Fishes currentNote;
 
        unsigned b = 0;
        f >> b;
        for( unsigned j = 1; j <= b; ++j )
        {
            string name;
            f >> name;
 
            ++currentNote[ name ];
        }
        
        for( Fishes::const_iterator it = currentNote.begin(); it != currentNote.end(); ++it )
        {
            if( result[ it->first] < it->second )
            {
                result[ it->first] = it->second;
            }
        }
    }
    f.close();
 
    unsigned sum = 0;
    for( Fishes::const_iterator it = result.begin(); it != result.end(); ++it )
    {
        sum += it->second;
    }
    
    ofstream o( "output.txt" );
    o << sum;
    
    return 0;
}
А считает-то правильно.
Bohes_
4 / 4 / 0
Регистрация: 18.06.2013
Сообщений: 51
04.08.2013, 01:44  [ТС]     Ошибка в программе или алгоритме (Задача Океанариум) #3
Цитата Сообщение от Fyret Посмотреть сообщение
На мой взгляд основная проблема - линейный поиск по массиву рыб при считывании каждого названия.

А считает-то правильно.
Действительно, ваше решение проходит все тесты.

Я понимаю, что мое решение не оптимально, но при прохождении части тестов происходит WA, а не нехватка времени. Хотелось бы найти ошибку...хотя бы ради интереса и ОС.
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
04.08.2013, 02:13     Ошибка в программе или алгоритме (Задача Океанариум) #4
Цитата Сообщение от Bohes_ Посмотреть сообщение
при прохождении части тестов происходит WA, а не нехватка времени. Хотелось бы найти ошибку..
Мое решение отличается от первоначального Вашего только используемыми структурами данных. При большом числе видов рыб будет выход за пределы массива Aquarium. Я понимаю, откуда взялось число 51 в коде, но это неправильно

P.S. Что такое WA?
Bohes_
4 / 4 / 0
Регистрация: 18.06.2013
Сообщений: 51
04.08.2013, 02:36  [ТС]     Ошибка в программе или алгоритме (Задача Океанариум) #5
Wrong Answer

Добавлено через 4 минуты
Цитата Сообщение от Fyret Посмотреть сообщение
Я понимаю, откуда взялось число 51 в коде, но это неправильно
2500 также не спасают от тех же ошибок

Добавлено через 6 минут
В комментариях к ошибке написано что-то вроде:
51 instead of 50 in pos 1
49 instead of 305 in pos 1

Добавлено через 9 минут
Fyret, подскажите, что означает данный код:
Цитата Сообщение от Fyret Посмотреть сообщение
for( Fishes::const_iterator it = currentNote.begin(); it != currentNote.end(); ++it )
* * * * {
* * * * * * if( result[ it->first] < it->second )
* * * * * * {
* * * * * * * * result[ it->first] = it->second;
* * * * * * }
* * * * }
Что такое it ->first и it->second?
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
04.08.2013, 02:49     Ошибка в программе или алгоритме (Задача Океанариум) #6
можно еще так
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
30
31
32
33
34
35
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>
#include <algorithm>
 
int main()
{
    std::ifstream in("input.txt");
    std::ofstream out("output.txt");
    std::unordered_map<std::string, std::unordered_map<int, int>> fish;
    //                 ^                               ^    ^
    //                  название рыбы                  ^    ^
    //                                                 ^     количество этой рыбы на этом листке
    //                                                 номер листка
    std::string str;
    int i; in >> i;
    in.get();
    while (i--) {
        int n; in >> n; in.get();
        while (n-- && std::getline(in, str))
            ++fish[str][i];
    }
 
    int count = 0;
 
    for (auto &x : fish) {
        count += std::max_element(std::begin(x.second), std::end(x.second),
                    [](const std::pair<int, int> &lhs, const std::pair<int, int> &rhs) {
                            return lhs.second < rhs.second; } )->second;
    }
 
    out << count;
    return 0;
}
проходит?
diagon
04.08.2013, 02:52
  #7

Не по теме:

Цитата Сообщение от Fyret Посмотреть сообщение
#include <unordered_map>
Цитата Сообщение от Bohes_ Посмотреть сообщение
решение проходит все тесты.
А можно ссылку на тестирующую систему, понимающую с++11?

Olivеr
04.08.2013, 02:53
  #8

Не по теме:

Цитата Сообщение от diagon Посмотреть сообщение

Не по теме:



А можно ссылку на тестирующую систему, понимающую с++11?

на тимусе (acm.timus.ru) есть компилятор С++11

Bohes_
4 / 4 / 0
Регистрация: 18.06.2013
Сообщений: 51
04.08.2013, 02:54  [ТС]     Ошибка в программе или алгоритме (Задача Океанариум) #9
Цитата Сообщение от Olivеr Посмотреть сообщение
можно еще так
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
30
31
32
33
34
35
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>
#include <algorithm>
 
int main()
{
    std::ifstream in("input.txt");
    std::ofstream out("output.txt");
    std::unordered_map<std::string, std::unordered_map<int, int>> fish;
    //                 ^                               ^    ^
    //                  название рыбы                  ^    ^
    //                                                 ^     количество этой рыбы на этом листке
    //                                                 номер листка
    std::string str;
    int i; in >> i;
    in.get();
    while (i--) {
        int n; in >> n; in.get();
        while (n-- && std::getline(in, str))
            ++fish[str][i];
    }
 
    int count = 0;
 
    for (auto &x : fish) {
        count += std::max_element(std::begin(x.second), std::end(x.second),
                    [](const std::pair<int, int> &lhs, const std::pair<int, int> &rhs) {
                            return lhs.second < rhs.second; } )->second;
    }
 
    out << count;
    return 0;
}
проходит?
Нет, не компилируется даже
problem 580708 cached
test log:
Testing solution: 904393 for problem: 580708
> ..\spawner2\build-gcc\sp.exe "C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\cl.exe" /Ox /EHsc /nologo "AA.cpp" /Fe"AA.exe"
AA.cpp
AA.cpp(24) : error C2143: syntax error : missing ',' before ':'
AA.cpp(24) : error C2530: 'x' : references must be initialized
AA.cpp(24) : error C3531: 'x': a symbol whose type contains 'auto' must have an initializer
AA.cpp(24) : error C2143: syntax error : missing ';' before '{'
AA.cpp(25) : error C2228: left of '.second' must have class/struct/union
type is 'int'
AA.cpp(25) : error C2228: left of '.second' must have class/struct/union
type is 'int'
AA.cpp(27) : error C2780: '_FwdIt std::max_element(_FwdIt,_FwdIt)' : expects 2 arguments - 3 provided
C:\Program Files\Microsoft Visual Studio 10.0\VC\include\algorithm(5073) : see declaration of 'std::max_element'
AA.cpp(27) : error C2227: left of '->second' must point to class/struct/union/generic type
process exit code: 2
-> UserTime: 0.187201 s | MemoryUsed: 14.117188 Mb | Written: 0.231291 Mb
compilation error
Добавлено через 49 секунд
Цитата Сообщение от diagon Посмотреть сообщение

Не по теме:



А можно ссылку на тестирующую систему, понимающую с++11?

http://imcs.dvgu.ru/cats/ но здесь компилятор VC++ 2010
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
04.08.2013, 02:54     Ошибка в программе или алгоритме (Задача Океанариум) #10
Bohes_, ну а как же вы проверяли решение Fyret если его код тоже под C++11?
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
04.08.2013, 02:55     Ошибка в программе или алгоритме (Задача Океанариум) #11
Цитата Сообщение от Bohes_ Посмотреть сообщение
подскажите, что означает данный код:
Сообщение от Fyret
for( Fishes::const_iterator it = currentNote.begin(); it != currentNote.end(); ++it )
* * * * {
* * * * * * if( result[ it->first] < it->second )
* * * * * * {
* * * * * * * * result[ it->first] = it->second;
* * * * * * }
* * * * }
Что такое it ->first и it->second?
Это аналог сток 55-59 исходной программы. Проходим по все элементам ассоциативного массива currentNote, каждый элемент есть пара "название рыбы" - "ее количество". Обращаемся к ним it->first и it->second соответственно.
result[ it->first ] - число рыб it->first (это название) в итоговом массиве, если их меньше, чем записано в каком-то листке (это it->second), меняем итоговое значение на it->second. В общем, посмотрите документацию std::map или std::unordered_map.

В Вашей же программе проблема на 35 строке. Замените на
C++
1
f >> tempName;
и все должно заработать. Потому как getline(f,tempName) первый раз возвращает пустую строку.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2013, 03:05     Ошибка в программе или алгоритме (Задача Океанариум)
Еще ссылки по теме:

Ошибка в алгоритме перегрузки оператора присваивания C++
Ошибка компиляции в Алгоритме Брезенхэма C++
Странная ошибка в алгоритме заполнения массива из файла C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Bohes_
4 / 4 / 0
Регистрация: 18.06.2013
Сообщений: 51
04.08.2013, 03:05  [ТС]     Ошибка в программе или алгоритме (Задача Океанариум) #12
Цитата Сообщение от Olivеr Посмотреть сообщение
Bohes_, ну а как же вы проверяли решение Fyret если его код тоже под C++11?
Никак, но первый код прошел, а второй--нет

Добавлено через 6 минут
Fyret, спасибо. Теперь работает нормально, но мою реализацию алгоритма нужно менять -- не прохожу по времени
Yandex
Объявления
04.08.2013, 03:05     Ошибка в программе или алгоритме (Задача Океанариум)
Ответ Создать тему
Опции темы

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