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

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

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

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

25.01.2012, 22:16. Просмотров 2100. Ответов 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
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 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;
}
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.05.2012, 20:10 #17
Цитата Сообщение от Toshkarik Посмотреть сообщение
Сейчас по Вашему варианту выдает правильный ответ, а вот если вбить 0 4 2 7 то уже нет
Не мучайтесь - без циклов вряд ли получится.
0
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 минуту
простинкий перебор
0
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;
}
0
Smart_S
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 3
26.11.2013, 18:55 #20
Цитата Сообщение от Smart_S Посмотреть сообщение
решение не проходит по времени.
Немного оптимизировал, вроде нет ошибки по времени, но все равно массив [100][100][100] не создать, а, похоже, один из тестов 100 100 100 как раз.
0
Натальяя
0 / 0 / 0
Регистрация: 28.11.2013
Сообщений: 11
29.11.2013, 08:47 #21
помоги пожалуйста, вообще не понимаю как можно с помощью структуры данных стек написать программу в С++, которая распознает арифметические выражения, то есть выводит правильно ли записано выражение или нет. Например если вводить с клавиатуры вот такое выражение (58as+r/(re-s) то программа должна сказать, что оно не правильное так как там не хватает закрывающей скобки (достаточно сказать, что оно не правильно и указать позицию, где встретилась ошибка). Данные выражения состоят из букв (латиница), цифр [0-9], скобок "(" и ")" и арифметических знаков "+","-" и "/"?????
0
Smart_S
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 3
29.11.2013, 18:27 #22
Задачу решил оптимизацией своего кода. Предполагаю, что есть другие решения, но это работает. Трехмерный массив нужно либо объявить вне стека, т.е. глобально, либо vector, либо указатель на линейный массив индексы пересчитывать (если кто-нибудь еще решать будет).

Добавлено через 3 минуты
Цитата Сообщение от Натальяя Посмотреть сообщение
помоги пожалуйста, вообще не понимаю как можно с помощью структуры данных стек написать программу в С++, которая распознает арифметические выражения, то есть выводит правильно ли записано выражение или нет. Например если вводить с клавиатуры вот такое выражение (58as+r/(re-s) то программа должна сказать, что оно не правильное так как там не хватает закрывающей скобки (достаточно сказать, что оно не правильно и указать позицию, где встретилась ошибка). Данные выражения состоят из букв (латиница), цифр [0-9], скобок "(" и ")" и арифметических знаков "+","-" и "/"?????
Если ко мне обращение, то отвечу, как думаю.

Проблема только в скобках. Если открывающая встречается, кладем в стек. Если закрывающая, проверяем, чтобы в стеке лежала последней закрывающая и удаляем ее. Если лежит открывающая, то выражение неверно.
Если после прохода стек непуст, то выражение неверно.
0
Натальяя
0 / 0 / 0
Регистрация: 28.11.2013
Сообщений: 11
29.11.2013, 20:34 #23
Smart_S, а можете скинуть вашу программу?
0
29.11.2013, 20:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2013, 20:34
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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