Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Помогите решить задачу. Индикатор
Автор: ForesTop 5.11.2010 16:10
Помогите решить задачу.
Задача Индикатор.
Лимит времени 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.
Моя программа очень долго выполняется и выдаёт ошибки. Помогите пожалуйста разобраться!
Автор: Archon 5.11.2010 19:48
Ты предлагаешь нам увлекательную игру "попробуй угадай за что отвечают эти однобуквенные переменные"? Нет уж, спасибо.
Первым делом объясни на словах свой алгоритм решения. Возможно ошибки именно в нём.
Автор: ForesTop 5.11.2010 20:02
Сначала я забиваю в массив кол-во чёрных палок для каждого числа! - Это должно быть понятно.
Потом математическим путём получаю число состоящее из считанных кол-ва цифр, и заодно получаю конечное максимальное число с считанным кол-во цифр. В примере такие числа получаю - 10000 и 99999.
Потом проверяю если кол-во палок меньше чем кол-во цифр, то есть если не получится числа, то вывожу надпись NO SOLUTION.
Дальше перевожу начальное число в строку.
И вхожу в цикл.
Потом в цикле считываю каждую цифру строки, и складываю кол-во палок для этой цифры с другими. Тем самым получаю сумму палок числа.
Сравниваю - равна ли эта сумма нужной, в примере 15, и если нет, то увеличиваю число на 1 и перевожу его опять в строку, а если да, то активирую специальную переменную l.
Потом заново вхожу в цикл, но уже с успешной проверкой переменной l, и там её деактивирую и активирую переменную z, но вместо простого числа ставлю конечное - 99999 и уже в цикле буду его уменьшать, а не увеличивать.
И если сумма палок каждой цифры полученного числа будет равна нужной, то сохраняю это число, и активирую последнюю переменную d.
Заново вхожу в цикл, и там после успешной проверки переменной d увеличиваю длину строки на 1, тем самым завершаю цикл.
И уже потом вывожу 2 числа - минимальное и максимальное число на дисплее калькулятора с считанным кол-вом чёрных палок, в примере - 15.
Моя программа выдаёт верные результаты лишь в некоторых случаях, а в остальных работает либо долго, либо вместо нормального максимального числа выдаёт 999999, ну и так далее.
Автор: TarasBer 5.11.2010 20:22
> Сначала я забиваю в массив кол-во чёрных палок для каждого числа! - Это должно быть понятно.
Это не обязательно.
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 20:26
А как тогда, если не перебором???
Автор: Archon 5.11.2010 20:29
Используй аналитический алгоритм. Подумай, как бы ты сам решал эту задачу. Без компьютера. Когда сформулируешь алгоритм, попробуй его запрограммировать и отладить.
Автор: ForesTop 5.11.2010 20:35
Используй аналитический алгоритм. Подумай, как бы ты сам решал эту задачу. Без компьютера. Когда сформулируешь алгоритм, попробуй его запрограммировать и отладить.
Да вот чего то не получается не так и никак, потому и прошу помощи.
Автор: Archon 5.11.2010 21:28
Тогда приведу свой вариант нахождения минимального числа. Попробуй по аналогии написать программу нахождения максимального. Суть алгоритма постарался передать в комментариях. Тем не менее, если что-то окажется не ясно, не стесняйся задавать вопросы.
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.
Автор: ForesTop 5.11.2010 22:25
Вот попробовал написать для максимального числа, вроде работает:
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.
Автор: Archon 5.11.2010 22:51
Попробуй входные данные n = 5, k = 11.
Автор: ForesTop 5.11.2010 22:57
А так???
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.
Автор: Archon 5.11.2010 23:02
n = 5, k = 13 
Автор: ForesTop 5.11.2010 23:08
Попробуй теперь, поправил в предыдущем коде, заменил некоторые значения для кол-ва палок.
Автор: Archon 5.11.2010 23:28
Все равно неправильно. Ответ для n = 5, k = 13 должен быть 77711.
Автор: ForesTop 5.11.2010 23:29
Тогда подскажите, где у меня ошибка?
Автор: Archon 5.11.2010 23:42
Ошибка в том, что твой алгоритм дает неправильный ответ. Конечно, я могу показать свое решение, но какой тогда смысл в решении олимпиадных задач для тебя?
Автор: ForesTop 5.11.2010 23:45
Согласен, но я не прошу показать мне Ваше решение, мне всего лишь нужна небольшая подсказка, где я и что делаю не правильно!
Автор: Archon 5.11.2010 23:56
Я бы и рад так поступить, но не могу указать на недочеты в твоем алгоритме, потому что не понимаю его идеи.
Начало вроде понятно, но вот этот кусок выглядит бездумным копипастом из моей программы:
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 мин.
Поясню, что в моем цикле (при поиске минимума) я должен распределить оставшиеся полоски так, что-бы число увеличилось как можно меньше. Для этого я должен оставить как можно больше разрядов слева нетронутыми. Поэтому я стараюсь заполнить разряды справа таким образом, что-бы потратить как можно больше полосок. В этом и есть основная идея кода.
Автор: ForesTop 6.11.2010 0:09
Соглашусь и с этим, это не только выглядит, но и самый что ни на есть копипаст бездумный, потому как я даже не представляю себе, как таким методом решить поставленную задачу, я с таким ещё пока не сталкивался, поэтому пытался каким-нибудь способом примудрить этот кусок кода в своём решении.
P.S.: Пока писал Вы уже ответили на мой вопрос, спасибо за разъяснение, буду думать дальше.
Автор: Archon 6.11.2010 0:18
Я потому и просил спрашивать, если мой алгоритм не понятен.
Автор: ForesTop 6.11.2010 0:39
Вот попробовал написать, но чего - то не получается, подскажите, может чего-то не так делаю?
var
n, k, i, j: Integer;
s: String;
begin
ReadLn(n, k);
j := k;
if k < n * 2 then
WriteLn('NO SOLUTION')
else begin
SetLength(s, n);
for i := 1 to n do
s[i] := '1';
k := k - (n * 2);
i := 2;
while (i <= n) and (k >= 4) do begin
s[i] := '0';
k := k - 4;
end;
i := n;
while (i >= 0) 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;
'0': begin
s[i] := '8';
k := k - 1;
end;
end;
i := i - 1;
end;
if k <> 0 then
writeln('NO SOLUTION')
else begin
writeln(s);
for i := 1 to n do
s[i] := '9';
k := j;
k := k - (n * 6);
i := n;
while (i <= n) and (k <= 1) do begin
s[i] := '1';
k := k + 4;
i := i-1;
end;
i := i + 1;
while (i <= n) and (k > 0) do begin
if k <= 3 then begin
s[i] := '7';
k := k - 1;
end else begin
s[i] := '9';
k := k - 4;
end;
i := i + 1;
end;
writeln(s);
end;
end;
readln;
end.
Автор: Archon 6.11.2010 1:06
Ну снова, было бы неплохо пояснять, что именно ты делаешь.
Автор: ForesTop 6.11.2010 1:20
Попробовал получить максимальное число методом перебора:
const a: array [0 .. 9] of integer = (6, 2, 5, 5, 4, 5, 6, 3, 7, 6);
var
n, k, i, j, n2, l: Integer;
s, c: String;
begin
ReadLn(n, k);
j := k;
if k < n * 2 then
WriteLn('NO SOLUTION')
else begin
SetLength(s, n);
for i := 1 to n do
s[i] := '1';
k := k - (n * 2);
i := 2;
while (i <= n) and (k >= 4) do begin
s[i] := '0';
k := k - 4;
end;
i := n;
while (i >= 0) 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;
'0': begin
s[i] := '8';
k := k - 1;
end;
end;
i := i - 1;
end;
if k <> 0 then
writeln('NO SOLUTION')
else begin
writeln(s);
k := j; s := ''; n2 := n;
for i := 1 to n do
for j := 9 downto 1 do begin
l := k - a[j];
if (2*(n2-1) <= l) and (l <= 7*(n2-1)) then begin
str(j, c);
s := s + c;
k := k - a[j];
n2 := n2 - 1;
break;
end;
end;
writeln(s);
end;
end;
readln;
end.
Программа перебирает все возможные цифры для числа, да так чтобы их ещё хватало. Короче я не много продумал этот момент, но всё равно врёт, работает, но неправильно.
Совет дайте дельный, не надо комменты типа "думай ещё", уже и так всё перевыдумал, я школьник, научите, может чего не знаю ещё, учитель информатики мало объясняет, мне его объяснений не достаточно, что бы решать задания такого уровня до всего приходиться доходить самому, а в книжках большинство невнятный бред. Если есть очевидные ошибки, укажите что не так.
Короче Help!
Автор: ForesTop 6.11.2010 4:58
Всем спасибо, вот решение методом перебора цифр для каждого числа.
const cnt: array[0..9]of Integer = (6, 2, 5, 5, 4, 5, 6, 3, 7, 6);
var
n, k : integer;
i : integer;
j : integer;
max, min : string;
st : integer;
ck, nk : integer;
cn : integer;
begin
readln(n, k);
if (k < 2 * n) or (k > 7 * n) then begin
writeln('NO SOLUTION');
halt(0);
end;
min := '';
ck := k;
cn := n;
for i := 1 to n do begin
st := 0;
if (i = 1) then begin
st := 1;
end;
for j := st to 9 do begin
nk := ck - cnt[j];
if (nk >= 2 * (cn - 1)) and (nk <= 7 * (cn - 1)) then begin
min := min + chr(ord('0') + j);
ck := nk;
cn := cn - 1;
break;
end;
end;
end;
max := '';
ck := k;
cn := n;
for i := 1 to n do begin
st := 0;
if (i = 1) then begin
st := 1;
end;
for j := 9 downto st do begin
nk := ck - cnt[j];
if (nk >= 2 * (cn - 1)) and (nk <= 7 * (cn - 1)) then begin
max := max + chr(ord('0') + j);
ck := nk;
cn := cn - 1;
break;
end;
end;
end;
writeln(min);
writeln(max);
readln;
end.
Автор: Archon 6.11.2010 13:25
Хорошее решение. И главное, самостоятельное =)