Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
Cool-T
20 / 13 / 1
Регистрация: 17.12.2010
Сообщений: 34
#1

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

25.01.2012, 22:16. Просмотров 2154. Ответов 22
Метки нет (Все метки)

Наткнулся на .
Текст задачи
Гриша очень любит газировку 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++;
    }
Ошибка в подходе к решению или в его реализации?
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.01.2012, 22:16
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Оптимальное заполнение или "Халява" (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Вставить пробел после каждого символа "." "," "!" или "?", если за этими символами не следует пробел - C++
Вставить пробел после каждого символа &quot;.&quot; &quot;,&quot; &quot;!&quot; или &quot;?&quot;, если за этими символами не следует пробел (т. е. следует любой символ, кроме...

Написать программу, которая запрашивает у пользователя номер дня недели и выводит одно из сообщений: "Рабочий день","Суббота" или "Воскресенье" - C++
Написать программу, которая запрашивает у пользователя номер дня недели и выводит одно из сообщений: &quot;Рабочий день&quot;,&quot;Суббота&quot; или...

Дан текст, хранящийся в текстовом файле f, каждый символ которого может быть малой буквой, цифрой или одним из знаков "+", "-", "*". - C++
Дан текст, хранящийся в текстовом файле f, каждый символ которого может быть малой буквой, цифрой или одним из знаков &quot;+&quot;, &quot;-&quot;, &quot;*&quot;. Групой...

Определить, какая из точек "В" или "С" расположены ближе к точке "А". - C++
На оси Ох расположены 3 точки А, В и С. Определить, какая из точек &quot;В&quot; или &quot;С&quot; расположены ближе к точке &quot;А&quot;. Предусмотреть вариант...

Обчисление введенной строки любого формата(пример:"(2+3)/4*2"или"2+3"или ...) - C++
Доброе время суток ! Если у когото есть такое код выложыте пожалуста,буду примного благодарен, или подскажыте какойто алгоритм или где...

22
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2012, 09:00 #2
Цитата Сообщение от Cool-T Посмотреть сообщение
Ошибка в подходе к решению или в его реализации?
в подходе к решению.
Вот Вам тест в помощь:
0 4 4 10
Правильный ответ: 2.
2
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 09:45 #3
Кто-нибудь может подсказать, как решается эта задача? Ее тема "Динамическое прогарммирование", но лично я вообще не вижу от чего к чему можно переходить! Разве что какой-то бинпоиск...
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 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]
1
Toshkarik
1148 / 865 / 51
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
20.05.2012, 15:44 #5
Просто стало интересно, а есть ли варианты, при которых нельзя просто все перемножить, сложить и разделить? Ведь значения очень малы.
0
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 операций заходят.
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 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.
1
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 16:23 #8
Цитата Сообщение от Toshkarik Посмотреть сообщение
Просто стало интересно, а есть ли варианты, при которых нельзя просто все перемножить, сложить и разделить? Ведь значения очень малы.
Вот Вам пример:
100
0 0 100 2
По вашему решению, ответ это 100*3 / 2 , а на самом деле не так, потому что всегда 1 звезда будет лишней и мы ее будем "терять".
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 16:24 #9
Цитата Сообщение от AncinetHero Посмотреть сообщение
Вообще странно, что 10^8 операций заходят.
Вообще-то 10^6 операций
1
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.05.2012, 16:46 #10
Memory limit. o-O
А Вы ее пытались сдавать?

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

Добавлено через 37 секунд
На счет лимита памяти - был тип long long , сделал int . Думал ответы будут большие иногда, оказалось - нет.
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 17:02 #13
Цитата Сообщение от AncinetHero Посмотреть сообщение
Сдал,
ну это самое главное )
0
Toshkarik
1148 / 865 / 51
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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;
}
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 19:54 #15
Цитата Сообщение от Toshkarik Посмотреть сообщение
Попробовал сделать без циклов и массивов, вроде работает:
вот так неправильно вычисляет:
1 11 0 11
должно быть 2.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2012, 19:54
Привет! Вот еще темы с ответами:

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Реализовать условие "больше или равно", "меньше или равно" для простых дробей в классе - C++
как реализовать условие больше или равно, меньше или равно для простых дробей в классе?

бинарный "++": "Counter" не определяет этот оператор или преобразование к типу приемлемо к встроенному - C++
бинарный &quot;++&quot;: &quot;Counter&quot; не определяет этот оператор или преобразование к типу приемлемо к встроенному оператору #include &lt;iostream&gt; ...

Нужно сделать так, чтобы при вводе числа, выводило "рублей" или "рубль" - C++
Начал решать задачу и засох на средине, не выходить формулу написать,если не сложно,подскажите) с с++ знаю пока что if,else и swith) //...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru