Форум программистов, компьютерный форум 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++ Дана строка, в котором есть слово "да" или слово "нет". Если в нем есть слово "нет", то удалить его
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Натальяя
0 / 0 / 0
Регистрация: 28.11.2013
Сообщений: 11
29.11.2013, 08:47     Оптимальное заполнение или "Халява" #21
помоги пожалуйста, вообще не понимаю как можно с помощью структуры данных стек написать программу в С++, которая распознает арифметические выражения, то есть выводит правильно ли записано выражение или нет. Например если вводить с клавиатуры вот такое выражение (58as+r/(re-s) то программа должна сказать, что оно не правильное так как там не хватает закрывающей скобки (достаточно сказать, что оно не правильно и указать позицию, где встретилась ошибка). Данные выражения состоят из букв (латиница), цифр [0-9], скобок "(" и ")" и арифметических знаков "+","-" и "/"?????
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Smart_S
0 / 0 / 0
Регистрация: 24.11.2013
Сообщений: 3
29.11.2013, 18:27     Оптимальное заполнение или "Халява" #22
Задачу решил оптимизацией своего кода. Предполагаю, что есть другие решения, но это работает. Трехмерный массив нужно либо объявить вне стека, т.е. глобально, либо vector, либо указатель на линейный массив индексы пересчитывать (если кто-нибудь еще решать будет).

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

Проблема только в скобках. Если открывающая встречается, кладем в стек. Если закрывающая, проверяем, чтобы в стеке лежала последней закрывающая и удаляем ее. Если лежит открывающая, то выражение неверно.
Если после прохода стек непуст, то выражение неверно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2013, 20:34     Оптимальное заполнение или "Халява"
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Натальяя
0 / 0 / 0
Регистрация: 28.11.2013
Сообщений: 11
29.11.2013, 20:34     Оптимальное заполнение или "Халява" #23
Smart_S, а можете скинуть вашу программу?
Yandex
Объявления
29.11.2013, 20:34     Оптимальное заполнение или "Халява"
Ответ Создать тему
Опции темы

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