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

Оптимальное заполнение или "Халява" - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
Cool-T
20 / 13 / 1
Регистрация: 17.12.2010
Сообщений: 34
25.01.2012, 22:16     Оптимальное заполнение или "Халява" #1
Наткнулся на задачку с ********.
Текст задачи
Гриша очень любит газировку PupsiCola. Однажды он узнал, что, собрав несколько крышек со звездочками, можно получить футболку. Гриша нашел A крышек с одной звездочкой, B крышек с двумя звездочками и C крышек с тремя звездочками. На футболку можно обменять набор крышек, общее количество звездочек на которых не меньше K.

Помогите Грише узнать, сколько футболок он может получить.

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

Входной файл INPUT.TXT содержит целые числа A, B, C и K (0 ≤ A, B, C ≤ 100, 1 ≤ K ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите максимальное количество футболок, которые может получить Гриша.


Вроде не сложно. Я начал решать задачу думая мол так : чем оптимальней заполнять k тем больше футболок получу на выходе. Как мне кажется, оптимальным будет начинать с трехзвездочных крышек, продолжая двухзвездочными и заканчивая однозвездочными, отдавая так, чтобы их сумма как можно реже превышала k.
Вроде бы все замечательно, я проверил с кучей вариантов из головы свой код, с ними все работает должным образом. Но тем не менее не прохожу проверку "Тест 3" на сайте.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while (k<=a+2*b+3*c)   // Пока крышек хватает на футболки
    {
        int o=k;             // o - остаток
        while(o>0)
        {       
            if (c && (o > 2 || !(a+b)))  // Отдать трёхзвездочную пробку только если
                {o-=3;c--;}     // остаток больше двух или остальные пробки кончились.
                        else
            if (b && (o > 1 || !a))      // --//-- для двухзвездочных
                {o-=2;b--;} 
                        else
            if(a && o> 0)                 // добить "k" единичками.
                {o-=1; a--;}
        }
        p++;
    }
Ошибка в подходе к решению или в его реализации?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.01.2012, 22:16     Оптимальное заполнение или "Халява"
Посмотрите здесь:

C++ Дано трехзначное число. Проверить истинность высказывания: "Цыфры даного числа образуют возрастающую или убывающую последовательность"."
"И" ведет себя как "ИЛИ" C++
C++ Обчисление введенной строки любого формата(пример:"(2+3)/4*2"или"2+3"или ...)
"Точность вычислений" или "Элементарная погрешность" C++
C++ Дана строка, в котором есть слово "да" или слово "нет". Если в нем есть слово "нет", то удалить его
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2012, 09:00     Оптимальное заполнение или "Халява" #2
Цитата Сообщение от Cool-T Посмотреть сообщение
Ошибка в подходе к решению или в его реализации?
в подходе к решению.
Вот Вам тест в помощь:
0 4 4 10
Правильный ответ: 2.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 09:45     Оптимальное заполнение или "Халява" #3
Кто-нибудь может подсказать, как решается эта задача? Ее тема "Динамическое прогарммирование", но лично я вообще не вижу от чего к чему можно переходить! Разве что какой-то бинпоиск...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 12:06     Оптимальное заполнение или "Халява" #4
Цитата Сообщение от AncinetHero Посмотреть сообщение
Кто-нибудь может подсказать, как решается эта задача?
Могу описать алгоритм, который сам использовал для решения этой задачи:
Для решения нужны два трехмерных массива: t1[][][] размером (a+1)*(b+1)*(c+1) и t2[][][] такого же размера. Изначально значения массивов равны 0.
t1[][][] - нужен для количества звездочек, которые не хватает на очередную футболку. Т.е. любое значение t1[i][j][y] (i- количество крышек с 1 звездой, j - количество крышек с 2-мя звездами, y - количество крышек с 3-мя звездами) может быть в диапазоне от 0 до K-1. Как только это значение достигает или превышает K , то мы значение t1[i][j][y] обнуляем, но увеличим на 1 значение t2[i][j][y].
t2[i][j][y] - будет иметь значение максимального числа футболок когда: i- количество крышек с 1 звездой, j - количество крышек с 2-мя звездами, y - количество крышек с 3-мя звездами.
Теперь сам проход:
три цикла:
C++
1
2
3
  for(i=1; i<a+1; i++)
      for(j=1; j<b+1; j++)
          for(y=1; y<c+1; y++)
В каждой итерации выбираем максимальные значения для t1[i][j][y] и t2[i][j][y].
Пробуем сначало оттолкнуться от значения t1[i-1][j][y] (количество неиспользуемых звезд) и t2[i-1][j][y] (количество имеющихся футболок). t1[i][j][y] будет равно t1[i-1][j][y]+1, а t2[i][j][y] будет равно t2[i-1][j][y]. Но если t1[i][j][y] стало равным или более K, то запишем t1[i][j][y]=0; t2[i][j][y]++;

Потом пробуем оттолкнуться от значения t1[i][j-1][y] и t2[i][j-1][y]. Здесь нужно учитывать, что значения в t1[i][j][y] и t2[i][j][y] уже есть, но если количество футболок получаем из варианта [i][j-1][y] превысит записанное значение в t2[i][j][y] или
количество футболок останется прежним, но увеличится количество неиспользованных звезд, то значения t1[i][j][y] и t2[i][j][y] будут расчитываться от значений t1[i][j-1][y] и t2[i][j-1][y].

Так же в этой же итерации проверяется возможность получения максимального значения t1[i][j][y] и t2[i][j][y] из варианта t1[i][j][y-1] и t2[i][j][y-1]
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
20.05.2012, 15:44     Оптимальное заполнение или "Халява" #5
Просто стало интересно, а есть ли варианты, при которых нельзя просто все перемножить, сложить и разделить? Ведь значения очень малы.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 16:21     Оптимальное заполнение или "Халява" #6
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Могу описать алгоритм, который сам использовал для решения этой задачи:
Для решения нужны два трехмерных массива: t1[][][] размером (a+1)*(b+1)*(c+1) и t2[][][] такого же размера. Изначально значения массивов равны 0.
t1[][][] - нужен для количества звездочек, которые не хватает на очередную футболку. Т.е. любое значение t1[i][j][y] (i- количество крышек с 1 звездой, j - количество крышек с 2-мя звездами, y - количество крышек с 3-мя звездами) может быть в диапазоне от 0 до K-1. Как только это значение достигает или превышает K , то мы значение t1[i][j][y] обнуляем, но увеличим на 1 значение t2[i][j][y].
t2[i][j][y] - будет иметь значение максимального числа футболок когда: i- количество крышек с 1 звездой, j - количество крышек с 2-мя звездами, y - количество крышек с 3-мя звездами.
Теперь сам проход:
три цикла:
C++
1
2
3
  for(i=1; i<a+1; i++)
      for(j=1; j<b+1; j++)
          for(y=1; y<c+1; y++)
В каждой итерации выбираем максимальные значения для t1[i][j][y] и t2[i][j][y].
Пробуем сначало оттолкнуться от значения t1[i-1][j][y] (количество неиспользуемых звезд) и t2[i-1][j][y] (количество имеющихся футболок). t1[i][j][y] будет равно t1[i-1][j][y]+1, а t2[i][j][y] будет равно t2[i-1][j][y]. Но если t1[i][j][y] стало равным или более K, то запишем t1[i][j][y]=0; t2[i][j][y]++;

Потом пробуем оттолкнуться от значения t1[i][j-1][y] и t2[i][j-1][y]. Здесь нужно учитывать, что значения в t1[i][j][y] и t2[i][j][y] уже есть, но если количество футболок получаем из варианта [i][j-1][y] превысит записанное значение в t2[i][j][y] или
количество футболок останется прежним, но увеличится количество неиспользованных звезд, то значения t1[i][j][y] и t2[i][j][y] будут расчитываться от значений t1[i][j-1][y] и t2[i][j-1][y].

Так же в этой же итерации проверяется возможность получения максимального значения t1[i][j][y] и t2[i][j][y] из варианта t1[i][j][y-1] и t2[i][j][y-1]
Спасибо за обьяснение, сейчас попробую сдать. Вообще странно, что 10^8 операций заходят.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 16:23     Оптимальное заполнение или "Халява" #7
Цитата Сообщение от Toshkarik Посмотреть сообщение
Просто стало интересно, а есть ли варианты, при которых нельзя просто все перемножить, сложить и разделить? Ведь значения очень малы.
В смысле сделать так:
(A*1 + B*2 + C*3 ) / K
это число и подать в ответ?
Если это имели ввиду, то могу привести несколько контрпримеров, когда нельзя.
Один прямо сейчас:
0 0 1 1
правильный ответ 1.
А если перемножить, сложить и разделить то получится 3.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 16:23     Оптимальное заполнение или "Халява" #8
Цитата Сообщение от Toshkarik Посмотреть сообщение
Просто стало интересно, а есть ли варианты, при которых нельзя просто все перемножить, сложить и разделить? Ведь значения очень малы.
Вот Вам пример:
100
0 0 100 2
По вашему решению, ответ это 100*3 / 2 , а на самом деле не так, потому что всегда 1 звезда будет лишней и мы ее будем "терять".
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 16:24     Оптимальное заполнение или "Халява" #9
Цитата Сообщение от AncinetHero Посмотреть сообщение
Вообще странно, что 10^8 операций заходят.
Вообще-то 10^6 операций
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 16:46     Оптимальное заполнение или "Халява" #10
Memory limit. o-O
А Вы ее пытались сдавать?

Добавлено через 44 секунды
Эх, придется извращаться и запоминать лишь предыдущие значения.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 16:54     Оптимальное заполнение или "Халява" #11
Цитата Сообщение от AncinetHero Посмотреть сообщение
А Вы ее пытались сдавать?
я ее когда-то уже сдавал.
Покажите весь код.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 16:56     Оптимальное заполнение или "Халява" #12
Сдал, спасибо большое . Только в цикле нужно от нулей начинать, кстати!

Добавлено через 37 секунд
На счет лимита памяти - был тип long long , сделал int . Думал ответы будут большие иногда, оказалось - нет.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 17:02     Оптимальное заполнение или "Халява" #13
Цитата Сообщение от AncinetHero Посмотреть сообщение
Сдал,
ну это самое главное )
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
20.05.2012, 18:14     Оптимальное заполнение или "Халява" #14
Попробовал сделать без циклов и массивов, вроде работает:
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
int main() {
   std::size_t A = 0,
               B = 0,
               C = 100,
               k = 2,
               shirt = 0,
               cCount = k / 3,
               bCount = k / 2;
   
   if ( k == 1 ) {
      shirt = A + B + C;
      std::cout << shirt << std::endl;
      return 0;
   }
   
   if ( k == 2 ) {
      shirt = B + C + ( A / 2 );
      std::cout << shirt << std::endl;
      return 0;
   }
   
   if ( k % 3 == 0 ) {
      shirt += C / cCount;
      C -= ( C / cCount ) * cCount;
      
      if ( A >= B / bCount ) {
         shirt += B / bCount;
         A -= B / bCount;
         B -= ( B / bCount ) * bCount;
      } else {
         shirt = A;
         B -= A * bCount;
         A = 0;
      }
   } else if ( k % 2 == 0 ) {
      B += A / 2;
      A = ( A & 1 );
      shirt += B / bCount;
      B -= ( B / bCount ) * bCount;
      
      shirt += C / ( cCount + 1 );
      C -= C / ( cCount + 1 ) * cCount;
   }
   
   if ( A + B * 2 + C * 3 >= k )
      shirt++;
   
   std::cout << shirt << std::endl;
   
   return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 19:54     Оптимальное заполнение или "Халява" #15
Цитата Сообщение от Toshkarik Посмотреть сообщение
Попробовал сделать без циклов и массивов, вроде работает:
вот так неправильно вычисляет:
1 11 0 11
должно быть 2.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
20.05.2012, 20:06     Оптимальное заполнение или "Халява" #16
Да я заметил, поспешил, не доделал. Сейчас по Вашему варианту выдает правильный ответ, а вот если вбить 0 4 2 7 то уже нет
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
int main() {
   std::size_t A = 0,
               B = 0,
               C = 0,
               k = 0,
               shirt = 0,
               cCount = 0,
               bCount = 0,
               temp = 0;
   
   std::ifstream inFile( "INPUT.TXT", std::ios::in );
   std::ofstream outFile( "OUTPUT.TXT", std::ios::out );
   
   inFile >> A >> B >> C >> k;
 
   if ( k == 1 ) {
      outFile << ( A + B + C );
      return 0;
   }
   
   if ( k == 2 ) {
      outFile << ( B + C + ( A / 2 ));
      return 0;
   }
   
   cCount = k / 3;
   bCount = k / 2;
   
   if ( k % 3 == 0 ) {
      temp = C / cCount;
      shirt += temp;
      C -= temp * cCount;
      
      if ( A >= B / bCount ) {
         temp = B / bCount;
         shirt += temp;
         B -= temp * bCount;
         A -= temp;
         
         temp = A / k;
         shirt += temp;
         A -= temp * k;
      } else {
         shirt += A;
         B -= bCount * A;
         A = 0;
         
         temp = B / ( bCount + 1 );
         shirt += temp;
         B -= temp * ( bCount + 1 );
      }
   } else if ( k % 3 == 1 ) {
      B += A / 2;
      A = ( A & 1 );
      
      if ( B >= C / cCount ) {
         temp = C / cCount;
         shirt += temp;
         B -= temp;
         C -= temp * cCount;
         
         temp = B / ( bCount + 1 );
         shirt += temp;
         B -= temp * ( bCount + 1 );
      } else {
         temp = C / cCount;
         shirt += B;
         C -= temp * B;
         B = 0;
         
         temp = C / ( cCount + 1 );
         shirt += temp;
         C -= temp * ( cCount + 1 );
      }
   } else {
      if ( A >= C / cCount ) {
         temp = C / cCount;
         shirt += temp;
         A -= temp;
         C -= temp * cCount;
 
         if ( A >= B / bCount ) {
            temp = B / bCount;
            shirt += temp;
            B -= temp * bCount;
            A -= temp;
 
            temp = A / k;
            shirt += temp;
            A -= temp * k;
         } else {
            shirt += A;
            B -= bCount * A;
            A = 0;
 
            temp = B / ( bCount + 1 );
            shirt += temp;
            B -= temp * ( bCount + 1 );
         }
      } else {
         temp = C / cCount;
         shirt += A;
         A = 0;
         C -= temp * A;
         A = 0;
 
         if ( B >= C / cCount ) {
            temp = C / cCount;
            shirt += temp;
            B -= temp;
            C -= temp * cCount;
 
            temp = B / ( bCount + 1 );
            shirt += temp;
            B -= temp * ( bCount + 1 );
         } else {
            temp = C / cCount;
            shirt += B;
            C -= temp * B;
            B = 0;
 
            temp = C / ( cCount + 1 );
            shirt += temp;
            C -= temp * ( cCount + 1 );
         }
      }
   }
   
   if ( A + B * 2 + C * 3 >= k )
      shirt++;
   
   outFile << shirt;
   
   return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 20:10     Оптимальное заполнение или "Халява" #17
Цитата Сообщение от Toshkarik Посмотреть сообщение
Сейчас по Вашему варианту выдает правильный ответ, а вот если вбить 0 4 2 7 то уже нет
Не мучайтесь - без циклов вряд ли получится.
byi_ja
7 / 7 / 0
Регистрация: 16.05.2012
Сообщений: 31
20.05.2012, 21:50     Оптимальное заполнение или "Халява" #18
if ((A*1 + B*2 + C*3 ) == K )then..
+три цикла
+запись в масив из которого потом найти оптимальный

Добавлено через 1 минуту
простинкий перебор
Smart_S
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 3
24.11.2013, 22:03     Оптимальное заполнение или "Халява" #19
Не знаю, принято ли тут создавать новые темы, или "поднимать" старые, так что на всякий случай напишу тут.

Тоже занялся этой задачкой.

Цитата Сообщение от valeriikozlov Посмотреть сообщение
Могу описать алгоритм, который сам использовал для решения этой задачи:
Для решения нужны два трехмерных массива: t1[][][] размером (a+1)*(b+1)*(c+1) и t2[][][] такого же размера. Изначально значения массивов равны 0.
После "облома" с "оптимальным" набором крышек для каждой футболки (тест 0 12 3 11) сам пришёл к такому алгоритму, реализовал. Выдаёт правильные ответы, но:

1) Массив размером [100][100][100] создать не удается, по крайней мере Visual Studio ругается. Что предпринять?
2) Возможно, я где-то туплю, но решение не проходит по времени.


