Задача со спичками

@Игорь2001 · Регистрация: 19.05.2015

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

Дано N спичек
Надо выложить из них минимальное и максимальное число
Название: b.png
Просмотров: 79

Размер: 4.1 Кб

Нули в начале запрещены
Помогите, куда двигаться, как примерно решать?

@Excalibur921 · 10.11.2016, 19:46

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

Берете каждую цифру, сколько спичек в ней. Продумываете какое мин и макс число можно из них собрать. Комбинируете получаете два числа…

Это наверно комбинаторика хоть и в извращенной форме =).

@Игорь2001 · 10.11.2016, 19:53 **[ТС]**

Это - первое, о чем я подумал
Вот что я написал перед началом работы
// 2 - 1
// 3 - 7
// 4 - 4
// 5 - 2, 3, 5
// 6 - 0, 6, 9
// 7 - 8

Но прикол в том, что просто выбирать минимальные числа, то получится, что, например, из 4 спичек можно составить 11, хотя в действительноти можно и меньше - 7

@Excalibur921 · 10.11.2016, 21:25

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

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

Переставить спички в каждом символе так чтобы было max min.
Сначала классифицируем сколько спичек в символе.
0-6с
1-2с
2-5с
3-5с
4-4с
5-5с
6-6с
7-3с
8-7с
9-6с

Допустимые комбинации в символе:
0-6с 0-6с, 6-6с, 9-6с
1-2с
2-5с 2-5с 3-5с 5-5с
3-5с 2-5с 3-5с 5-5с
4-4с
5-5с 2-5с 3-5с 5-5с
6-6с 0-6с 6-6с 9-6с
7-3с
8-7с
9-6с 0-6с 6-6с 9-6с
Выбираем min:
0-6с 0-6с,
1-2с
2-5с 2-5с
3-5с 2-5с
4-4с
5-5с 2-5с
6-6с 0-6с
7-3с
8-7с
9-6с 0-6с
Значит: 0122420780
Ноль нельзя первый: 6122420780
Max:
0-6с 9-6с
1-2с
2-5с 5-5с
3-5с 5-5с
4-4с
5-5с 5-5с
6-6с 9-6с
7-3с
8-7с
9-6с 9-6с
Значит: 9155459789

Min: 6 122 420 780
Max: 9 155 459 789

@Игорь2001 · 10.11.2016, 21:55 **[ТС]**

Не понял практически ничего.

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

0-6с 0-6с, 6-6с, 9-6с
1-2с
2-5с 2-5с 3-5с 5-5с
3-5с 2-5с 3-5с 5-5с
4-4с
5-5с 2-5с 3-5с 5-5с
6-6с 0-6с 6-6с 9-6с
7-3с
8-7с
9-6с 0-6с 6-6с 9-6с

Почему числа повторяются?

@Excalibur921 · 10.11.2016, 22:17

Так наглядней. Ответ какой?

@Sergio Leone · 10.11.2016, 22:57

Сообщение от Игорь2001

Не понял практически ничего.

ты не одинок, я тоже из рассуждений мало что уловил...

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

Ответ какой?

какой ответ?
челу нужен алгоритм, как по заданному числу спичек N найти минимальное число и максимальное число.

ну, например,
ему говорят, дано N=4
он отвечает.
минимальное число, которое можно сложить из 4-х спичек - это 4
а максимальное число, которое можно сложить из 4-х спичек - это 11

Игорь2001, а ограничение на N есть?
я бы решал эту задачу через рекурсивный вызов, но не факт, что это самый эффективный вариант.

@Игорь2001 · 10.11.2016, 23:20 **[ТС]**

Сообщение от Sergio Leone

а ограничение на N есть?

От двух до 2 000 000 000
С трудом в инт влезает))
рекурсия не катит, стек забьет, даже если одними восьмерками оперировать, получим 250 000 000 рекурсивных вызовов...

@Excalibur921 · 10.11.2016, 23:25

Сообщение от Игорь2001

Почему числа повторяются?

А если так?
0-6с 0-6с, 6-6с, 9-6с
Значит из спичек символа 0 использующего 6 спичек можно сложить символы 0,6,9 исп. 6 спичек каждый.
2-5с 2-5с 3-5с 5-5с
Из спичек символа 2 можно сложить 2,3,5.
Задание на спичек подразумевает вообще визуальное решение.

@Sergio Leone · 10.11.2016, 23:27

