Какой алгоритм применить к этой задачи?

@tyitoite · Регистрация: 11.08.2020

Студворк — интернет-сервис помощи студентам

Привет всем. Недавно наткнулся на задачу с Муниципального этапа ВсОШ. Вот ее условие:

-----------------------------------------------------------------------------------------------------------------------------------------

В Берляндии в обиходе монеты достоинством 1, 2, 3, 4, 5 и 6 бурлей, толщина всех монет одинаковая. У Васи есть неограниченное количество монет каждого достоинства. Вася и Петя играют в следующую игру: Петя загадывает сумму
S, которую необходимо набрать, и сообщает Васе число N — количество монет, которые Вася может использовать. После этого Вася должен подобрать такие N монет, чтобы их сумма равнялась ровно S бурлям. Далее все N монет раскладываются в 6 стопок по номиналам.

Петя решил усложнить игру и предложил Васе найти среди всех возможных вариантов такой, что высота самой высокой стопки монет будет максимальной. Толщина всех монет одинаковая, а значит на высоту стопки влияет только количество монет. С усложнённой версией игры у Васи возникли трудности, и он просит вас решить поставленную задачу.

ФОРМАТ ВВОДА:
В единственной строке подается число n, в следующих n строках вводится S и N

ФОРМАТ ВЫВОДА:
Вывести n строк - ответ для каждого S и N
Тесты:

INPUT:

1
30 6

OUTPUT:

0 0 0 0 6 0

написал код, но работает только на 56/100 баллов.

не подскажите какой алгоритм применить к данной задаче. Может воспользоваться Динамическим Программированием?

скиньте код и объяснение, если не сложно

спасибо всем заранее

@LegionK · 11.08.2020, 17:58

Можно ли увидеть систему проверки, куда можно код отправить и почитать оригинал условия?

@tyitoite · 11.08.2020, 18:45 **[ТС]**

ссылка https://imcs.dvfu.ru/cats/stat... 63151.html
что бы проверить решение нужно принять виртуальное участие в соревновании.

@LegionK · 11.08.2020, 19:43

Не знаю, можно было дп написать, конечно :
dp i j a - можно ли набрать сумму i из j количества монет, если брать монеты из первых a чисел (a = 1,2,3...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
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
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
 
    int t;
    cin >> t;
 
    for(int z = 0;z<t;++z){
 
        int n,m;
        cin >> n >> m;
 
        vector<int>ans;
 
        int ma = 0;
 
        for(int one = 0;;++one){            ///////////////
 
            if(one*1 > n || one > m)break;
 
            for(int two = 0;;++two){                //////////////
 
                if((two*2+one*1) > n || (two+one) > m)break;
 
                for(int three = 0;;++three){
 
                    if((three*3+one*1+two*2) > n || (three+one+two) > m)break;     ////////////
 
                    for(int four = 0;;++four){                      ///////////
 
                        if((four*4+three*3+one*1+two*2) > n || (four+one+two+three) > m)break;
 
                        for(int five = 0;;++five){                      ///////////
 
                            if((five*5+four*4+three*3+one*1+two*2) > n || (four+one+two+three+five) > m)break;
 
                            for(int six = 0;;++six){                        ///////////
 
                                //cout << one << two << three << four << five << six << "\n";
 
                                if((six*6+five*5+four*4+three*3+one*1+two*2) > n || (four+one+two+three+five+six) > m)break;
 
                                if((six*6+five*5+four*4+three*3+one*1+two*2) != n || (four+one+two+three+five+six) != m)continue;;
 
                                vector<int>temp = {one,two,three,four,five,six};
 
                                int var = *max_element(temp.begin(),temp.end());
 
                                if(var > ma){
                                    ma = var;
                                    ans = temp;
                                }
 
                            }
 
                        }
 
 
 
                    }
 
                }
 
            }
 
        }
 
        for(int i = 0;i<ans.size();++i)cout << ans[i] << ' ';
        cout << "\n";
 
    }
 
 
    return 0;
}

@vantfiles · 11.08.2020, 21:18

вы свое решение не привели, вы примерно так решали? :

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
#include <iostream>
#include <conio.h>
 
int main() 
{
  int mx1, mx2, mx3, mx4, mx5, mx6;
  int N, S, sum;
 
  N = 6;
  S = 30;
 
  mx1 = mx2 = mx3 = mx4 = mx5 = mx6 = N;
 
 
mx1 = ( S     < N ) ? S     : N;
mx2 = ( S / 2 < N ) ? S / 2 : N;
mx3 = ( S / 3 < N ) ? S / 3 : N;
mx4 = ( S / 4 < N ) ? S / 4 : N;
mx5 = ( S / 5 < N ) ? S / 5 : N;
mx6 = ( S / 6 < N ) ? S / 6 : N;
 
 
for( int i6 = 0; i6 <= mx6; i6++ ){
   for( int i5 = 0; i5 <= mx5; i5++ ){
      for( int i4 = 0; i4 <= mx4; i4++ ){
         for( int i3 = 0; i3 <= mx3; i3++ ){
            for( int i2 = 0; i2 <= mx2; i2++ ){
               for( int i1 = 0; i1 <= mx1; i1++ ){
                    if( i1 + i2 + i3 + i4 + i5 + i6 <= N ){
                        sum = i1 + 2*i2 + 3*i3 + 4*i4 + 5*i5 + 6*i6;
                        if( sum == S ){
                            cout << i1 << i2 << i3 << i4 << i5 << i6 << "\n";
                        }
                    }
               }
            }
         }
      }
   }
}
 
    return 0;
}

