Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.57/21: Рейтинг темы: голосов - 21, средняя оценка - 4.57
 Аватар для Kam_1995
34 / 34 / 22
Регистрация: 23.03.2013
Сообщений: 176

Найти минимальное количество шариков, которое необходимо перекрасить, чтобы все шарики были одного цвета

06.06.2015, 19:04. Показов 4516. Ответов 8

Студворк — интернет-сервис помощи студентам
Написал код для одной задачи. Ответ выдает он вроде правильный. Но на сайте при тестировании моего алгоритма, он проходит тест на 31% (4/13). Подскажите пожалуйста, какие могут быть вводные данные, для которых мой алгоритм не работоспособен; и если есть ошибка, то где она?

---------------------------------------------------------------
Задача:

Шарики

У продавца воздушных шариков есть N шаров. Каждый из них имеет некоторый цвет. Однако совсем недавно Три Толстяка издали указ, разрешающий торговать шариками какого-то одного цвета. Чтобы не нарушать закон, но при этом и не потерять прибыль, продавец решил перекрасить некоторые из своих шариков.

Напишите программу для определения минимального количества перекрашиваний.

Входные данные

В первой строке входного файла задано количество шариков N (1 ≤ N ≤ 100000). Вторая строка состоит из N целых чисел, в пределах от 1 до 9, определяющие цвета шариков (1 - синий, 2 - зеленый, 3 - голубой, 4 - красный, 5 - розовый, 6 - желтый, 7 - серый, 8 - черный, 9 - белый).

Выходные данные

В единственную строку выходного файла выведите минимальное количество шариков, которое необходимо перекрасить, чтобы все шарики были одного цвета.

-----------------------------------------------------------------
Пример:

Входные данные
4
3 1 2 1

Выходные данные
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
#include "stdafx.h";
#include <iostream>;
using namespace std;
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int n;
    cin >> n;
    int a[n];
    for (int i=0;i<n;i++) cin >> a[i];
 
    int j=1,i=0,max,m=0;
    
    while (j<10)
    {
    for (i=0;i<n;i++)
    {
        if (a[i]==j) m++;
    }
    if (i==0) max=m;
    else if (max<m) max=m;
    m=0;
    j++;
    }
    cout << n-max <<'\n';
    
    system("pause");
    return 0;
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
06.06.2015, 19:04
Ответы с готовыми решениями:

Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n гривен
В банкомате имеются в достаточном количестве купюры номиналом 10, 20, 50, 100, 200 и 500 гривен. Найти минимальное количество купюр,...

Найти минимальное количество указаний карты, которое нужно выполнить, чтобы прийти к кладу
Мы находимся на острове, на котором закопан клад. Мы находимся в точке с координатами (0, 0) и смотрим на север. Нам известно, где закопан...

Найти минимальное число монет, которые нужно перевернуть, чтобы все монеты были повернуты вверх одной и той же стороной
На столе лежат n монеток. Некоторые из них лежат вверх решкой, а некоторые – гербом. Определите минимальное число монеток, которые нужно...

8
67 / 67 / 72
Регистрация: 10.04.2015
Сообщений: 281
06.06.2015, 23:29
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
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    int n;
    ifstream f("file.txt");
    if(f.is_open()) f>>n;
    int *ball_color = new int[n];
  
    int i = 0;
    while(f.good())
    {
        i++;
        f>>ball_color[i]; //считываем цвета шариков
    }
    f.close();
     int mas[10] = {0};//количество шариков каждого цвета
     
    for (int i=0;i<n+1;i++)  
        for(int j = 1;j<10;j++) 
            if(ball_color[i]==j){ mas[j]++; break;} //заносим в массив количество шариков каждого цвета
    
    int max = 0;        
    for(int j = 1;j<10;j++)  
        if(mas[j]>max) max = mas[j]; //находим максимальный цвет
    
    cout<<n-max;
 
    delete [] ball_color; 
return 0;

Не по теме:

int n;
cin >> n;
int a[n];
переменная в размерности массива
if (i==0) max=m;
else if (max<m) max=m;
Условие, однако=-O

1
 Аватар для dcStep
41 / 41 / 36
Регистрация: 13.04.2015
Сообщений: 83
07.06.2015, 01:07
Цитата Сообщение от Kam_1995 Посмотреть сообщение
для которых мой алгоритм не работоспособен
Что, если надо будет считать 2.1 млн чисел? У тебя размер массива зависит от количества считываемых чисел, это плохо.
Создавай массив константного размера 9 (так как всего 9 цветов) каждый цвет будет соответствовать индексу массива, и просто увеличиваешь кол-во на +1 при считывании цвета.

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
#include <iostream>
 
#define SIZE 9
 