Сообщение от Игорь2001

рекурсия не катит, стек забьет

да, при таких ограничениях, согласен, рекурсия не выход.

надо прогнать программу перебором (ну, скажем, для N=100), посмотреть варианты,
из этих вариантов выводить аналитическую формулу, думаю, что там будут повторы по определённому правилу...

Добавлено через 1 минуту
Excalibur921, ты о чём? У меня такое впечатление, что ты какую-то другую, свою задачу решаешь!

@Игорь2001 · 10.11.2016, 23:31 **[ТС]**

Сообщение от Sergio Leone

надо прогнать программу перебором (ну, скажем, для N=100), посмотреть варианты,
из этих вариантов выводить аналитическую формулу, думаю, что там будут повторы по определённому правилу...

Для N = 100 надо перебрать очень много значений, ибо даже у, например 10 спичек очень много вариантов
11111
747
477
774
69
96.........

Добавлено через 30 секунд
Если число четное, максимальным будет N/2 единиц подряд

Добавлено через 15 секунд
Это я нашел еще до того, как сюда написал

@Sergio Leone · 10.11.2016, 23:45

Сообщение от Игорь2001

Для N = 100 надо перебрать очень много значений, ибо даже у, например 10 спичек очень много вариантов

Ты что, вручную их перебирать собрался?

Ты не поверишь. Компьютер может обрабатывать миллионы вариантов в секунду.
А нас интересует только результат: какое число для заданного числа спичек можно собрать минимальное и какое максимальное.
в виде
N=2 min=1 max=1
N=3 min=7 max=7
N=4 min=4 max=11
и т.д.

Ну вот видишь, ты уже и начал эту аналитическую формулу выводить!

Сообщение от Игорь2001

Если число четное, максимальным будет N/2 единиц подряд

согласен.
а для нечётного - 7 и (N-3)/2 единиц подряд

так с максимальным разобрались.

а что делать с минимальным?

@Excalibur921 · 10.11.2016, 23:45

Сообщение от Sergio Leone

свою задачу решаешь

Точно свою =)). И ответ никто не проверил(.

1)Почему задача с комбинаторики не в форуме комбинаторика?
2)Зачем абстракция со спичками?
3) Изначальная задача что? Может вообще подход не правильный.
4)Кажется такая формулировка задания отпугнет 90% экспертов.

@Sergio Leone · 10.11.2016, 23:48

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

Зачем абстракция со спичками?

Какая комбинаторика? Какая абстракция?
Это и есть задача такая. Вот прямо как на канале с лохотронами!
Даны спички. Из них можно складывать цифры по заданному образцу.
Требуется установить какое минимальное и какое максимальное число можно сложить из заданного количества спичек.

@Игорь2001 · 10.11.2016, 23:54 **[ТС]**

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

Почему задача с комбинаторики не в форуме комбинаторика?

Я не знал , что это комбинаторика

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

Зачем абстракция со спичками?

Такое задание

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

Кажется такая формулировка задания отпугнет 90% экспертов.

Если я напишу оригинал он отпугнет минимум тех, кто не знает украинского. Таких тут, пожалуй, много

Добавлено через 45 секунд

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

Кажется такая формулировка задания отпугнет 90% экспертов.

Гра із сірниками
Степан вирішив кинути палити і щоб не думати про цигарки придумав гру із сірниками. У нього є дві коробки сірників по N штук у кожній. Він хоче викласти із сірників однієї коробки якомога більше число, а іншої — якомога менше число, причому він хоче використати усі сірники. Допоможіть Степану. Те, як з сірників викладаються цифри, ви можете подивитися на рисунку, наведеному нижче. Врахуйте, що Степан знає, що ставити на початок чисел нулі не можна.

Вхідні дані:
У першому рядку вхідного файлу задано натуральне числоN (2 ≤ N ≤ 2 000 000 000).
Вихідні дані:
У вихідний файл через пробіл виведіть два числа: найбільше і найменше натуральні числа, які може викласти Степан, витративши рівно N сірників на кожне з чисел.
Примеры
Входные данные
5
Результат работы
71 2

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

Сообщение от Sergio Leone

Ты не поверишь. Компьютер может обрабатывать миллионы вариантов в секунду.

Спасибо, я в курсе

@Sergio Leone · 10.11.2016, 23:57