@tyitoite · 12.08.2020, 04:41 **[ТС]**

Сообщение от vantfiles

вы свое решение не привели, вы примерно так решали? :

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
#include <iostream>
#include <conio.h>
 
int main() 
{
  int mx1, mx2, mx3, mx4, mx5, mx6;
  int N, S, sum;
 
  N = 6;
  S = 30;
 
  mx1 = mx2 = mx3 = mx4 = mx5 = mx6 = N;
 
 
mx1 = ( S     < N ) ? S     : N;
mx2 = ( S / 2 < N ) ? S / 2 : N;
mx3 = ( S / 3 < N ) ? S / 3 : N;
mx4 = ( S / 4 < N ) ? S / 4 : N;
mx5 = ( S / 5 < N ) ? S / 5 : N;
mx6 = ( S / 6 < N ) ? S / 6 : N;
 
 
for( int i6 = 0; i6 <= mx6; i6++ ){
   for( int i5 = 0; i5 <= mx5; i5++ ){
      for( int i4 = 0; i4 <= mx4; i4++ ){
         for( int i3 = 0; i3 <= mx3; i3++ ){
            for( int i2 = 0; i2 <= mx2; i2++ ){
               for( int i1 = 0; i1 <= mx1; i1++ ){
                    if( i1 + i2 + i3 + i4 + i5 + i6 <= N ){
                        sum = i1 + 2*i2 + 3*i3 + 4*i4 + 5*i5 + 6*i6;
                        if( sum == S ){
                            cout << i1 << i2 << i3 << i4 << i5 << i6 << "\n";
                        }
                    }
               }
            }
         }
      }
   }
}
 
    return 0;
}

не так, мой код:

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
#include <iostream>
using namespace std;
 
int main()
{
 
    int c;
 
    cin >> c;
 
    int arr[50][6];
 
    int s_n[50][2];
 
    for (int i = 0; i < c; i++)
    {
 
        cin >> s_n[i][0] >> s_n[i][1];
 
    }
    for (int i = 0; i < 50; i++)
    {
 
        for (int j = 0; j < 6; j++)
        {
 
            arr[i][j] = 0;
 
        }
    }
    for (int i = 0; i < c; i++)
    {
 
        int S = s_n[i][0];
 
        int N = s_n[i][1];
 
        int t = (S + N - 1) / N;
 
        int pos = N;
 
        if (S % N == 0)
        {
 
            arr[i][t - 1] = pos;
 
            continue;
 
        }
 
        if (S - t * (N - 1) < 0)
        {
 
            t--;
 
 
        }
 
        if (S - t * (N - 1) > 0)
        {
 
            pos--;
 
            arr[i][S - t * (N - 1) - 1] = 1;
 
 
        }
 
        arr[i][t - 1] = pos;
 
    }
 
    for (int i = 0; i < c; i++)
    {
 
        for (int j = 0; j < 6; j++)
        {
 
            cout << arr[i][j] << " ";
 
        }
        cout << "\n";
 
    }
}

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@tyitoite 1 / 1 / 0 Регистрация: 11.08.2020 Сообщений: 16

	Какой алгоритм применить к этой задачи? 11.08.2020, 15:13. Показов 1486. Ответов 5 Метки алгоритмы, задача, олимпиада (Все метки) Привет всем. Недавно наткнулся на задачу с Муниципального этапа ВсОШ. Вот ее условие: ----------------------------------------------------------------------------------------------------------------------------------------- В Берляндии в обиходе монеты достоинством 1, 2, 3, 4, 5 и 6 бурлей, толщина всех монет одинаковая. У Васи есть неограниченное количество монет каждого достоинства. Вася и Петя играют в следующую игру: Петя загадывает сумму S, которую необходимо набрать, и сообщает Васе число N — количество монет, которые Вася может использовать. После этого Вася должен подобрать такие N монет, чтобы их сумма равнялась ровно S бурлям. Далее все N монет раскладываются в 6 стопок по номиналам. Петя решил усложнить игру и предложил Васе найти среди всех возможных вариантов такой, что высота самой высокой стопки монет будет максимальной. Толщина всех монет одинаковая, а значит на высоту стопки влияет только количество монет. С усложнённой версией игры у Васи возникли трудности, и он просит вас решить поставленную задачу. ФОРМАТ ВВОДА: В единственной строке подается число n, в следующих n строках вводится S и N ФОРМАТ ВЫВОДА: Вывести n строк - ответ для каждого S и N Тесты: INPUT: 1 30 6 OUTPUT: 0 0 0 0 6 0 написал код, но работает только на 56/100 баллов. не подскажите какой алгоритм применить к данной задаче. Может воспользоваться Динамическим Программированием? скиньте код и объяснение, если не сложно спасибо всем заранее 0

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	11.08.2020, 17:58
	Можно ли увидеть систему проверки, куда можно код отправить и почитать оригинал условия? 0

@tyitoite 1 / 1 / 0 Регистрация: 11.08.2020 Сообщений: 16
	11.08.2020, 18:45 [ТС]
	ссылка https://imcs.dvfu.ru/cats/stat... 63151.html что бы проверить решение нужно принять виртуальное участие в соревновании. 0

Какой алгоритм применить к этой задачи?

Решение