Помогите решить задачу. Индикатор |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Помогите решить задачу. Индикатор |
ForesTop |
5.11.2010 12:10
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
Помогите решить задачу.
Задача Индикатор. Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Недавно Вася приобрёл калькулятор с жидкокристаллическим индикатором. Этот индикатор отображает N цифр с помощью N одинаковых элементов. Отметим, что каждый элемент содержит семь полосок, каждая из которых может быть либо белой, либо чёрной. В частности при отображении цифры "1" чёрными являются две полоски. Вася - очень любознательный мальчик, поэтому он хочет узнать, какое максимальное и минимальное N-значные числа могут быть отображены на индикаторе его нового калькулятора так, чтобы черными были ровно k полосок. Напишите программу, которая найдёт ответ на Васин вопрос. Учитывайте при этом, что числа не могут содержать ведущие нули. Входные данные: два целых числа: N и k (1<=N<=100, 1<=k<=700). Выходные данные: В первой строке - минимальное число, во второй строке - максимальное число. Если указанным образом не может быть представлено ни одно число, выходной файл должен содержать одну строку NO SOLUTION. Пример 1. на входе: 5 15 на выходе: 10117 97111 Пример 2. на входе: 10 1 на выходе: NO SOLUTION Мой вариант решения (не работает):
Моя программа очень долго выполняется и выдаёт ошибки. Помогите пожалуйста разобраться! Сообщение отредактировано: ForesTop - 5.11.2010 15:32 |
Archon |
5.11.2010 15:48
Сообщение
#2
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Ты предлагаешь нам увлекательную игру "попробуй угадай за что отвечают эти однобуквенные переменные"? Нет уж, спасибо.
Первым делом объясни на словах свой алгоритм решения. Возможно ошибки именно в нём. -------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 16:02
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
Сначала я забиваю в массив кол-во чёрных палок для каждого числа! - Это должно быть понятно.
Потом математическим путём получаю число состоящее из считанных кол-ва цифр, и заодно получаю конечное максимальное число с считанным кол-во цифр. В примере такие числа получаю - 10000 и 99999. Потом проверяю если кол-во палок меньше чем кол-во цифр, то есть если не получится числа, то вывожу надпись NO SOLUTION. Дальше перевожу начальное число в строку. И вхожу в цикл. Потом в цикле считываю каждую цифру строки, и складываю кол-во палок для этой цифры с другими. Тем самым получаю сумму палок числа. Сравниваю - равна ли эта сумма нужной, в примере 15, и если нет, то увеличиваю число на 1 и перевожу его опять в строку, а если да, то активирую специальную переменную l. Потом заново вхожу в цикл, но уже с успешной проверкой переменной l, и там её деактивирую и активирую переменную z, но вместо простого числа ставлю конечное - 99999 и уже в цикле буду его уменьшать, а не увеличивать. И если сумма палок каждой цифры полученного числа будет равна нужной, то сохраняю это число, и активирую последнюю переменную d. Заново вхожу в цикл, и там после успешной проверки переменной d увеличиваю длину строки на 1, тем самым завершаю цикл. И уже потом вывожу 2 числа - минимальное и максимальное число на дисплее калькулятора с считанным кол-вом чёрных палок, в примере - 15. Моя программа выдаёт верные результаты лишь в некоторых случаях, а в остальных работает либо долго, либо вместо нормального максимального числа выдаёт 999999, ну и так далее. |
TarasBer |
5.11.2010 16:22
Сообщение
#4
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> Сначала я забиваю в массив кол-во чёрных палок для каждого числа! - Это должно быть понятно.
Это не обязательно. const A: array [0 .. 9] of integer = (6, 2, 5, 5, 4, 5, 6, 3, 7, 6); > Потом математическим путём получаю число Какой тип данных ты будешь использовать для хранения 100-значного числа? Надо сразу работать только со строками. > var number: array[1..200000000]of LongInt; 800 Мегабайт?! В уловии другое ограничение. > Сравниваю - равна ли эта сумма нужной, в примере 15, и если нет, то увеличиваю число на 1 и перевожу его опять в строку, а если да, то активирую специальную переменную l. Перебор?! По 100-значным числам?! -------------------- |
ForesTop |
5.11.2010 16:26
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
А как тогда, если не перебором???
|
Archon |
5.11.2010 16:29
Сообщение
#6
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Используй аналитический алгоритм. Подумай, как бы ты сам решал эту задачу. Без компьютера. Когда сформулируешь алгоритм, попробуй его запрограммировать и отладить.
-------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 16:35
Сообщение
#7
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
|
Archon |
5.11.2010 17:28
Сообщение
#8
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Тогда приведу свой вариант нахождения минимального числа. Попробуй по аналогии написать программу нахождения максимального. Суть алгоритма постарался передать в комментариях. Тем не менее, если что-то окажется не ясно, не стесняйся задавать вопросы.
var Сообщение отредактировано: Archon - 5.11.2010 17:43 -------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 18:25
Сообщение
#9
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
Вот попробовал написать для максимального числа, вроде работает:
Сообщение отредактировано: ForesTop - 5.11.2010 18:31 |
Archon |
5.11.2010 18:51
Сообщение
#10
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Попробуй входные данные n = 5, k = 11.
-------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 18:57
Сообщение
#11
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
А так???
var Сообщение отредактировано: ForesTop - 5.11.2010 19:07 |
Archon |
5.11.2010 19:02
Сообщение
#12
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
n = 5, k = 13
-------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 19:08
Сообщение
#13
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
Попробуй теперь, поправил в предыдущем коде, заменил некоторые значения для кол-ва палок.
|
Archon |
5.11.2010 19:28
Сообщение
#14
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Все равно неправильно. Ответ для n = 5, k = 13 должен быть 77711.
Сообщение отредактировано: Archon - 5.11.2010 19:35 -------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 19:29
Сообщение
#15
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
Тогда подскажите, где у меня ошибка?
Сообщение отредактировано: ForesTop - 5.11.2010 19:33 |
Archon |
5.11.2010 19:42
Сообщение
#16
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Ошибка в том, что твой алгоритм дает неправильный ответ. Конечно, я могу показать свое решение, но какой тогда смысл в решении олимпиадных задач для тебя?
-------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 19:45
Сообщение
#17
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
Согласен, но я не прошу показать мне Ваше решение, мне всего лишь нужна небольшая подсказка, где я и что делаю не правильно!
|
Archon |
5.11.2010 19:56
Сообщение
#18
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Я бы и рад так поступить, но не могу указать на недочеты в твоем алгоритме, потому что не понимаю его идеи.
Начало вроде понятно, но вот этот кусок выглядит бездумным копипастом из моей программы: i := 1; { Начинаем цикл со первого числа, для опять таки достижения макимально возможного числа } Добавлено через 13 мин. Поясню, что в моем цикле (при поиске минимума) я должен распределить оставшиеся полоски так, что-бы число увеличилось как можно меньше. Для этого я должен оставить как можно больше разрядов слева нетронутыми. Поэтому я стараюсь заполнить разряды справа таким образом, что-бы потратить как можно больше полосок. В этом и есть основная идея кода. Сообщение отредактировано: Archon - 5.11.2010 19:57 -------------------- Close the World...txeN eht nepO
|
ForesTop |
5.11.2010 20:09
Сообщение
#19
|
Новичок Группа: Пользователи Сообщений: 23 Пол: Мужской Реальное имя: Влад Репутация: 0 |
Соглашусь и с этим, это не только выглядит, но и самый что ни на есть копипаст бездумный, потому как я даже не представляю себе, как таким методом решить поставленную задачу, я с таким ещё пока не сталкивался, поэтому пытался каким-нибудь способом примудрить этот кусок кода в своём решении.
P.S.: Пока писал Вы уже ответили на мой вопрос, спасибо за разъяснение, буду думать дальше. Сообщение отредактировано: ForesTop - 5.11.2010 20:11 |
Archon |
5.11.2010 20:18
Сообщение
#20
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Я потому и просил спрашивать, если мой алгоритм не понятен.
-------------------- Close the World...txeN eht nepO
|
Текстовая версия | 20.09.2024 6:08 |