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

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

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

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

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

C++ Проверить, есть ли в слове приставка "пре" или "пре".
"И" ведет себя как "ИЛИ" C++
C++ О том как я сошел с ума или "expression must have integral"
Сгенерировать число "1" или "2" C++
"Точность вычислений" или "Элементарная погрешность" C++
C++ Определить, находится ли координата на "ободе", или за пределами, или внутри круга (найти ошибку)
Что применить "\n" или "endl"? 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     Оптимальное заполнение или "Халява"
Еще ссылки по теме:

C++ Класс "Человек", информация о поле: char или int?
Заполнение массива "Змейкой" C++
C++ Структура "Авто", заполнение и запись в файл
Алгоритм для реализации оператора "побитовое исключающее ИЛИ" C++
Написать функцию, реализующую логическую операцию "Исключающее ИЛИ" C++

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

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

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