Как написать программу

@AG_1337 · Регистрация: 06.10.2019

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

Уран наконец-то освоен! МОЗГу удалось и на этой мертвой планете поставить нужные преобразователи. Теперь на этой планете можно проводить некоторое время без вреда для здоровья. Чем и решили воспользоваться межпланетные туристические фирмы. Одна из них - «С нами хоть на Луну» - решила потратить весь свой фонд на покупку квадратных участков на Уране. Дабы не потерять в прибыли — нужно потратить весь фонд до монеты, а чтобы иметь меньше проблем с Межпланетной налогово-таможенной службой, было бы здорово купить наименьшее количество участков. Цена 1 кв.м. планеты - 1 монета.

Помогите решить проблему турфирмы.

Формат входного файла
В единственной строке задано одно число — количество монет в фонде турфирмы. Количество монет не превышает 100.

Формат выходного файла
Выведите минимальное количество квадратных участков, которое можно купить, потратив все деньги.

Пояснение к примеру
15 = 3 * 3 + 2 * 2 + 1 * 1 + 1 * 1

ФедосеевПавел · 06.10.2019, 21:43

Чувствую, что можно ускорить и упростить, но не соображу как.
А так - алгоритм Дейкстры

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
program Uran;
 
var
  a: array[0..100] of integer;
  Coins, i, ii, j: integer;
begin
  {исходные данные}
  readln(Coins);
  {инициализация}
  for i := 0 to Coins do
    a[i] := i;
  {решение}
  i := 2;
  ii := sqr(i);
  repeat
    a[ii] := 1;
    for j := ii to Coins do
      if a[j] > a[j - ii] + 1 then
        a[j] := a[j - ii] + 1;
    Inc(i);
    ii := sqr(i);
  until ii > Coins;
  {вывод результата}
  writeln(a[Coins]);
end.

Добавлено через 1 минуту
Только подгоните синтаксис под PABC.NET.

@Sun Serega · 06.10.2019, 21:54

Так вроде работает, и без массива:

Pascal
1
2
3
4
5
6
7
8
9
10
begin
  var coins := ReadInteger;
  var res := 0;
  for var i := 10 downto 1 do
  begin
    var sq := i*i;
    res += System.Math.DivRem(coins,sq,coins);
  end;
  res.Println;
end.

Однако раз есть такой сложный алгоритм... Моё решение что то не учитывает?

Добавлено через 1 минуту
А вообще при чём тут графы?

ФедосеевПавел · 06.10.2019, 22:10

Sun Serega, задача напоминает графы, т.к. получается, что каждое число - вершина графа, а попасть из вершины графа можно не в любую, а только в некоторые. Так из числа 7 напрямую можно перейти в 8, 11, 16 и т.д. Т.е. существует связанность вершин. Если назначить цену перемещения в 1, то получается задача минимизации стоимости пути от 1 до Coins, к которой применим алгоритм Дейкстры.

Т.к. особенность задачи позволяет не определять весовую матрицу смежности, то обходимся без неё.

Что учитывается, а что нет - можно прогнать в цикле Coins от 1 до 100 и сравнить результаты.

@Sun Serega · 06.10.2019, 22:20

А, таким мой неправильный. На 12, к примеру, выдаёт 3х3+1х1+1х1+1х1, хотя можно 2х2+2х2+2х2.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@AG_1337 0 / 0 / 0 Регистрация: 06.10.2019 Сообщений: 1

	Как написать программу 06.10.2019, 20:36. Показов 1880. Ответов 4 Метки нет (Все метки) Уран наконец-то освоен! МОЗГу удалось и на этой мертвой планете поставить нужные преобразователи. Теперь на этой планете можно проводить некоторое время без вреда для здоровья. Чем и решили воспользоваться межпланетные туристические фирмы. Одна из них - «С нами хоть на Луну» - решила потратить весь свой фонд на покупку квадратных участков на Уране. Дабы не потерять в прибыли — нужно потратить весь фонд до монеты, а чтобы иметь меньше проблем с Межпланетной налогово-таможенной службой, было бы здорово купить наименьшее количество участков. Цена 1 кв.м. планеты - 1 монета. Помогите решить проблему турфирмы. Формат входного файла В единственной строке задано одно число — количество монет в фонде турфирмы. Количество монет не превышает 100. Формат выходного файла Выведите минимальное количество квадратных участков, которое можно купить, потратив все деньги. Пояснение к примеру 15 = 3 * 3 + 2 * 2 + 1 * 1 + 1 * 1 0

ФедосеевПавел Модератор 8644 / 4479 / 1669 Регистрация: 01.02.2015 Сообщений: 13,883 Записей в блоге: 11
	06.10.2019, 22:10
	Sun Serega, задача напоминает графы, т.к. получается, что каждое число - вершина графа, а попасть из вершины графа можно не в любую, а только в некоторые. Так из числа 7 напрямую можно перейти в 8, 11, 16 и т.д. Т.е. существует связанность вершин. Если назначить цену перемещения в 1, то получается задача минимизации стоимости пути от 1 до Coins, к которой применим алгоритм Дейкстры. Т.к. особенность задачи позволяет не определять весовую матрицу смежности, то обходимся без неё. Что учитывается, а что нет - можно прогнать в цикле Coins от 1 до 100 и сравнить результаты. 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	06.10.2019, 22:20
	А, таким мой неправильный. На 12, к примеру, выдаёт 3х3+1х1+1х1+1х1, хотя можно 2х2+2х2+2х2. 0

Как написать программу

Решение