Тема 5: Строки. Элементы лексического и синтаксического разобра

 

«Печать строк»

Сергей очень любит играть в такую игру: произвольным способом выбирает два натуральных числа

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.

 

 

Тема: Сортировка и выбор

Условие задачи: Для игры в квидич используются мячи - снитчи. Проблема заключается в том, что они разного размера. Для проведения матча требуется выбрать снитч нужного веса. Перед началом матча все снитчи выстраиваются в ряд в порядке неубывания весов и Гарри Поттер должен как можно быстрее найти снитч с весом ровно Х кг или сообщить судье об отсутствии нужного мяча.

Формат входных данных:

В первой строке входного файла записаны через пробел два целых числа N и X. В следующих N строках записаны веса мячей в порядке неубывания (по одному числу в строке). Веса – целые числа, не превосходящие 100, 0<N£50000.

Формат выходных данных:

В выходной файл вывести номер снитча, имеющего вес X или число 0, если такого снитча нет.

Лимит времени: 1 секунда на тест.

Пример:

INPUT. TXT	OUTPUT.TXT
5 3

Указания к решению. Очевидное решение состоит в просмотре всего ряда снитчей сначала до конца, что требует времени, пропорционального числу снитчей. Однако этот алгоритм не использует того факта, что веса снитчей уже отсортированы. Наилучший метод поиска состоит в том, чтобы проверить, стоит ли нужный мяч в середине ряда. Если да, то ответ получен. Если вес x меньше веса среднего снитча, то мы можем применить тот же метод поиска к отсортированному подряду слева от среднего элемента; аналогично, если x больше веса среднего мяча, то в дальнейшем мы будем рассматривать правую половину ряда.

Код возможного решения:

program tt;

const bl = 32;

type mass = array [1..bl] of integer;

var i, n, h, x: integer;

a: mass;

input, output: text;

 

function snwe (a: mass; st, n, x, h: integer): integer;

var i, br: integer;

begin

br:=round ((n-st)/2);

h:=br+st;

if (br = 0) then

begin

snwe:=0;

exit;

end;

if (a[h] = x) then

begin

snwe:=h;

end

else

begin

if (a[h] > x) then

begin

n:=n-br;

end

else

begin

st:=st+br;

end;

snwe:=snwe (a, st, n, x, h);

end;

end;

 

begin

assign (input, 'c:\input.txt');

assign (output, 'c:\output.txt');

 

filemode:=2;

 

reset (input);

rewrite (output);

 

read (input, n, x);

 

for i:=1 to n do

begin

read (input, a[i]);

end;

 

close (input);

 

write (output, snwe (a, 1, n, x, h));

 

close (output);

end.