Определить минимальное количество купюр, необходимое для покупки

@vlados124 · Регистрация: 13.09.2018

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

Часто граждане пытаются выяснить, насколько богатыми являются депутаты. Некоторые верят, что материальное положение отдельных депутатов являются неограниченными.
Поэтому представьте себе депутата, у которого есть неограниченное количество купюр всех номиналов (1, 2, 5, 10, 20, 50, 100, 200, 500 рублей). Он хочет приобрести подарок для своей тещи, что стоит N рублей. Несмотря на то, что наш герой бесконечно богат, он также является и бесконечно скупым. Именно поэтому он хочет оплатить покупку наличными без остатка. Какое минимальное количество купюр ему для этого понадобится?

Входные данные
Целое число N

Выходные данные
Минимальное количество купюр, необходимой для покупки

Ограничения
1 ≤ N ≤ 10⁹

Пример
Входные данные
74
Выходные данные
4

@Puporev · 19.09.2018, 08:44

Не по теме:

Сообщение от vlados124

наш герой бесконечно богат, он также является и бесконечно скупым.

Типа Порошенко...

@vlados124 · 19.09.2018, 14:35 **[ТС]**

Напишите пж))

@bormant · 19.09.2018, 16:45

Не по теме:

Зачем?

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

@Constantin Cat · 19.09.2018, 19:52

Не по теме:

Сообщение от vlados124

Поэтому представьте себе депутата,

Лучше

Сообщение от vlados124

1, 2, 5

Сейчас их сделали, их железными, пусть качаются.
:)

@Cyborg Drone · 20.09.2018, 02:18

Да отчего же не написать? Знания за чужой счёт жить не помогают...

Один из вариантов решения для "олимпийского" сайта:

Pascal

const
  k: longint = 0;
  q: longint = 10;
  d: longint = 100;
 
var
  n, p, i: longint;
 
begin
  readln(n);
  repeat
    for i := 1 to 3 do
      begin
        p := q shr i * d;
        inc(k, n div p);
        n := n mod p
      end;
    d := d div 10
  until d = 0;
  writeln(k)
end.

@bormant · 20.09.2018, 08:44

Cyborg Drone,
купюрный ряд (а это всё, кроме строк 2, 10, 15, 16, 20) отлично получился

@vlados124 · 20.09.2018, 14:57 **[ТС]**

Паскаль выдает ошибку, связаной с делением на ноль

@D1973 · 21.09.2018, 09:02

Сообщение от vlados124

купюр всех номиналов (1, 2, 5, 10, 20, 50, 100, 200, 500 рублей)

Задача-то из прошлого века... В 1991 - 1992 г. были купюры таких номиналов

Добавлено через 1 час 33 минуты
Cyborg Drone, странное решение...
сначала const k: longint = 0;
и далее: inc(k, n div p);
Это как это так: значение константы менять?
Другое дело, если k, q, d под var объявить...

@bormant · 21.09.2018, 09:10

D1973,
ничего странного, раздел называется Turbo Pascal, в его синтаксисе инициализированные переменные выглядят именно так, с const (типизированные константы назывались они), см. Turbo Pascal и инициализированные переменные
Синтаксис с возможностью инициализации в разделе var появился намного позже не только выхода, но и завершения поддержки последнего из линейки Turbo Pascal.

@D1973 · 21.09.2018, 09:13

Другой вариант...

Pascal

const A: array[1..9] of integer = (1, 2, 5, 10, 20, 50, 100, 200, 500);
var Rez: array[1..9] of integer;
    Count, Summ, i: integer;
    s1, s2: String;
 
