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

@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, а можете скинуть вашу программу?

Новые блоги и статьи Все статьи Все блоги /
Установка нескольких штампов электронной подписи в строго определенных местах файла docx ВладимирСамохин 19.07.2026 (В!) Работа с Электронной подписью - это неотъемлемая часть современного документооборота. Но что делать, если нужно поставить несколько штампов электронной подписи в строго определенных местах. . .	сукцессия 35. Научная статья о проделанной работе anaschu 19.07.2026 Написал в формате латекс и пдф	Вангую, что это не пройдёт модерацию, и на неделе я запущу свой сервер. Hrethgir 19.07.2026 Эта публикация сейчас в песочнице и ждёт приглашения. https:/ / habr. com/ ru/ sandbox/ 295048/ начало и оглавление - Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование. . .	сукцессия 33. открытые вопросы от клауде anaschu 19.07.2026 "Что накопилось за эту часть А — тринадцать правок, из которых шесть пришли из ваших вопросов и каждая оказалась реальной ошибкой, а не калибровкой: односторонний симбиоз, отсутствующий листопад,. . .
32 сукцессия anaschu 19.07.2026 сукцессия 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не «подкручивает» сходимость —. . .	сукцессия 31: модель микоризы - это модель ещё нескольких явлений, социальных и экономических anaschu 18.07.2026 Теория «Всего»: апдейт v1. 1. 2 — 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не. . .	сукцессия 30. Массив проверяющих друг друга моделей anaschu 18.07.2026 Архитектура сети взаимопроверяющих моделей микоризной сукцессии (v2. 0) Развитие тензорного ОДУ-ядра и создание кросс-платформенного калибровочного полигона Уважаемые коллеги! В продолжение. . .	Грибы - это женщины, деревья - это мужчины. Анти инь янь для союза мужчины и женщины. anaschu 18.07.2026 ГЛАВНЫЙ НАУЧНО-ФИЛОСОФСКИЙ ВЫВОД: Сексуально-Репродуктивный Капитализм против Государства Моногамии Коллеги, мы вышли на финишную прямую 20-мерного ОДУ-моделирования вековой сукцессии (ветка. . .

@Натальяя 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