e-olymp 7847. Кількість різних елементів

12/01/2020 by Андрей Мартынюк

Задача

Дано масив з [latex]N[/latex] цілих чисел. Визначте, скільки в цьому масиві різних елементів.

Вхідні дані

В першому рядку записано число [latex]N[/latex]. В наступному рядку записано [latex]N[/latex] цілих чисел. Всі числа за модулем не перевищують [latex]100[/latex].

Вихідні дані

Кількість різних елементів в масиві.

Тести

№	Вхідні дані	Вихідні дані
1.	7 3 5 -7 7 5 -9 -4	6
2.	5 1 25 59 75 100	5
3.	6 1 2 3 1 2 4	4

Код 1

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
                break;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

for (int i = 0; i < n; i++)

{

cin >> a[i];

}

int diffNum = 0;

for (int i = 0; i < n; i++)

{

bool newNum = true;

for (int j = 0; j < i; j++)

{

if (a[j] == a[i])

{

newNum = false;

break;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Код 1(without break)

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) { cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i && a[i-1] != a[j]; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

for (int i = 0; i < n; i++) { cin >> a[i];

}

int diffNum = 0;

for (int i = 0; i < n; i++)

{

bool newNum = true;

for (int j = 0; j < i && a[i-1] != a[j]; j++)

{

if (a[j] == a[i])

{

newNum = false;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Решение

Ставим отметку числу как будто видим его впервые.
Далее задача пройти по всем предыдущим числам и проверить не встретится ли такое же число.
Если встретится, то отметку снимаем, а пройдя по всем предыдущим числам так и не встретив числа равного текущему, значит «видим его впервые» и отметка поставлена справедливо.
Считаем количество отметок.

Ссылки

Код 2

#include <iostream>
using namespace std;
#include 
int main() {
    vector a(202, false);
    int n, diffNum, curVal;
    cin >> n;
    diffNum = n;
    for(int i = 0; i < n; i++)
    {
        cin >> curVal;
        if(a[curVal + 100]) 
        {
            diffNum--;
        }
        else 
        {
            a[curVal + 100] = true;
        }
    }
    cout << diffNum << endl;
    return 0;
}

#include <iostream>

using namespace std;

#include

int main() {

vector a(202, false);

int n, diffNum, curVal;

cin >> n;

diffNum = n;

for(int i = 0; i < n; i++)

{

cin >> curVal;

if(a[curVal + 100])

{

diffNum--;

}

else

{

a[curVal + 100] = true;

}

cout << diffNum << endl;

return 0;

}

Решение

Сначала, предположим, что все числа разные. Т.е. количество различных чисел равно [latex]n.[/latex] Далее в цикле for отметим читаем числа из потока и отмечаем в векторе vector<bool> a, что число встретилось. Встретив число ранее уже отмеченное уменьшаем счетчик различных чисел.

Ссылки

Related Images:

Похожее

9 thoughts on “e-olymp 7847. Кількість різних елементів”

Мазурок Игорь Евгеньевич says: 14/01/2020 at 21:49
- Пожалуйста, сохраняйте в работе язык оригинала.
- Используйте для заголовков H1 и H2 для подзаголовков. Если они есть.
- Меток нет.
- Категория не указана.
- Зачем такое количество пустых строк? Ну, в коде — понятно, а по тексту их быть не должно. Если нужен вертикальный отступ, то в заголовках он есть.
- Не стоит использовать буквы кириллицы в адресе публикации.
- В условии не сказано сколько может быть чисел. С чего Вы взяли, что массива на 101 элемент будет достаточно? Его и недостаточно.
- Вы не знаете сколько будет чисел, но знаете что сами числа не меньше чем -100 и не больше чем 100. Сколько же среди них может быть различных? не больше чем 201. Вот такой массив создать можно. Например массив логических значений — встретилось ли такое число или нет.
Войдите, чтобы ответить
- Мазурок Игорь Евгеньевич says: 19/01/2020 at 22:51
  
  Еще раз повторяю. Во входном потоке может быть СКОЛЬ УГОДНО МНОГО чисел. Автор не делает ограничений на переменную $N$. Вы прошлый раз предположили, что $N$ не больше 100. Сейчас — 201. Я, конечно добавлю в какой-нибудь тест 1000 нулей, но не проще ли прочитать мой предыдущий комментарий внимательно?
  Если задачу на 201 различное число решить сразу сложно, предлагаю сначала решить следующую:
  Маше на Новый Год подарили пакет с некоторым количеством конфет. Известно, что мамин профком закупил для подарков шоколадные, карамельные и леденцы. Как Маше узнать сколько из этих трёх типов конфет встретились в ее пакете? При этом известно, что Маша еще маленькая и умеет только есть конфеты и считать до трёх.
- Андрей Мартынюк says: 06/02/2020 at 14:37
  
  Исправил.
- Мазурок Игорь Евгеньевич says: 08/02/2020 at 19:06
  
  Нет. Совсем даже не исправил.
  Вы опять предлагаете решение квадратичной сложностью. Нельзя запоминать все элементы и сравнивать каждый с каждым. Вам нужно полностью поменять концепцию.
  Видимо на конфетах плохо получилось объяснить или Вы эту часть моего моего комментария проигнорировали.
  Попытка №2. Решите задачу.
  Вам в течение часа с невероятной скоростью сообщают какие-то цифры. В конце этого часа Вам необходимо мгновенно ответить на вопрос — какие цифры ни разу не встретились. При этом у вас нет ни бумаги ни карандаша. Есть только две руки с пятью гибкими пальцами на каждой.
  P.S. Кажется теперь Вам не увернуться и придется изобрести правильный алгоритм
Мазурок Игорь Евгеньевич says: 08/02/2020 at 19:08

Нет. Совсем даже не исправил.
Вы опять предлагаете решение квадратичной сложностью. Нельзя запоминать все элементы и сравнивать каждый с каждым. Вам нужно полностью поменять концепцию.
Видимо на конфетах плохо получилось объяснить или Вы эту часть моего моего комментария проигнорировали.
Попытка №2. Решите задачу.
Вам в течение часа с невероятной скоростью сообщают какие-то цифры. В конце этого часа Вам необходимо мгновенно ответить на вопрос — какие цифры ни разу не встретились. При этом у вас нет ни бумаги ни карандаша. Есть только две руки с пятью гибкими пальцами на каждой.
P.S. Кажется теперь Вам не увернуться и придется изобрести правильный алгоритм

Войдите, чтобы ответить
- Андрей Мартынюк says: 14/03/2020 at 17:05
  
  Добавил ещё один вариант решения.
Мазурок Игорь Евгеньевич says: 30/03/2020 at 19:01
1. В условии переменные оформите в laTeX.
2. Подумайте, как избавиться от brake в первом коде.
3. 6-я строка второго кода. Вы хотели инициализировать ВЕСЬ массив. Но ваш способ задает значение первого элемента массива. Остальные получают случайные значения. При первом запуске все вероятно будет хорошо, но это недопустимая практика. Хотите автоматическую инициализацию нулями — определите массив вне функций. Но само решение мне нравится. Правильный подход.
  И есть вопрос. С какой целью Вы так сильно растягиваете код пустыми строчками? Мне кажется его не очень удобно читать. а вам?
Войдите, чтобы ответить
- Андрей Мартынюк says: 01/06/2020 at 21:43
  
  Исправил.

Всё, сдаюсь. Исправил последний код, завел его на ideone.com, поставил ссылку на него, написал объяснение, удалил все nbsp. Конечно, логично было бы все писать на украинском, раз начали на украинском. Но, нет, переводить не буду.
Зачтено, молодец. Марафон длинною в полгода успешно завершен.

P.S. Я всего-то надеялся увидеть дюжину строчек в типа

#include <iostream>
bool f[201];
int main() {
    int n, c = 0;
    std::cin >> n;
    for (int x, i = 0; i < n; i++) {
        std::cin >> x;
        if (!f[x + 100]) c++;
        f[x + 100] = true;
    }
    std::cout << c;
}

#include <iostream>

bool f[201];

int main() {

int n, c = 0;

std::cin >> n;

for (int x, i = 0; i < n; i++) {

std::cin >> x;

if (!f[x + 100]) c++;

f[x + 100] = true;

}

std::cout << c;

}

Добавить комментарий Отменить ответ

Для отправки комментария вам необходимо авторизоваться.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

e-olymp 7847. Кількість різних елементів

Задача

Вхідні дані

Вихідні дані

Тести

Код 1

Код 1(without break)

Решение

Ссылки

Код 2

Решение

Ссылки

Related Images:

Понравилось это:

Похожее

9 thoughts on “e-olymp 7847. Кількість різних елементів”

Добавить комментарий Отменить ответ

Задача

Вхідні дані

Вихідні дані

Тести

Код 1

Код 1(without break)

Решение

Ссылки

Код 2

Решение

Ссылки

Related Images:

Поделиться ссылкой:

Понравилось это:

Похожее

9 thoughts on “e-olymp 7847. Кількість різних елементів”

Добавить комментарий Отменить ответ