Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
18 / 18 / 9
Регистрация: 12.10.2014
Сообщений: 100

Задача про кубики

22.04.2016, 18:35. Показов 2816. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть столбики указанных размеров. Задание такое: Какое наименьшое количество перекладываний необходимо сделать, что бы высота 2х любых столбиков не отличалась больше чем на 1. Кроме того, за один раз можно перекладывать только один кубик из любого в столбика в соседний.
Входные данные (в первый элемент - количество столбиков, последующие - их высота):
5
3 4 8 2 5
Выходные данные (одно число - наименьшее количество перекладываний):
4

С чего стоит начать решение это задачи? Мне не сколько код необходим(сам могу написать), сколько алгоритм решения, с чем я прошу вас помочь.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
22.04.2016, 18:35
Ответы с готовыми решениями:

Ваня и кубики. Олимпиадная задача
Ване на день рождения подарили n кубиков. Он с друзьями решил построить из них пирамиду. Ваня хочет построить пирамиду следующим образом:...

Задача про кубики
Условие: Имеется N кубиков. Стеной будем считать несколько столбиков из этих кубиков, расположенных рядом. Обозначим h - высотой i-го...

Задача про кубики и лесенки или Динамика с двумя параметрами.
Думал я думал, так и не придумал как реализовать эту задачу, даже нет идей... Родители подарили мальчику Пете очень много одинаковых...

11
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13184 / 6820 / 1821
Регистрация: 18.10.2014
Сообщений: 17,260
22.04.2016, 18:49
Цитата Сообщение от PaT TEma Посмотреть сообщение
что бы высота 2х любых столбиков не отличалась больше чем на 1
Ну то есть все кубики - одинаковы.

Так а "уничтожать" столбики можно или нет? Т.е. если я перемещу все кубики из одного столбика в другой, означает ли это что исходный столбик исчез? Или это означает, что столбик остался, но имеет высоту 0?
0
18 / 18 / 9
Регистрация: 12.10.2014
Сообщений: 100
22.04.2016, 18:54  [ТС]
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Так а "уничтожать" столбики можно или нет? Т.е. если я перемещу все кубики из одного столбика в другой, означает ли это что исходный столбик исчез? Или это означает, что столбик остался, но имеет высоту 0?
это будет означать, что размер столбика равен 0

Добавлено через 2 минуты
Вот полное условие:
На День рождения своего племянника Петрика Степан подарил ему набор кубиков. Петрик
тут же стал строить из кубиков забор, однако столбики у Пети выходили разной высоты. Степана
заинтересовал вопрос: "Какое наименьшее количество переложений можно сделать, чтобы высота любых
двух столбиков отличалась не более чем на один кубик. Кроме того за один раз можно переводить
только один кубик из произвольного колонки на рядом расположен.
Входные данные
В первой строке входного файла записано число N (1 ≤ N ≤ 1000) - количество столбиков с
кубиками в Петрика. Вторая строка содержит N целых чисел - высоту каждого столбика (в кубиках).
Все числа не превышают 106
.
Выходные данные
В выходной файл необходимо вывести одно единственное число - наименьшее количество переложений
кубиков, в результате которых высота любых двух столбиков не будет отличаться более чем на один
кубик.
пример:
Ввод:
5
3 4 8 2 5
Вывод:
4

Объяснение: Сделать два перекладывание из колонки №3 в столбик №4. результат -
3 4 6 4 5. Затем переложить кубик из колонки №2 в столбик №1. Результат - 4 3 6 4 5 И напоследок
переместить кубик из колонки №3 в столбик №2. Результат - 4 4 5 4 5.
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
22.04.2016, 20:59
PaT TEma,
Цитата Сообщение от PaT TEma Посмотреть сообщение
Ввод:
5
3 4 8 2 5
Вывод:
4
Объяснение: Сделать два перекладывание из колонки №3 в столбик №4. результат -
3 4 6 4 5. Затем переложить кубик из колонки №2 в столбик №1. Результат - 4 3 6 4 5 И напоследок
переместить кубик из колонки №3 в столбик №2. Результат - 4 4 5 4 5.
Результат должен быть 3.
При 3 4 6 4 5 надо переложить с к. №3 в к. №1 - и результат будет тот же 4 4 5 4 5.

Ну это так, к слову.
Реализация должна быть такой: на каждом ходу перекладывается один кубик из самого высокого столбца на самый низкий пока не будет выполнено условие.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13184 / 6820 / 1821
Регистрация: 18.10.2014
Сообщений: 17,260
22.04.2016, 21:12
Цитата Сообщение от RQdan Посмотреть сообщение
Результат должен быть 3. При 3 4 6 4 5 надо переложить с к. №3 в к. №1 - и результат будет тот же 4 4 5 4 5.
Так нельзя. Перекладывать кубики разрешается только на рядом расположенные столбики. Именно поэтому в примере ответ 4, а не 3.

Если бы перекладывать разрешалось откуда угодно куда угодно, то задача была бы совсем тривиальной.

