Нужно выдать сдачу при ограниченном количестве купюр в банкомате(который мы задаем сами)

@Aida Tynybek · Регистрация: 08.05.2019

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

Очень прошу помочь, хотя бы разобрать задачу

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

Формат входных данных
В первой строке ваша программа представляет количество различных номиналов монет N (0 <= N <= 10). В следующих строках перечислена информация о монетах, находящихся в автомате. Каждая строка содержит два числа: первое - номинал монеты, второе - количество монет данного номинала в автомате. Номинал - положительное целое число не более 100. Количество монет одного номинала может быть от 0 до 100. Номиналы монет в списке строго возрастают. Затем дано количество запросов на выдачу сдачи M (0 <= M <= 10). В каждой их следующих M строк содержится единственное число - сдача, которую необходимо выдать. Сдача - целое число от 1 до 10000.

Формат выходных данных
Ваша программа должна вывести M строк. В каждой содержится ответ на соответствующий запрос. Если сдачу выдать можно, то сначала выведите, каким минимальным количеством монет это можно сделать, а затем список монет, разделенных пробелами. Если существует больше одного способа выдать сдачу минимальным числом монет, то максимизируйте номинал первой выданной монеты, затем второй, и т.д. В случае, когда сдачу выдать невозможно, выведите строку Impossible.

Входные данные
5
1 2
5 3
10 1
50 6
100 2
3
126
18
527
Выходные данные
6 100 10 5 5 5 1
Impossible
14 100 100 50 50 50 50 50 50 10 5 5 5 1 1

@QueryMonkey · 02.06.2022, 20:52

Напишите табличное решение.
Для каждой комбинации посмотрите ответ в таблице.

@Aida Tynybek · 03.06.2022, 08:41 **[ТС]**

Не могли бы подробнее объяснить, пожалуйста, я сейчас изучаю джава, поэтому многое дается сложно

Добавлено через 42 секунды
Не могли бы подробнее объяснить, пожалуйста, я сейчас изучаю джава, поэтому многое дается сложно

@Arsegg · 03.06.2022, 09:52

Aida Tynybek, с чем возникли проблемы? Знакомо ли понятие "жадный алгоритм"?

@Aida Tynybek · 03.06.2022, 12:32 **[ТС]**

Такое понятие знакомо, но вот как мне принимать входные данные?
5
1 2
5 3
10 1
50 6
100 2
3
126
18
527

@Arsegg · 03.06.2022, 12:46

Сообщение от Aida Tynybek

но вот как мне принимать входные данные?

Scanner Class in Java.

@Aida Tynybek · 03.06.2022, 12:58 **[ТС]**

Про сканнер тоже знаю
имею в виду, когда вводим

Формат входных данных
В первой строке ваша программа представляет количество различных номиналов монет N (0 <= N <= 10). В следующих строках перечислена информация о монетах, находящихся в автомате. Каждая строка содержит два числа: первое - номинал монеты, второе - количество монет данного номинала в автомате. Номинал - положительное целое число не более 100. Количество монет одного номинала может быть от 0 до 100. Номиналы монет в списке строго возрастают. Затем дано количество запросов на выдачу сдачи M (0 <= M <= 10). В каждой их следующих M строк содержится единственное число - сдача, которую необходимо выдать. Сдача - целое число от 1 до 10000.

5
1 2
5 3
10 1
50 6
100 2
3
126
18
527

@Arsegg · 03.06.2022, 13:31

Aida Tynybek, в чем вопрос?

@Aida Tynybek · 03.06.2022, 14:13 **[ТС]**

Arsegg, Как можно будет получать номиналы и их количество в банкомате

Java
1
2
3
4
5
6
7
8
9
10
11
     Scanner scanner = new Scanner(System.in);
        numOfNomenals = scanner.nextInt(); // получаю количество  вводимых номиналов
 
// дальше читаю вводимые номиналы и их количество с консоли и записываю в массив строк 
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] inputBanknotes = new String[numOfNomenals];
        if (numOfNomenals <= 10){ // если количество номиналов меньше или равно 10 считываем дальнейшее
            for (int i = 0; i < numOfNomenals; i++) {
                inputBanknotes[i] = reader.readLine()  ;  //.replaceAll("\\s+", "");
            }
        }

Вводимые купюры и их количество
1 2
5 3
10 1
50 6
100 2 т.е только такое количество купюр есть в банкомате
исходя из этого нужно выдавать сдачи

Только вот как мне отделить из принимаемого массива строк купюры и их количество

Добавлено через 1 минуту
Arsegg, Не могли бы написать свой телеграм?

@Arsegg · 03.06.2022, 14:41

Сообщение от Aida Tynybek

Как можно будет получать номиналы и их количество в банкомате

Java
1
2
3
4
for (int i = 0; i < n; i++) {
  final var denomination = scanner.nextInt();  // Номинал
  final var amount = scanner.nextInt();  // Количество
}

Сообщение от Aida Tynybek

Про сканнер тоже знаю

@Aida Tynybek · 03.06.2022, 15:04 **[ТС]**

в таком случае он же возвращает две последние значения
а как мне тогда вычислить сумму всех денег, которые есть в банкомате?
5 - количество номиналов, которые есть в банкомате
1 2 ( 1 это купюра, 2 -количество)
5 3
10 1
50 6
100 2
Общая сумма всех денег - (1*2)+5*3+10*1+50*6+100*2=527
Потом вводят
3 - количество сдач
126 - 6 100 10 5 5 5 1, где 6 это количество выдаваемых купюр
18 - выдать невозможно
527 - 14 100 100 50 50 50 50 50 50 10 5 5 5 1 1

