IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Помогите решить задачу. Индикатор
сообщение
Сообщение #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


Мой вариант решения (не работает):


Program New;
uses crt;
var number: array[1..200000000]of LongInt;
a: array[0..9]of Integer;
n, sum, k, i, c, g, j: Integer;
s: String;
z, l, d: Boolean;
p, save, copy: LongInt;
f: Text;
begin
clrscr;
assign(f, 'input.txt');
reset(f);
read(f, n, k);

a[0]:=6; a[1]:=2; a[2]:=5; a[3]:=5; a[4]:=4; a[5]:=5; a[6]:=6; a[7]:=3;
a[8]:=7; a[9]:=6;

if (n > k) or (k < n*2) then
write('NO SOLUTION')
else
begin
l:=false;
p:=1;
for i:=1 to n-1 do
p:=p*10;
copy:=p;
save:=0;
for i:=1 to n do
begin
save:=save+(copy*9);
copy:=copy div 10;
end;
str(p, s);
j:=0; l:=false; z:=false; d:=false;
repeat
sum:=0;
if d=true then
s:=s+'1'
else
begin
if l=true then
begin
l:=false;
z:=true;
p:=save;
end;
for i:=1 to n do
begin
val(s[i], g, c);
sum:=sum+a[g];
end;
if sum = k then
begin
if z<>true then
l:=true
else
d:=true;
j:=j+1;
number[j]:=p;
end;
if z=true then
p:=p-1
else
p:=p+1;
str(p, s);
end;
until length(s) > n;
writeln(number[1]);
write(number[2]);
end;

readln;
end.




Моя программа очень долго выполняется и выдаёт ошибки. Помогите пожалуйста разобраться!

Сообщение отредактировано: ForesTop -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
Ответов(1 - 19)
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Ты предлагаешь нам увлекательную игру "попробуй угадай за что отвечают эти однобуквенные переменные"? Нет уж, спасибо.

Первым делом объясни на словах свой алгоритм решения. Возможно ошибки именно в нём.


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Сначала я забиваю в массив кол-во чёрных палок для каждого числа! - Это должно быть понятно.
Потом математическим путём получаю число состоящее из считанных кол-ва цифр, и заодно получаю конечное максимальное число с считанным кол-во цифр. В примере такие числа получаю - 10000 и 99999.
Потом проверяю если кол-во палок меньше чем кол-во цифр, то есть если не получится числа, то вывожу надпись NO SOLUTION.
Дальше перевожу начальное число в строку.
И вхожу в цикл.
Потом в цикле считываю каждую цифру строки, и складываю кол-во палок для этой цифры с другими. Тем самым получаю сумму палок числа.
Сравниваю - равна ли эта сумма нужной, в примере 15, и если нет, то увеличиваю число на 1 и перевожу его опять в строку, а если да, то активирую специальную переменную l.
Потом заново вхожу в цикл, но уже с успешной проверкой переменной l, и там её деактивирую и активирую переменную z, но вместо простого числа ставлю конечное - 99999 и уже в цикле буду его уменьшать, а не увеличивать.
И если сумма палок каждой цифры полученного числа будет равна нужной, то сохраняю это число, и активирую последнюю переменную d.
Заново вхожу в цикл, и там после успешной проверки переменной d увеличиваю длину строки на 1, тем самым завершаю цикл.
И уже потом вывожу 2 числа - минимальное и максимальное число на дисплее калькулятора с считанным кол-вом чёрных палок, в примере - 15.
Моя программа выдаёт верные результаты лишь в некоторых случаях, а в остальных работает либо долго, либо вместо нормального максимального числа выдаёт 999999, ну и так далее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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-значным числам?!


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


А как тогда, если не перебором???
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Используй аналитический алгоритм. Подумай, как бы ты сам решал эту задачу. Без компьютера. Когда сформулируешь алгоритм, попробуй его запрограммировать и отладить.


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Цитата(Archon @ 5.11.2010 16:29) *

Используй аналитический алгоритм. Подумай, как бы ты сам решал эту задачу. Без компьютера. Когда сформулируешь алгоритм, попробуй его запрограммировать и отладить.

Да вот чего то не получается не так и никак, потому и прошу помощи.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Тогда приведу свой вариант нахождения минимального числа. Попробуй по аналогии написать программу нахождения максимального. Суть алгоритма постарался передать в комментариях. Тем не менее, если что-то окажется не ясно, не стесняйся задавать вопросы.
var
n, k, i: Integer;
s: String;
begin
ReadLn(n, k);

if k < n * 2 then { Если полосок не хватает для составления n-значного числа, решения нет. }
WriteLn('NO SOLUTION')
else begin
{ За основу возьмем n-значное число из одних единиц. Такое число требует наименьшего
количества полосок. }
SetLength(s, n);
for i := 1 to n do
s[i] := '1';
k := k - n * 2; { Определяем оставшееся количество полосок. }

{ Теперь попробуем уменьшить число, используя оставшиеся полоски. Для этого будем
заменять единицы на нули, начиная со 2-ой цифры, пока цифры не кончатся или полосок
начнет не хватать. }
i := 2;
while (i <= n) and (k >= 4) do begin
s[i] := '0';
k := k - 4;
i := i + 1;
end;

