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

@Cool-T · Регистрация: 17.12.2010

Студворк — интернет-сервис помощи студентам

Наткнулся на задачку с acmp.ru.

Текст задачи

Гриша очень любит газировку 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++;
    }

Ошибка в подходе к решению или в его реализации?

@Натальяя · 29.11.2013, 08:47

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

@Smart_S · 29.11.2013, 18:27

Задачу решил оптимизацией своего кода. Предполагаю, что есть другие решения, но это работает. Трехмерный массив нужно либо объявить вне стека, т.е. глобально, либо vector, либо указатель на линейный массив индексы пересчитывать (если кто-нибудь еще решать будет).

Добавлено через 3 минуты

Сообщение от Натальяя

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

Если ко мне обращение, то отвечу, как думаю.

Проблема только в скобках. Если открывающая встречается, кладем в стек. Если закрывающая, проверяем, чтобы в стеке лежала последней закрывающая и удаляем ее. Если лежит открывающая, то выражение неверно.
Если после прохода стек непуст, то выражение неверно.

@Натальяя · 29.11.2013, 20:34

Smart_S, а можете скинуть вашу программу?

Новые блоги и статьи Все статьи Все блоги /
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .

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

@Натальяя 0 / 0 / 0 Регистрация: 28.11.2013 Сообщений: 11
	29.11.2013, 20:34
	Smart_S, а можете скинуть вашу программу? 0

Опции темы