как можно принимать и хранить список купюр которые есть в банкомате
исходя из этого выдавать сдачи

@Arsegg · 03.06.2022, 15:49

Не по теме:

Сообщение от Aida Tynybek

в таком случае он же возвращает две последние значения

Только не говори, что вы жадные алгоритмы проходили, а массивы нет...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .

@Aida Tynybek 0 / 0 / 0 Регистрация: 08.05.2019 Сообщений: 9

	Нужно выдать сдачу при ограниченном количестве купюр в банкомате(который мы задаем сами) 02.06.2022, 20:44. Показов 928. Ответов 11 Метки java (Все метки) Очень прошу помочь, хотя бы разобрать задачу Вам поручили написать программу для автомата по продаже напитков. Вам известно, какие номиналы монет и в каком количестве есть в автомате, а также какую сдачу он должен выдать клиенту. Результатом работы вашей программы должен стать список выданных монет или сообщение, что выдать сдачу невозможно. Если сдачу можно выдать несколькими способами, то используйте как можно меньше монет. Если существует больше одного способа выдать сдачу минимальным числом монет, то максимизируйте номинал первой выданной монеты, затем второй, и т.д. Формат входных данных В первой строке ваша программа представляет количество различных номиналов монет N (0 <= N <= 10). В следующих строках перечислена информация о монетах, находящихся в автомате. Каждая строка содержит два числа: первое - номинал монеты, второе - количество монет данного номинала в автомате. Номинал - положительное целое число не более 100. Количество монет одного номинала может быть от 0 до 100. Номиналы монет в списке строго возрастают. Затем дано количество запросов на выдачу сдачи M (0 <= M <= 10). В каждой их следующих M строк содержится единственное число - сдача, которую необходимо выдать. Сдача - целое число от 1 до 10000. Формат выходных данных Ваша программа должна вывести M строк. В каждой содержится ответ на соответствующий запрос. Если сдачу выдать можно, то сначала выведите, каким минимальным количеством монет это можно сделать, а затем список монет, разделенных пробелами. Если существует больше одного способа выдать сдачу минимальным числом монет, то максимизируйте номинал первой выданной монеты, затем второй, и т.д. В случае, когда сдачу выдать невозможно, выведите строку Impossible. Входные данные 5 1 2 5 3 10 1 50 6 100 2 3 126 18 527 Выходные данные 6 100 10 5 5 5 1 Impossible 14 100 100 50 50 50 50 50 50 10 5 5 5 1 1 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	02.06.2022, 20:52
	Напишите табличное решение. Для каждой комбинации посмотрите ответ в таблице. 0

@Aida Tynybek 0 / 0 / 0 Регистрация: 08.05.2019 Сообщений: 9
	03.06.2022, 08:41 [ТС]
	Не могли бы подробнее объяснить, пожалуйста, я сейчас изучаю джава, поэтому многое дается сложно Добавлено через 42 секунды Не могли бы подробнее объяснить, пожалуйста, я сейчас изучаю джава, поэтому многое дается сложно 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	03.06.2022, 09:52
	Aida Tynybek, с чем возникли проблемы? Знакомо ли понятие "жадный алгоритм"? 0

@Aida Tynybek 0 / 0 / 0 Регистрация: 08.05.2019 Сообщений: 9
	03.06.2022, 12:32 [ТС]
	Такое понятие знакомо, но вот как мне принимать входные данные? 5 1 2 5 3 10 1 50 6 100 2 3 126 18 527 0

@Aida Tynybek 0 / 0 / 0 Регистрация: 08.05.2019 Сообщений: 9
	03.06.2022, 12:58 [ТС]
	Про сканнер тоже знаю имею в виду, когда вводим Формат входных данных В первой строке ваша программа представляет количество различных номиналов монет N (0 <= N <= 10). В следующих строках перечислена информация о монетах, находящихся в автомате. Каждая строка содержит два числа: первое - номинал монеты, второе - количество монет данного номинала в автомате. Номинал - положительное целое число не более 100. Количество монет одного номинала может быть от 0 до 100. Номиналы монет в списке строго возрастают. Затем дано количество запросов на выдачу сдачи M (0 <= M <= 10). В каждой их следующих M строк содержится единственное число - сдача, которую необходимо выдать. Сдача - целое число от 1 до 10000. 5 1 2 5 3 10 1 50 6 100 2 3 126 18 527 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	03.06.2022, 13:31
	Aida Tynybek, в чем вопрос? 0

@Aida Tynybek 0 / 0 / 0 Регистрация: 08.05.2019 Сообщений: 9
	03.06.2022, 15:04 [ТС]
	в таком случае он же возвращает две последние значения а как мне тогда вычислить сумму всех денег, которые есть в банкомате? 5 - количество номиналов, которые есть в банкомате 1 2 ( 1 это купюра, 2 -количество) 5 3 10 1 50 6 100 2 Общая сумма всех денег - (12)+53+101+506+100*2=527 Потом вводят 3 - количество сдач 126 - 6 100 10 5 5 5 1, где 6 это количество выдаваемых купюр 18 - выдать невозможно 527 - 14 100 100 50 50 50 50 50 50 10 5 5 5 1 1 как можно принимать и хранить список купюр которые есть в банкомате исходя из этого выдавать сдачи 0