Игорь2001, ты согласен, что половина задачи (нахождение максимального числа) уже тут решена?
Осталось придумать, по какой формуле найти минимальное и дело в шляпе!

@Игорь2001 · 11.11.2016, 00:08 **[ТС]**

Сообщение от Sergio Leone

надо прогнать программу перебором (ну, скажем, для N=100)

Для этого тоже надо алгоритм придумать)))
Если бы не было спичек, на нормальные числа....

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

Сообщение от Sergio Leone

ты согласен

более или менее, уточнить только, откуда 2-я ф-ла?

Добавлено через 8 минут
А для минимального числа будет по-идее минимальное число из остачи деления на 8 и ряд восьмерок в количестве целочисленного деления на 8

@Sergio Leone · 11.11.2016, 00:14

Сообщение от Игорь2001

более или менее, уточнить только, откуда 2-я ф-ла?

ты про поиск максимального?
если N - чётное, то ответ (N/2) единиц
если N - нечётное, то ответ "7" + ((N-3)/2) единиц (N-3 - это отнимаем от N три спички, из них складывает "7"ку, а из оставшихся спичек выкладываем единицы подряд.

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

Сообщение от Игорь2001

А для минимального числа будет по-идее минимальное число из остачи деления на 8 и ряд восьмерок в количестве целочисленного деления на 8

а вот в этом я не уверен.

ну, для начала нужно исключить начальные значения N (для них сразу задать таблицу):
N Min
2 1
3 7
4 4
5 2
6 6
7 8
8 10
9 18
10 22
11 20
12 28
13 68

а вот дальше надо выводить формулу.

если сам не придумаешь (и никто не подскажет), то, сорри, я только завтра вечером тут буду...

@Shamil1 · 11.11.2016, 00:36

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string Solve(int n)
{
    if (n < 2) return null;
    int d = n / 7;
    int r = n % 7;
    if (r == 1) d -= 1;
    string tail = new string('8', d);
    switch (r)
    {
        case 1: return "10" + tail;
        case 2: return "1" + tail;
        case 3: return "7" + tail;
        case 4: return "4" + tail;
        case 5: return "2" + tail;
        case 6: return "6" + tail;
        default: return tail;
    }
}

@Игорь2001 · 11.11.2016, 11:31 **[ТС]**

Я примерно так и реализовал вою идею

C++
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
26
void minimum(int count) {
    int n = count % 7;
    switch (n){
    case 1: cout << 18;
        break;
    case 2: cout << 1;
        break;
    case 3: cout << 7;
        break;
    case 4: cout << 4;
        break;
    case 5: cout << 2;
        break;
    case 6: cout << 6;
        break;
    }
    if (n == 1) {
        count -= 8;
    }
    else {
        count -= n;
    }
    for (int i = 0; i < count / 7; i++) {
        cout << 8;
    }
}

Проходит не все тесты

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@Игорь2001 20 / 20 / 10 Регистрация: 19.05.2015 Сообщений: 704

	Задача со спичками 10.11.2016, 18:56. Показов 5481. Ответов 25 Метки нет (Все метки) Дано N спичек Надо выложить из них минимальное и максимальное число Нули в начале запрещены Помогите, куда двигаться, как примерно решать? 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	10.11.2016, 19:46
	Почему то вспомнились лохотроны по телику когда то шли ночью. Берете каждую цифру, сколько спичек в ней. Продумываете какое мин и макс число можно из них собрать. Комбинируете получаете два числа… Это наверно комбинаторика хоть и в извращенной форме =). 0

@Игорь2001 20 / 20 / 10 Регистрация: 19.05.2015 Сообщений: 704
	10.11.2016, 19:53 [ТС]
	Это - первое, о чем я подумал Вот что я написал перед началом работы // 2 - 1 // 3 - 7 // 4 - 4 // 5 - 2, 3, 5 // 6 - 0, 6, 9 // 7 - 8 Но прикол в том, что просто выбирать минимальные числа, то получится, что, например, из 4 спичек можно составить 11, хотя в действительноти можно и меньше - 7 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	10.11.2016, 22:17
	Так наглядней. Ответ какой? 0

@Sergio Leone 2511 / 1132 / 582 Регистрация: 07.06.2014 Сообщений: 3,286
	10.11.2016, 23:57
	Игорь2001, ты согласен, что половина задачи (нахождение максимального числа) уже тут решена? Осталось придумать, по какой формуле найти минимальное и дело в шляпе! 0