{ Теперь оставшиеся полоски попробуем разместить в числе так, что-бы оно увеличилось
как можно меньше. Для этого будем рассматривать цифры числа начиная с последнего.
Напомню, что число на данном этапе состоит только из нулей и единиц. }
i := n;
while (i >= 1) and (k > 0) do begin
case s[i] of
'1': begin
{ Если текущая цифра - 1, то это значит, что заполнить число нулями до
конца не удалось и полосок осталось меньше 4, ... }
if k = 1 then begin
s[i] := '7';
k := 0;
end else if k = 2 then begin
s[i] := '4';
k := 0;
end else if k = 3 then begin
s[i] := '2';
k := 0;
end else if k = 4 then begin { ... или мы находимся на первой цифре в числе. }
s[i] := '6';
k := 0;
end else begin
s[i] := '8';
k := k - 5;
end;
end;
'0': begin
{ Если текущая цифра - 0, заменяем его на 8, что-бы уменьшить количество
оставшихся полосок. }
s[i] := '8';
k := k - 1;
end;
end;
i := i - 1;
end;

if k <> 0 then { Если полоски после всего еще остались, значит решения нет. }
WriteLn('NO SOLUTION')
else { Если не остались, выводим ответ. }
WriteLn(s);
end;
end.


Сообщение отредактировано: Archon -


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Вот попробовал написать для максимального числа, вроде работает:


var
n, k, i: Integer;
s: String; { Текущее число. }
begin
ReadLn(n, k);

if k < n * 2 then
WriteLn('NO SOLUTION')
else begin

SetLength(s, n);

for i := 1 to n do { Заполняем число девятками, то есть возьмём максимально
возможный результат}
s[i] := '9';

k := k - (n * 6); { Высчитываем кол-во оставшихся полосок, их может быть в минусе }

i:=n; { Начнём цикл с конца числа, для достижения максимально допустимого числа }
while (i <= n) and (k <= 0) do begin
s[i]:='1'; { Будем заполнять число еденицами, для того, что бы выбить число К из минуса }
k := k + 4;
i:=i-1;
end;

i := 2; { Начинаем цикл со второго числа, для опять таки достижения макимально возможного числа }
while (i <= n) and (k > 0) do begin
case s[i] of
'1': if k = 1 then begin
s[i] := '7';
k := 0;
end else if k = 2 then begin
s[i] := '4';
k := 0;
end else if k = 3 then begin
s[i] := '2';
k := 0;
end else if k = 4 then begin
s[i] := '6';
k:=0;
end else begin
s[i] := '8';
k := k - 5;
end;
end;
i := i + 1;
end;

if k <> 0 then
writeln('NO SOLUTION')
else
writeln(s);
end;

readln;
end.



Сообщение отредактировано: ForesTop -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Попробуй входные данные n = 5, k = 11.


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


А так???

var
n, k, i: Integer;
s: String; { Текущее число. }
begin
ReadLn(n, k);

if k < n * 2 then
WriteLn('NO SOLUTION')
else begin

SetLength(s, n);

for i := 1 to n do { Заполняем число девятками, то есть возьмём максимально
возможный результат}
s[i] := '9';

k := k - (n * 6); { Высчитываем кол-во оставшихся полосок, их может быть в минусе }

i:=n; { Начнём цикл с конца числа, для достижения максимально допустимого числа }
while (i <= n) and (k <= 0) do begin
s[i]:='1'; { Будем заполнять число еденицами, для того, что бы выбить число К из минуса }
k := k + 4;
i:=i-1;
end;

i := 1; { Начинаем цикл со первого числа, для опять таки достижения макимально возможного числа }
while (i <= n) and (k > 0) do begin
case s[i] of
'1': if k = 1 then begin
s[i] := '7';
k := 0;
end else if k = 2 then begin
s[i] := '4';
k := 0;
end else if k = 3 then begin
s[i] := '5';
k := 0;
end else if k = 4 then begin
s[i] := '9';
k:=0;
end else begin
s[i] := '8';
k := k - 5;
end;
end;
i := i + 1;
end;

if k <> 0 then
writeln('NO SOLUTION')
else
writeln(s);
end;

readln;
end.



Сообщение отредактировано: ForesTop -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


n = 5, k = 13 smile.gif


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Попробуй теперь, поправил в предыдущем коде, заменил некоторые значения для кол-ва палок.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Все равно неправильно. Ответ для n = 5, k = 13 должен быть 77711.

Сообщение отредактировано: Archon -


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Тогда подскажите, где у меня ошибка?

Сообщение отредактировано: ForesTop -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Ошибка в том, что твой алгоритм дает неправильный ответ. Конечно, я могу показать свое решение, но какой тогда смысл в решении олимпиадных задач для тебя?


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Согласен, но я не прошу показать мне Ваше решение, мне всего лишь нужна небольшая подсказка, где я и что делаю не правильно!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

Начало вроде понятно, но вот этот кусок выглядит бездумным копипастом из моей программы:
                i := 1; { Начинаем цикл со первого числа, для опять таки достижения макимально возможного числа }
while (i <= n) and (k > 0) do begin
case s[i] of
'1': if k = 1 then begin
s[i] := '7';
k := 0;
end else if k = 2 then begin
s[i] := '4';
k := 0;
end else if k = 3 then begin
s[i] := '5';
k := 0;
end else if k = 4 then begin
s[i] := '9';
k:=0;
end else begin
s[i] := '8';
k := k - 5;
end;
end;
i := i + 1;
end;


Добавлено через 13 мин.
Поясню, что в моем цикле (при поиске минимума) я должен распределить оставшиеся полоски так, что-бы число увеличилось как можно меньше. Для этого я должен оставить как можно больше разрядов слева нетронутыми. Поэтому я стараюсь заполнить разряды справа таким образом, что-бы потратить как можно больше полосок. В этом и есть основная идея кода.

Сообщение отредактировано: Archon -


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


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

P.S.: Пока писал Вы уже ответили на мой вопрос, спасибо за разъяснение, буду думать дальше.

Сообщение отредактировано: ForesTop -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Я потому и просил спрашивать, если мой алгоритм не понятен.


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 3:08
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name