begin
 Write('Введите сумму: ');
 Readln(Summ);
 Count := 0;
 for i := 1 to 9 do
  Rez[i] := 0;
 for i := 9 downto 1 do
  if Summ div A[i] > 0 then 
   begin
     inc(Rez[i], Summ div A[i]);
     inc(Count, Summ div A[i]);
     Summ := Summ - A[i] * (Summ div A[i]);
   end;  
 s1 := '';
 s2 := '';
 for i := 1 to 9 do
  begin
   s1 := s1 + IntToStr(A[i]) + #9;   
   s2 := s2 + IntToStr(Rez[i]) + #9;
  end;
 writeln(s1);
 writeln(s2);
 writeln('Количество купюр - ', Count);
end.

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

Сообщение от bormant

типизированные константы назывались они

Забыл про это наглухо... Виноват-с...

@bormant · 21.09.2018, 11:34

D1973,
раздел называется Turbo Pascal:
- вы забыли приложить реализацию функции IntToStr() ;-)
- 10-11, 19-20: глобальныя переменныя Rez, s1, s2 уже инициализированы нулями/пустыми строками, повторная инициализация теми же значениями ни к чему ;-) (но это на самом деле просто придирки

).
- Integer -- он тут 16-разрядный, нет смысла так ограничивать допустимую сумму, когда 32-разряда (Longint) почти ничего не стоят.
- деление штука дорогая (было раньше, хотя нет, раньше оно было очень дорогим), а тут их аж 4 штуки одинаковых.
Кругом по коду "магические числа" (1, 9) -- нехорошо, неуниверсально, неаккуратно -- сопровождение такого кода требует большого внимания и провоцирует ошибки.

Зачем делать плохо, когда можно делать хорошо за ровно ту же цену?

Добавлено через 22 минуты
Попробуем избавиться от недостатков:

Pascal

const
  Nom: array [1..9] of Integer = (1, 2, 5, 10, 20, 50, 100, 200, 500);
var
  Res: array [Low(Nom)..High(Nom)] of Longint;
  Cnt, Sum: Longint;
  i: Integer;
begin
  Write('Введите сумму: '); ReadLn(Sum);
  for i:=High(Nom) downto Low(Nom) do begin
    Res[i]:=Sum div Nom[i];
    if Res[i]>0 then begin
      Inc(Cnt,Res[i]);
      Dec(Sum,Res[i]*Nom[i]);
    end;
  end;
  WriteLn(Cnt,' купюр всего');
  WriteLn('По номиналам:');
  Write(Nom[Low(Nom)]); for i:=Low(Nom)+1 to High(Nom) do Write(#9,Nom[i]); WriteLn;
  Write(Res[Low(Res)]); for i:=Low(Res)+1 to High(Res) do Write(#9,Res[i]); WriteLn;
end.

@D1973 · 21.09.2018, 11:43

Не по теме:

Ох, беда-беда... Вот не хочется все это вспоминать, а ведь придется: детеныш в школе начал изучение Turbo Pascal... Придется соответствовать подрастающему поколению... Вот залез посмотреть-попрактиковаться... Осталось TP7 найти-поставить...

bormant, спасибо!

@bormant · 21.09.2018, 11:46

Не по теме:

Сообщение от D1973

найти

Есть такая тема ;) Скачать Паскаль

@D1973 · 21.09.2018, 17:18

Ага, я ее видел... Я тут просто еще не определился, то ли через DOS-Box работать (пробовал с C++ 3.0 - не очень понравилось...), то ли виртуалку поднимать Win98... Сейчас как-то в эту сторону больше смотрю...

Не по теме:

А вообще - надо в школе узнать, как они там работают, чтобы моя школота в ступор не впала, увидев нечто, отличное от того, к чему дома привыкли...

@vlados124 1 / 1 / 0 Регистрация: 13.09.2018 Сообщений: 126
		1
	Определить минимальное количество купюр, необходимое для покупки 18.09.2018, 22:42. Показов 1205. Ответов 14 Метки нет (Все метки) Часто граждане пытаются выяснить, насколько богатыми являются депутаты. Некоторые верят, что материальное положение отдельных депутатов являются неограниченными. Поэтому представьте себе депутата, у которого есть неограниченное количество купюр всех номиналов (1, 2, 5, 10, 20, 50, 100, 200, 500 рублей). Он хочет приобрести подарок для своей тещи, что стоит N рублей. Несмотря на то, что наш герой бесконечно богат, он также является и бесконечно скупым. Именно поэтому он хочет оплатить покупку наличными без остатка. Какое минимальное количество купюр ему для этого понадобится? Входные данные Целое число N Выходные данные Минимальное количество купюр, необходимой для покупки Ограничения 1 ≤ N ≤ 10⁹ Пример Входные данные 74 Выходные данные 4 0

@Puporev
	19.09.2018, 08:44 #2
	Не по теме: Сообщение от vlados124 наш герой бесконечно богат, он также является и бесконечно скупым. Типа Порошенко... 0

@vlados124 1 / 1 / 0 Регистрация: 13.09.2018 Сообщений: 126
	19.09.2018, 14:35 [ТС]	3
	Напишите пж)) 0