int main() {
    int N, color;
    int array[SIZE] = {0};
    int max = 0;
 
    std::cin >> N;
 
    for ( int i = 0; i < N; i++ ) {
        std::cin >> color;
        array[color-1] += 1;
    }
 
    for ( int i = 0; i < N; i++ ) {
        if ( max < array[i] ) {
            max = array[i];
        }
    }
 
    std::cout << N - max << std::endl;
 
    return 0;
}
0
 Аватар для Kam_1995
34 / 34 / 22
Регистрация: 23.03.2013
Сообщений: 176
07.06.2015, 01:30  [ТС]
Цитата Сообщение от mr_mczakenberg Посмотреть сообщение
Код C++
Спасибо за помощь! Позаимствовал у вас только метод нахождения одинаковых цифр и сайт полностью засчитал ответ(13/13). Можете ли сказать, так чем отличаются наши методы. Мы вроде делаем практически одну и ту же вещь. Что я не учел в своем алгоритме?

--------------------------------------------------------
Получилось вот это:

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
#include "stdafx.h";
#include <iostream>;
using namespace std;
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int n;
    cin >> n;
    int a[n];
    for (int i=0;i<n;i++) cin >> a[i];
 
 
 int mas[10] = {0};//количество шариков каждого цвета
     
    for (int i=0;i<n+1;i++)  
        for(int j = 1;j<10;j++) 
            if(a[i]==j){ mas[j]++; break;} //заносим в массив количество шариков каждого цвета
    
    int max = 0;        
    for(int j = 1;j<10;j++)  
        if(mas[j]>max) max = mas[j]; //находим максимальный цвет
int ballon;
ballon=n-max;
 
    cout<<ballon<<'\n';
 
    
    system("pause");
    return 0;
}
Добавлено через 12 минут
Цитата Сообщение от dcStep Посмотреть сообщение
Создавай массив константного размера 9
Идея отличная и на взгляд экономная, но сайт опять взялся за свое. Попробовал ваш алгортим: 3/13 - засчитано, 3/13 - ошибка выполнения, а остальные - неверны. Я замечаю, что, чем лучше идея алгоритма, тем он хуже проходит тест. Я хочу разобраться: почему ранее мною указанный алгоритм он засчитал полностью, а ваш - нет.
0
 Аватар для dcStep
41 / 41 / 36
Регистрация: 13.04.2015
Сообщений: 83
07.06.2015, 01:33
Цитата Сообщение от dcStep Посмотреть сообщение
C++
1
for ( int i = 0; i < N; i++ )
опечатался, моя 17 строка должна иметь вид:
C++
1
for ( int i = 0; i < SIZE; i++ )
1
 Аватар для Kam_1995
34 / 34 / 22
Регистрация: 23.03.2013
Сообщений: 176
07.06.2015, 12:01  [ТС]
Цитата Сообщение от dcStep Посмотреть сообщение
опечатался
Да, вставил: полностью засчитал (13/13). Так можете ли сказать, чем мой алгоритм хуже. Я же ведь тоже считаю кол-во одинаковых цифр. Только методы расчета различаются.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
07.06.2015, 12:12
[удалить]
0
67 / 67 / 72
Регистрация: 10.04.2015
Сообщений: 281
07.06.2015, 13:01
C++
1
if (i==0) max=m;
ALERT!
Пер. i всегда равна нулю, т.к. она не меняется в программе. ( в цикле участвует совсем другая переменная i);
а значит max = m, даже если m<max.
1
 Аватар для Kam_1995
34 / 34 / 22
Регистрация: 23.03.2013
Сообщений: 176
07.06.2015, 13:51  [ТС]
Цитата Сообщение от mr_mczakenberg Посмотреть сообщение
ALERT!
Исправил, полностью засчитал. Спасибо!)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
07.06.2015, 13:51
Помогаю со студенческими работами здесь

Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной
Добрый вечер, наткнулся на простую задачу - сложность всего лишь 8%. Её нужно решить с использованием цикла for. Задачу, я, конечно, решил,...

Минимальное число монеток, которые нужно перевернуть, чтобы все монетки были повернуты вверх одной стороной
На столе лежат n монеток. Некоторые из них лежат вверх решкой, а некоторые – гербом. Определите минимальное число монеток, которые нужно...

Определить минимальное количество монет, которое должно находиться в автомате, чтобы всем хватило сдачи
Здравствуйте. Не первый раз создаю тему об олимпиадных задачах , думаю, и не последнюю)) Возникла проблема со следующей задачей: ...

Определить минимальное количество листов, которое должно быть в книге, чтобы редкие ингредиенты не пострадали
1935. Слёзы утопленников Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ Гадалка Тиа Дальма, давняя подруга капитана Джека...

Определить, какого цвета шарики есть хотя бы у одного ребенка
На детском празднике каждому ребенку был подарен воздушный шарик (&quot;с&quot; - синий, &quot;г&quot; - голубой, &quot;з&quot; - зе-леный и т.д.)....


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru