loganbaby
@loganbaby
c++, html, css

Как решить эту задачу на C++?

#include <iostream>

int main() {
  int sum;

  std::cout << "Введите сумму, которую хотите обналичить : ";
  std::cin >> sum;

  if (sum > 150000) {
    std::cout << "Превышено максимальное число для вывода денег.";
  } else if ((sum % 5000 == 0) || ((sum - 5000) != 0)) {
    int remainder;
    remainder = sum - 5000;
    std::cout << sum / 5000 << " купюр по 5000";       //нужно как то поместить в if
  if (remainder == 0) {
    std::cout << "1 купюра по 5000";
  } else if (remainder % 2000 == 0) {
    std::cout << " и " << remainder / 2000 << " купюр по 2000";       //еще склонения купюр надо сделать
  } else if (remainder % 1000 == 0) {
    std::cout << " и " << remainder / 1000 << " купюр по 1000";
  } else if (remainder % 500 == 0) {
    std::cout << " и " << remainder / 500 << " купюр по 500";
  } else if (remainder % 200 == 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }

  }/* else if ((sum % 2000 == 0) || ((sum - 2000) != 0)) {
    int remainder = sum - 2000;
    //std::cout << sum / 2000  << " купюр по 2000";
    if (remainder == 0) {
      std::cout << "1 купюра по 2000";
    }
    else if (remainder % 1000 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 1000 << " купюр по 1000";
  } else if (remainder % 500 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 500 << " купюр по 500";
  } else if (remainder % 200 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

   else if ((sum % 1000 == 0) && ((sum - 1000) != 0)) {
    int remainder = sum - 1000;
    std::cout << sum / 1000  << " купюр по 1000";
    if (remainder % 500 == 0) {
    std::cout << " и " << remainder / 500 << " купюр по 500";
  } else if (remainder % 200 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

  else if ((sum % 500 == 0) && ((sum - 500) != 0)) {
    int remainder = sum - 500;
    std::cout << sum / 500  << " купюр по 500";
    if (remainder % 200 == 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

  else if ((sum % 200 == 0) && ((sum - 200) != 0)) {
    int remainder = sum - 200;
    std::cout << sum / 200  << " купюр по 200";
    if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

  else if ((sum % 100 == 0) && ((sum - 100) != 0)) {
    int remainder = sum - 100;
    std::cout << sum / 100  << " купюр по 100";
  } else {
    std::cout << "Такую сумму вывести невозможно";
  }*/
}


как решить уже и не знаю. алгоритм с погнутой логикой. любой помощи буду рад

текст задачи :
Однажды Вася подошел к банкомату и захотел обналичить N рублей. В банкомате есть купюры достоинством 100, 200, 500, 1000, 2000 и 5000 рублей. Банкомат хочет выдать Васе запрошенную сумму, обойдясь как можно меньшим числом купюр.

Напишите программу для банкомата, которая по заданному числу N решает, сколько купюр каждого номинала нужно выдать для получения суммы ровно N рублей, либо говорит, что выдать ровно N рублей невозможно (например, если N не делится на 100). В качестве дополнительного ограничения учтите, что банкомат не может выдать за раз более 150 000 рублей, при попытке запросить такую сумму должно быть выдано сообщение об ошибке.

Если можно выдать запрошенную сумму разными способами, которые не отличаются по суммарному количеству купюр, разрешается вывести любой из них. Например, 800 рублей можно выдать как 4 по 200 или как 500 и еще 3 по 100.
  • Вопрос задан
  • 2654 просмотра
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Немного порешав разные суммы руками можно понять, что тут работает жадное решение - можно брать самую большую купюру, помещающуюся в оставшуюся сумму.

Это также можно доказать. Брать более одной 100 нет смысла, их можно было бы заменть на 200. Также более двух 200 брать смысла нет - три можно разменять на 500+100, что меньше купюр. Аналогично для всех оставшихся купюр.

Ну вот вам осталось для каждой купюры проверить, что оставшаяся сумма не меньше купюры, потом выдать сколько влезает купюр и заменить сумму на остаток от деления.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы