«Печать строк»
Сергей очень любит играть в такую игру: произвольным способом выбирает два натуральных числа
N(1≤N≤100) и M (1≤M≤100).
Создается строка символов, в которых подряд выписываются числа: сначала одна 1, потом две 2, потом три 3 и так далее до N. Например, для N=5 полученная строка такая: 122333444455555. Потом полученная строка записывается в несколько строк по M символов в строке. Последняя строка может быть неполной длинны. Например, предыдущая строка для М=3 будет иметь вид:
Нужно написать программу, которая освободит Сергея от подобного времяпрепровождения.
Входные данные: LINE.DAT в одной строке входного файла заданы два числа N и М, которые не превышают 100 и разделены пробелом.
Выходные данные: LINE.SOL в каждой строке выходного файла должно содержаться по М символов из полученной N строки. Последняя строка может быть неполной.
LINE.DAT | LINE.SOL |
5 3 |
Var
n, m, i, j: byte;{n - количество символов, используемых в строке, m-количество символов в одной строке вывода, i,j - переменные для счетчика цикла}
|
|
s, x: string;{s - строка символов, x - очередной символ строки}
Begin
assign(input, 'LINE.dat');{связываем входной файл и файловую переменную}
reset(input);{открываем файл для чтения}
readln(n, m);{считываем входные данные}
close(Input);{закрываем входной файл}
assign(Output,'LINE.sol');{связываем выходной файл и файловую переменную}
rewrite(Output);{открываем файл для записи}
s:='';{обнуляем строку}
for i:=1 to n do {перечисляем цифры для формирования строки}
for j:=1 to i do {перечисляем количество каждой отдельной цифры}
Begin
str(i,x); {переводим цифру в строку}
s:=s+x;{записываем символы в строку}
while Length(s)>=m do {выводим до тех пор пока длина строки не станет меньшей M}
Begin
writeln(Copy(s,1,m));{копируем и выводим m-символов}
delete(s,1,m);{удаляем в исходной строке m символов}
end;
end;
if length(s)>0 then writeln(s);{выводим последние символы в файл}
close(Output);{закрываем файл}
end.
Тема: М етод перебора вариантов, отсечение перебора
Задача «Вырубка деревьев»
Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет N деревьев, расстояния между соседними деревьями одинаковы.
После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.
Входные данные
Входной файл INPUT.TXT содержит два целых числа M и N (0 <= M <= N <= 1000).
Выходные данные
В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов.
Комментарии
Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубки некоторых из N деревьев так, чтобы после вырубки осталось M деревьев и соседние деревья находились на равном расстоянии друг от друга.
|
|
Примечания
Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.
Если у нас есть 0 деревьев и 0 деревьев должно остаться после вырубки, то существует один вариант вырубки - это надо учитывать при решении задачи.
INPUT.TXT | OUTPUT.TXT |
5 3 |
Progpam 111;
Var
n, m: longint;
i, d, s: longint;
input, output: text;
Begin
Assign(input,'input.txt');
Reset(input);
Read (input, n, m);
Close(input);
s:=0;
if m = 0 then
s:=1
Else
if m = 1 then
s:= n
Else
for d:= 1 to (n-1) div (m-1) do
inc(s,n-(m-1)*d);
Assign(output,'output.txt');
Rewrite(output);
Write(output,s);
Close(output);
end.