При этом, решения многих на ******** работают быстро и используют ~56 Кб памяти, вроде 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <fstream>
using namespace std;
int main() {
    int unused_stars[30][30][30];
    int clothes_number[30][30][30];
    ifstream in;
    ofstream out;
    in.open("INPUT.TXT");
    out.open("OUTPUT.TXT");
    int a, b, c, k;
    in >> a >> b >> c >> k;
    unused_stars[0][0][0] = 0;
    clothes_number[0][0][0] = 0;
    int i, j, n, current_unused_stars, current_clothes_number;
    for (i = 0; i <= c; i++) {
        for (j = 0; j <= b; j++) {
            for (n = 0; n <= a; n++) {
                current_clothes_number = 0;
                current_unused_stars = 0;
                if (n != 0) {
                    unused_stars[i][j][n] = unused_stars[i][j][n-1] + 1;
                    if (unused_stars[i][j][n] >= k) {
                        unused_stars[i][j][n] = 0;
                        clothes_number[i][j][n] = clothes_number[i][j][n - 1] + 1;
                    }
                    else clothes_number[i][j][n] = clothes_number[i][j][n - 1];
                } 
 
                if (j != 0) {
                    current_unused_stars = unused_stars[i][j-1][n] + 2;
                    if (current_unused_stars >= k) {
                        current_unused_stars = 0;
                        current_clothes_number = clothes_number[i][j-1][n] + 1;
                    }
                    else current_clothes_number = clothes_number[i][j-1][n];
                }
 
                if ((current_clothes_number > clothes_number[i][j][n]) || ((current_clothes_number == clothes_number[i][j][n]) && (current_unused_stars > unused_stars[i][j][n]))) {
                    clothes_number[i][j][n] = current_clothes_number;
                    unused_stars[i][j][n] = current_unused_stars;
                }
 
                if (i != 0) {
                    current_unused_stars = unused_stars[i-1][j][n] + 3;
                    if (current_unused_stars >= k) {
                        current_unused_stars = 0;
                        current_clothes_number = clothes_number[i-1][j][n] + 1;
                    }
                    else current_clothes_number = clothes_number[i-1][j][n];
                }
 
                if ((current_clothes_number > clothes_number[i][j][n]) || ((current_clothes_number == clothes_number[i][j][n]) && (current_unused_stars > unused_stars[i][j][n]))) {
                    clothes_number[i][j][n] = current_clothes_number;
                    unused_stars[i][j][n] = current_unused_stars;
                }
            }
        }
    }
    out << clothes_number[c][b][a];
    in.close();
    out.close();
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2013, 18:55     Оптимальное заполнение или "Халява"
Еще ссылки по теме:

Что применить "\n" или "endl"? C++
"Чудеса типа float" или "Куда девалась информация?" C++
Нужно сделать так, чтобы при вводе числа, выводило "рублей" или "рубль" C++

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

Или воспользуйтесь поиском по форуму:
Smart_S
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 3
26.11.2013, 18:55     Оптимальное заполнение или "Халява" #20
Цитата Сообщение от Smart_S Посмотреть сообщение
решение не проходит по времени.
Немного оптимизировал, вроде нет ошибки по времени, но все равно массив [100][100][100] не создать, а, похоже, один из тестов 100 100 100 как раз.
Yandex
Объявления
26.11.2013, 18:55     Оптимальное заполнение или "Халява"
Ответ Создать тему
Опции темы

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