@bormant
	19.09.2018, 16:45 #4
	Не по теме: Зачем? Предметная олимпиада — состязание учащихся учреждений среднего общего, высшего или профессионального образования, требующее от участников демонстрации знаний и навыков в области одной или нескольких изучаемых дисциплин. Участник олимпиады обычно усиленно готовится к ней, что способствует усвоению учебного и дополнительного материала. 0

@Constantin Cat
	19.09.2018, 19:52 #5
	Не по теме: Сообщение от vlados124 Поэтому представьте себе депутата, Лучше Сообщение от vlados124 1, 2, 5 Сейчас их сделали, их железными, пусть качаются. :) 0

@bormant Модератор 7771 / 4600 / 2824 Регистрация: 22.11.2013 Сообщений: 13,080 Записей в блоге: 1
	20.09.2018, 08:44	7
	Cyborg Drone, купюрный ряд (а это всё, кроме строк 2, 10, 15, 16, 20) отлично получился 0

@vlados124 1 / 1 / 0 Регистрация: 13.09.2018 Сообщений: 126
	20.09.2018, 14:57 [ТС]	8
	Паскаль выдает ошибку, связаной с делением на ноль 0

@D1973 Модератор 9270 / 6048 / 2380 Регистрация: 21.01.2014 Сообщений: 25,828 Записей в блоге: 3
	21.09.2018, 09:02	9
	Сообщение от vlados124 купюр всех номиналов (1, 2, 5, 10, 20, 50, 100, 200, 500 рублей) Задача-то из прошлого века... В 1991 - 1992 г. были купюры таких номиналов Добавлено через 1 час 33 минуты Cyborg Drone, странное решение... сначала const k: longint = 0; и далее: inc(k, n div p); Это как это так: значение константы менять? Другое дело, если k, q, d под var объявить... 0

@bormant Модератор 7771 / 4600 / 2824 Регистрация: 22.11.2013 Сообщений: 13,080 Записей в блоге: 1
	21.09.2018, 09:10	10
	D1973, ничего странного, раздел называется Turbo Pascal, в его синтаксисе инициализированные переменные выглядят именно так, с const (типизированные константы назывались они), см. Turbo Pascal и инициализированные переменные Синтаксис с возможностью инициализации в разделе var появился намного позже не только выхода, но и завершения поддержки последнего из линейки Turbo Pascal. 0

@D1973 Модератор 9270 / 6048 / 2380 Регистрация: 21.01.2014 Сообщений: 25,828 Записей в блоге: 3
	21.09.2018, 11:43	13
	Не по теме: Ох, беда-беда... Вот не хочется все это вспоминать, а ведь придется: детеныш в школе начал изучение Turbo Pascal... Придется соответствовать подрастающему поколению... Вот залез посмотреть-попрактиковаться... Осталось TP7 найти-поставить... bormant, спасибо! 0

	21.09.2018, 17:18

@bormant
	21.09.2018, 11:46 #14
	Не по теме: Сообщение от D1973 найти Есть такая тема ;) Скачать Паскаль 0