Цитата Сообщение от RQdan Посмотреть сообщение
Реализация должна быть такой: на каждом ходу перекладывается один кубик из самого высокого столбца на самый низкий пока не будет выполнено условие.
Не соответствует условию задачи.
1
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
22.04.2016, 21:44
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Перекладывать кубики разрешается только на рядом расположенные столбики
Да, что-то пропустил такое.
Эх, уже сделал код на неправильное условие (.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13184 / 6820 / 1821
Регистрация: 18.10.2014
Сообщений: 17,260
22.04.2016, 22:13
Понятно, что привести столбики в правильное состояние - это привести все высоты в диапазон [Hmin, Hmax], где K - общее количество кубиков, Hmin = floor(K/N), Hmax = ceil(K/N).

Однако жадная стратегия "берем слишком высокий и сбрасываем в ближайший < Hmax, берем слишком низкий и дополняем из ближайшего > Hmin" не всегда дает оптимальный результат...
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
22.04.2016, 23:42
PaT TEma, прошу сильно не бить, но единственное, что приходит в голову - перебор через рекурсию.
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
 
void Equalizer(int*, int , int, int, int, int&);
bool Check(int*, int);
 
void main() {
    int n, minAccept, maxAccept, sum = 0;
    int count = INT_MAX;
    int* actualMas;
 
    std::cin >> n;
    actualMas = new int[n];
 
    for(int i = 0; i < n; i++) {
        std::cin >> actualMas[i];
        sum += actualMas[i];
    }
    minAccept = sum / n;
    maxAccept = minAccept + !!(sum % n);
 
    Equalizer(actualMas, n, minAccept, maxAccept, 0, count);
 
    std::cout << count << std::endl;
}
 
void Equalizer(int* mas, int n, int minAccept, int maxAccept, int curCount, int& count) {
    if(Check(mas, n)) {
        count = curCount;
        return;
    }
    for(int i = 0; i < n; i++) {
        if(mas[i] > maxAccept) {
            int j = 1;
            while((i - j >= 0 || i + j < n) && curCount + j < count) {
                if(i - j >= 0 && mas[i - j] < maxAccept) {
                    mas[i]--;
                    mas[i - j]++;
                    Equalizer(mas, n, minAccept, maxAccept, curCount + j, count);
                    mas[i]++;
                    mas[i - j]--;
                }
                if(i + j < n && mas[i + j] < maxAccept) {
                    mas[i]--;
                    mas[i + j]++;
                    Equalizer(mas, n, minAccept, maxAccept, curCount + j, count);
                    mas[i]++;
                    mas[i + j]--;
                }
                j++;
            }           
        }
        if(mas[i] < minAccept) {
            int j = 1;
            while((i - j >= 0 || i + j < n) && curCount + j < count) {
                if(i - j >= 0 && mas[i - j] > minAccept) {
                    mas[i]++;
                    mas[i - j]--;
                    Equalizer(mas, n, minAccept, maxAccept, curCount + j, count);
                    mas[i]--;
                    mas[i - j]++;
                }
                if(i + j < n && mas[i + j] > minAccept) {
                    mas[i]++;
                    mas[i + j]--;
                    Equalizer(mas, n, minAccept, maxAccept, curCount + j, count);
                    mas[i]--;
                    mas[i + j]++;
                }
                j++;
            }
        }
    }
}
 
bool Check(int* mas, int n) {
    int min = 0, max = 0;
    for(int i = 1; i < n; i++) {
        if(mas[min] > mas[i]) min = i;
        if(mas[max] < mas[i]) max = i;
    }
    if(mas[max] - mas[min] > 1) return false;
    return true;
}
1
techpriest
 Аватар для Mirmik
634 / 213 / 57
Регистрация: 27.02.2014
Сообщений: 1,180
22.04.2016, 23:57
Нда... Я за перебор с отсевом заведомо ухудшающих ситуацию вариантов и вариантов, длительность которых больше чем самого быстрого найденного.
0
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
23.04.2016, 00:12
Цитата Сообщение от Mirmik Посмотреть сообщение
Я за перебор с отсевом заведомо ухудшающих ситуацию вариантов и вариантов, длительность которых больше чем самого быстрого найденного.
Вроде так и сделал.
Разве что еще где можно улучшить код. Или проще написать.
0
18 / 18 / 9
Регистрация: 12.10.2014
Сообщений: 100
23.04.2016, 00:29  [ТС]
RQdan, всё отлично, осталось оптимизировать. А то сильно долго выполняется. Мне нужно не больше 1сек. Попробую что то сделать
0
techpriest
 Аватар для Mirmik
634 / 213 / 57
Регистрация: 27.02.2014
Сообщений: 1,180
23.04.2016, 09:58
Вот. У меня теперь быстро.
Можно расскометировать работу с векторами. Станет медленно, но можно будет просмотреть вариант.
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// ConsoleApplication1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
 
struct move;
 
#define CRCT_MOVES 8
#define COLUMNS 5
#define UPPERSIDE 1
#define DOWNSIDE 0
 
int columns[COLUMNS] = {3,2,11,4,2};
 
void print_columns()
{
    for (int i = 0; i < COLUMNS; ++i)
    {
        std::cout << columns[i];
        std::cout << ((i != COLUMNS - 1) ? ":" : "");
    };
};
 
void print_columns(int step)
{
    std::cout << "step " << step << ": ";
    print_columns();
};
 
float Hmedian;
int Hmin;
int Hmax;
float FHmin;
float FHmax;
 
int minimum_steps = 0x10;
std::vector<move> minimum_chain;
 
bool side(int column)
{
    if ((FHmax + FHmin) / 2 < columns[column]) return UPPERSIDE;
    else return DOWNSIDE;
};
 
bool quality_move(int dst_column, int src_column)
{
    if (columns[src_column] == 0) return 0;
    if (side(src_column) == UPPERSIDE)
    {
        return columns[src_column] >= columns[dst_column];
    }
    else
    {
        return columns[src_column] <= columns[dst_column];
    };
};
 
bool in_range(int column)
{
    return columns[column] == Hmin || columns[column] == Hmax;
};
 
bool all_in_range()
{
    for (int i = 0; i < 5; ++i)
    {
        if (!in_range(i)) return false;
    };
    return true;
};
 
std::vector<move> move_chain;
 
struct move
{
    int dst;
    int src;
    move(int _dst, int _src) : dst(_dst), src(_src) {};
    move() {};
 
    void do_move()
    {
        --columns[src];
        ++columns[dst];
        //move_chain.push_back(*this);
    };
 
    void un_move()
    {
        ++columns[src];
        --columns[dst];
        //move_chain.pop_back();
    };
 
    bool quality()
    {
        return quality_move(dst, src);
    };
};
 
move correct_moves[CRCT_MOVES]
{
    move(0,1),
    move(1,2),
    move(2,3),
    move(3,4),
    move(4,3),
    move(3,2),
    move(2,1),
    move(1,0)
};
 
void step_of_recursion(int current_step)
{
    move mv;
    ++current_step;
    for (int i = 0; i < CRCT_MOVES; ++i)
    {
        mv = correct_moves[i];
        if (mv.quality())
        {
            mv.do_move();
            if (all_in_range())
            {
                minimum_steps = current_step;
                //minimum_chain = move_chain;
                printf("FIND!!!%d\r\n",current_step);
                mv.un_move();
                return;
            };
 
            if (current_step + 1 < minimum_steps)
                step_of_recursion(current_step);
            mv.un_move();
        };
    };
};
 
int main()
{
 
    for (int i = 0; i < 5; ++i)
        Hmedian += columns[i]; 
    Hmedian /= 5;
    Hmin = Hmedian;
    Hmax = Hmedian + 1;
    FHmin = Hmin;
    FHmax = Hmax;
 
    printf("median: %f\r\n", Hmedian);
    printf("Hmin: %d\r\n", Hmin);
    printf("Hmax: %d\r\n", Hmax);
 
 
    
    step_of_recursion(0);
    
    //int step = 0;
    //print_columns(step);
    //std::cout << "\r\n";
    //for_each(minimum_chain.begin(), minimum_chain.end(), [&step](move& m) 
    //{
    //  step++;
    //  m.do_move();
    //  print_columns(step); 
    //  std::cout << " dst:" << m.dst << " src:" << m.src << "\r\n";
    //});
 
    printf("THATS_ALL!!!\r\n");
    getchar();
    return 0;
}
Добавлено через 1 минуту
Проблемма алгоритма в том, что его скорость зависит от начальной заданной глубины поиска.

Добавлено через 7 минут
Попробовал увеличивать число допустимых ходов по одному в цикле.
Тобишь... Не нашла при такой глубине, ищи глубже.

В общем... Ходов так до 10 -мгновенно.... Дальше - комбинаторный взрыв.

Добавлено через 5 минут
Скорее всего, всё-таки жадность нужна .
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
23.04.2016, 09:58
Помогаю со студенческими работами здесь

Про кубики
Всем привет. Какое из 2х событий более вероятно: А - при бросании четырех игральных костей выпадает хотя бы одна единица или Б - при 24...

3 задачи: про цветные шарики, окрашенные кубики и делители числа.
помогите решить задачи, пожалуйста. 1. В я щике 4 голубых и 5 красных шаров. из ящика на угад вынимают 2 шара. Найти вероятность того,...

Задача Кубики
Pascal ABC Вообще не могу понять(( Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему...

Задача C. Кубики
Когда маша начала учить английские слова, родители подарили ей набор кубиков с буквами английского алфавита. Изначально в наборе было...

Ускорить код.Задача кубики
Всем привет. Решил задачу,но не проходит по скорости.Изменял около 5 раз, и оптимизировал максимум на что был способен(с подглядываниями в...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
Использование значений реквизитов справочника в документе, с определенными условиями и правами
Maks 07.04.2026
1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
Уведомление о неверно выбранном значении справочника
Maks 06.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru