Это чисто техническая задача на аккуратное программирование.

строкизадачи

Задача 6 Текст

Дан текст, состоящий из слов, знаков препинания и других символов. Словом в тексте считается последовательность символов из прописных и строчных букв латинского алфавита. Требуется перевернуть (записать в обратном порядке) все слова текста, оставив знаки препинания и другие символы, включая буквы русского алфавита, без изменений. В строке не более 255 символов, строк в файле не более 1000.

Пример.

Input.txt	Output.txt
This is an example. Prim333primяяrt	sihT si na elpmaxe. mirP333mirpяяtr

Входной файл Input.Txt в первой строке входного файла находится 5 чисел,разделенных пробелом: n, m, s, t, q.

N, M – размеры доски (отсчет начинается с 1); S, T – координаты клетки - кормушки (номер строки и столбца соответственно), Q – количество блох на доске. И далее Q строк по два числа – координаты каждой блохи.

Выходной файл Output.txt содержит одно число – минимальное значение суммы длин путей или –1, если сбор невозможен.

Примеры.

Input.txt	Output.txt
4 4 1 1 3 2 3 3 2 3 3	6
5 5 3 4 0	0

Эта задачу можно решить двумя способами. 1 способ При решении задачи на Pascal-е можно было использовать тип string, так как максимальная длина строки 255 символов. После считывания очередной строки, необходимо изменить ее следующим образом: каждое найденное "слово" перевернуть на месте. Далее вывести эту строку. 2 способ Более элегантный подход заключатся в том, что не надо анализировать текст по строкам, можно представить его в виде последовательности символом с переводами кареток. Для переворота "слов", можно использовать концепцию работы стека, накапливая символы в нем. Рассмотрим его реализацию: var s:string; c:char; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); s:=''; while not eof(input)do пока не дошли до конца файла begin read(c); считываем символ if c in ['A'..'Z','a'..'z']  если это буква then s:=c+s прибавляем символ в начало слова        else begin               write(s); иначе выводим слово               s:=''; очищаем строку               write(c); выводим символ             end;    end; write(s); close(input); close(output); end. Здесь до конца файла считывается по одному символу. Если текущий символ латинский, то он является частью слова, поэтому он приписывается в начало строки s. Если символ не латинский, то на данной итерации либо конец "слова", либо просто продолжение текста. В последнем случае необходимо вывести перевернутое слово, очистить строку s, а также вывести только что считанный символ текста, уже не являющимся частью слова.  Еще надо учитывать случай, когда в конце файла находиться "слово", но нет перевода каретки. В результате мы теряем последнее слово.

строкизадачи

Задача 7 Форум

Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме. После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это

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

Первая строка входного файла содержит целое число N - количество сообщений в форуме (1 <= N <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке.Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения. Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения. Длина всех сообщений не превышает 100 символов. Формат выходных данных

Выведите в выходной файл название темы, к которой относится наибольшее количество сообщений. Если таких тем несколько, то выведите первую в хронологическом порядке.

Пример

Input.txt	Output.txt
7 0 Олимпиада по информатике Скоро третья командная олимпиада? 0 Новая компьютерная игра Вышла новая крутая игра! 1 Она пройдет 24 ноября 1 В Санкт-Петербурге и Барнауле 2 Где найти? 4 Примет участие более 50 команд 6 Интересно, какие будут задачи	Олимпиада по информатике

Каждую тему в форуме можно представить в виде дерева, т.е. первое сообщение - это корень дерева, остальные - ветви и листья. Нам необходимо найти дерево с максимальным количеством элементов и вывести тему, которая соответствуют корню этого дерева. Каждое дерево надо преобразовать в другое дерево, не имеющее ветвей. Т.е. ответ на какое-то сообщение, принадлежащее данной теме, делал ответом на первое сообщение в теме.

Такое преобразование делается очень просто: создаем массив, для каждого элемента содержащий номер его предка; если сообщение - начало новой темы (т.е. ответ на сообщение 0), то номер предка этого сообщения - его собственный номер, если же сообщение не является началом новой темы, то его номер предка равен номеру предка его отца. Т.е. на рисунке у сообщения 1 предок равен самому себе, у сообщения 2 отец - 1 сообщения, следовательно, предок 2 также 1, у 3 сообщения отец - 2 сообщение, его предок - 1, значит и предок 3 - 1 и т.д.

Теперь подсчитываем наиболее популярную тему. Это можно сделать прямо по ходу преобразования деревьев. Надо завести массив, в котором будет содержаться количество элементов в дереве, корнем которого является элемент массива. Затем следует найти максимальный элемент массива (это также можно делать по ходу преобразований) и вывести соответствующую ему тему. Темы надо хранить в массиве строк с длиной 30, а сообщения вообще хранить не надо, а считывать их оператором readln.

Program forum;

const nmax=10;

var tem:array[1..nmax] of string[30]; массив тем

coob:array[1..nmax] of string[100]; массив сообщений

num:array[0..nmax] of word; массив показывающий на какое

сообщение отвечает данное

ch,ind,max,i,j,n,cod,m,it,is:integer; ind-номер темы у которой

максимальное количество сообщений

s:string[100]; s-переменная в которую считываем

строку из файла

Procedure Init; it-индекс темы

Begin is-индекс сообщения

Assign(input,'forum.in'); ch-хранит число сообщений к теме

Reset(input); m-код темы или сообщения

readln(N);it:=1;is:=1;

while not seekeof do пока не дошли до конца файла

повторяем

begin

readln(s); считываем строку

val(s,m,cod); переводим ее в числовой формат

if m=0

then если это тема

begin

readln(tem[it]); считываем тему

num[is]:=0; сообщению в теме ничего не

предшествует

inc(it); считаем тему

readln(coob[is]); считываем сообщение

inc(is); считаем его

end

else если это сообщение

begin

readln(coob[is]); считываем его

num[is]:=m;inc(is); записываем на какое сообщение оно

отвечает

end;

end;

End;

Procedure out;

Begin

Assign(output,'forum.out');

Rewrite(output);

write(tem[ind]);

End; выводим ответ

Procedure Solve;

Begin

max:=0;

for i:=n downto 1 do движемся по массиву num с конца

begin

ch:=1; счетчик сообщений к теме

j:=num[i]; указатель на предыдущее сообщение

while num[j]<>0 do пока не дошли до сообщения, которое

было в теме

begin

inc(ch); считаем сообщение

j:=num[j]; меняем указатель

end;

if ch>max then

begin max:=ch;ind:=j end; сравниваем количество сообщений к

теме с максимальным

end;

End;

Begin init; solve; out; End.

строкизадачи

Задача 8 Даны две строки. Является ли вторая строка подстрокой первой.

В решении используем алгоритм Кнута-Морриса- Пратта

program Project2;

{$APPTYPE CONSOLE}

{$o-}

uses SysUtils;

var s,t:string;

i,k,n:integer;

p:array[0..100000]of integer;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

readln(t);

readln(s);

n:=length(s);

s:=s+'$'+t;

p[0]:=0;

p[1]:=0;

for i:=2 to length(s) do

begin

k:=i-1;

while (k>0)and(s[i]<>s[p[k]+1])

do k:=p[k]; перебираем префиксы (и находим

максимальный по длине), которые

являются суффиксом подстроки

S[1..i-1]

if s[i]=s[p[k]+1]

then p[i]:=p[k]+1; если нашли => префикс функция

S[1..i] будет на 1 больше, чем

префикс функция найденного префикса S[1..i-1]

if p[i]=n then writeln(i-2*n); выводим позицию в текста, с

которой начинается вхождение

искомой подстроки

end;

close(input);

close(output);

end.

строкизадачи

Задача 9  Неправильное сложение

Володя написал программу, которая складывает в столбик два числа. К сожалению, он не разобрался, как правильно переносить единицу из одного разряда в следующий. Поэтому программа стала выполняться следующим образом. Сначала она складывает последние цифры обоих чисел и за­писывает результат, как в случае, если он однозначный, так и в случае, если он двузначный. Затем программа складыва­ет предпоследние цифры обоих чисел и результат сложения приписывает слева к результату предыдущего сложения. Далее процесс повторяется для всех разрядов. Если в одном числе цифр меньше, чем в другом, то программа размещает нули в соответствующих разрядах более короткого числа.

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

Требуется написать программу, которая поможет Феде и Володе определить, верно ли утверждение, что, складывая заданные три числа в разном порядке, можно получить разные суммы.

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

Входной файл содержит в одной строке три целых числа a, b и c (1  a, b, c  1 000 000). Все числа в строке разделены пробелом.

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

В первую строку выходного файла необходимо вывести слово YES, если данные три числа можно сложить разными способами и получить разные суммы. В противном случае, необходимо вывести слово NO.

В последующих строках выходного файла необходимо вывести все возможные суммы, которые можно получить, складывая числа a, b и c. Суммы следует выводить по одной на строке и в порядке их возрастания.

Пример:

Input.txt	Output.txt
30 239 566	YES 7945 71215
643 733 553	NO 18129

program z;

{$APPTYPE CONSOLE} !!!!!!!!!!!

uses SysUtils,Math;

var x,xx,xxx,kol,maxn,i,j,k:longint;

s,ans:array[1..3]of string;

vs,s1,s2,s3,cs:string;

function bol(x1,x2:longint):boolean;

var i:longint;

begin

if length(ans[x1])>length(ans[x2]) then begin result:=true; exit; end else

if length(ans[x1])<length(ans[x2]) then begin result:=false; exit; end;

for i:=1 to length(ans[x1]) do

if ans[x1][i]>ans[x2][i] then begin result:=true; exit; end else

if ans[x1][i]<ans[x2][i] then begin result:=false; exit; end;

end;

begin

reset(input,'input.txt'); rewrite(output,'output.txt');

read(x,xx,xxx);

s[1]:=inttostr(x);s[2]:=inttostr(xx);s[3]:=inttostr(xxx);

kol:=0;

maxn:=max(length(s[1]),max(length(s[2]),length(s[3])));

for i:=1 to 3 do

for j:=1 to maxn-length(s[i]) do

s[i]:='0'+s[i];

for i:=1 to 2 do

for j:=i+1 to 3 do begin

vs:='';s1:=s[i]; s2:=s[j]; s3:=s[6-i-j];

for k:=length(s1) downto 1 do

vs:=inttostr(ord(s1[k])+ord(s2[k])-2*ord('0'))+vs;

cs:=vs;

for k:=1 to length(vs)-length(s3) do s3:='0'+s3;

vs:='';

for k:=length(cs) downto 1 do

vs:=inttostr(ord(cs[k])+ord(s3[k])-2*ord('0'))+vs;

while (vs[1]='0')and(length(vs)>1) do delete(vs,1,1);

for k:=1 to kol+1 do begin

if vs=ans[k] then break;

if k=kol+1 then begin inc(kol); ans[k]:=vs; end;

end;

end;

if kol=1 then writeln('NO') else writeln('YES');

for i:=1 to kol-1 do

for j:=i+1 to kol do

if bol(i,j) then begin vs:=ans[i]; ans[i]:=ans[j]; ans[j]:=vs; end;

for i:=1 to kol do

writeln(ans[i]);

end.

строкизадачи

Задача 10 Палиндром

Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.

Во входном файле записан набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется написать программу, которая из данных букв по указанным правилам составит палиндром наибольшей длины, а если таких палиндромов несколько, то первый в алфавитном порядке.

Входные данные:

В первой строке записано натуральное число N (1 ≤ N ≤ 100000). Во второй строке записана последовательность из N больших латинских букв (буквы записаны без пробелов).

Выходные данные:

В единственной строке - искомый палиндром.

Пример входного и выходного файла

Input.txt	Output.txt
3 AAB	ABA
6 QAZQAZ	AQZZQA
6 ABCDEF	A

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

var a:array[65..91] of longint;

ch:char;

i,j,n,k,m:longint;

s:string;

log:boolean;

Procedure closing; процедура, закрывающая файлы

begin

close(input); close(output); halt(0);

end;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

readln(n);

log:=false;

fillchar(a,sizeof(a),0);

for i:=1 to n do

begin

read(ch); считываем символ

inc(a[ord(ch)]); и считаем количество букв каждого вида

for i:=65 to 90 do составляем палиндром

if (a[i]<>0) then если буква есть

begin

if (a[i]mod 2=1) and(not log ) если буква встречалась нечетное количество раз

then

begin ch:=chr(i); log:=true; end; и мы ее еще не брали, то запоминаем ее в ch

if a[i]>1 then если количество букв больше 1

for j:=1 to (a[i]div 2) do s:=s+chr(i) то половину добавляем в строку s

end;

write(s); выводим половину палиндрома

if ch<>'' then write(ch); если в ch есть буква, то добавляем и ее

for i:=length(s) downto 1 do выводим вторую половину палиндрома

write(s[i]);

closing;

end.

строкизадачи

Задача 11 Сумма к первых

Известный ламер Вася Пупкин не смог найти сумму первых К цифр 2000- значного числа. А вы сможете?

Входные данные: В первой строке одно число К, во второй одно число, содержащее 2000 цифр.

Выходные данные : одно число - сумму первых К цифр данного числа.

Пример:

Input.txt	Output.txt
5 1234567890…	15

Это утешительная задача.

program zad4;

Var n,i,j,k:longint;

c:char;

Procedure closing;

begin

close(input); close(output);

halt(0);

end;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

readln(k); считываем количество цифр

n:=0;

for i:=1 to k do считываем К символов

begin

read(c);

n:=n+(ord(c)-ord(‘0’)); преобразуем символ в цифру

end;

write(n); выводим результат

closing;

end.

Задача 12  Числа Татарстан 2009

Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.

Чтобы ответить на поставленный вопрос, Вова решил написать программу, которая позволит ему найти число различных последовательностей неотрицательных целых чисел, в каждой из которых любое число не превосходит C. Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних k цифр этого числа.

Требуется написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу.

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

Первая строка входного файла содержит три целых числа — n, C и k (1  n  50 000, 1  C  10⁸, 1  k  18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр.

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

В выходной файл выведите последние k цифр искомого количества последовательностей без ведущих нулей.

Пример входных и выходных данных

numbers.in	numbers.out
3 11 2 111	3
19 9 1 0123456789876543210	1
1 8 3 9	0

Примечание

Решения, работающие только для k  9, будут оцениваться из 70 баллов.

program ;

{$APPTYPE CONSOLE}

uses SysUtils;

Var n,c,k,mm,ch:int64;

vs:string;

s:array[1..50000]of char;

i,j:longint;

ans:array[0..50000]of int64;

u:boolean;

function strtoint64(ss:string):int64; превращает строку в число

var i:longint;

begin

result:=0;

if ((length(ss)=19)and(ss[1]>'1'))or(length(ss)>19)

then begin result:=0; u:=true; end;

for i:=1 to length(ss) do

result:=result*10+ord(ss[i])-ord('0');

end;

begin

reset(input,'input.txt);

rewrite(output,'output.txt);

readln(n,c,k);

mm:=1;

for i:=1 to k do mm:=mm*10; вычисляем 10^к

for i:=1 to n do read(s[i]);

ans[0]:=1;

for i:=1 to n do

begin

vs:='';

for j:=i downto 1 do

begin

vs:=s[j]+vs;

u:=false;

ch:=strtoint64(vs);

if (ch>c)or(u)

then break

else

if (vs[1]<>'0')or(length(vs)=1)

then ans[i]:=(ans[i]+ans[j-1]) mod mm;

end;

end;

writeln(ans[n]);

end.

строкизадачи

К оглавлению

Графы

Часто в задачах встречается следующая конструкция - есть дома и дороги, их соединяющие; у каждой дороги есть своя длина или все дороги имеют одну и туже длину. По другой терминологии такая конструкция называется графом, дома называются "вершинами", дороги - "ребрами" , а длина дороги "весом ребра". Таким образом, фраза «найти минимальный вес пути между вершинами s и k в графе» может быть переведена так: «есть дома и дороги их соединяющие. Также заданы длины дорог. Найти кратчайшую длину пути от города s до города k, если двигаться можно только по дорогам». Вес ребра (i,j) означает, например, сколько груза может быть перевезено по дороге (по ребру) (i,j) за единицу времени) или стоимость проезда по дороге из i в j.

Граф состоит из вершин и ребер. Вершины графа - объекты любой природы; поскольку их должно быть конечное число, то мы будем обозначать их натуральными числами1,2,3 и т.д.. Ребра графа соединяют некоторые из его вершин. Если ребра имеют направление, то граф называется ориентированным (орграфом); в противном случае он неориентированный. Если в графе есть ребро C из вершины A в вершину B, то говорят, что ребро C инцидентно вершинам A и B, а также что вершина A смежна с вершиной B. Степень вершины - число инцидентных ей ребер. Для орграфа есть входящая степень - число входящих в вершину ребер, и исходящая степень - число исходящих из вершины ребер. Вершина называется четной, если ее степень четна, и нечетной в противном случае. Вершина степени 0 называется изолированной. Путь в графе - последовательность вершин, каждые две соседние из которых смежные. Длина пути - количество вершин в нем минус 1. Если из вершины A в вершину B есть путь, то говорят, что вершина B достижима из вершины A. Путь называется простым, если все вершины в нем различны. Цикл в ориентированном графе - путь длины больше 0, в котором первая и последняя вершины совпадают. Цикл называется простым, если в нем нет совпадающих вершин, кроме первой и последней. В неориентированном графе цикл - путь длины не меньше 3, в котором первая и последняя вершины совпадают. Граф, в котором нет циклов, называется ациклическим. Неориентированный граф называется связным, если из любая его вершина достижима из любой другой. Любой неориентированный граф можно разбить на компоненты связности, т. е. такие непересекающиеся множества вершин, что вершина A достижима из B в том и только в том случае, если эти вершины принадлежат одной компоненте связности.

Полный граф - граф, в котором любая вершина смежна любой другой. Двудольный граф - граф, в котором вершины можно разбить на два множества A и B так, что никакие две вершины, принадлежащие одному множеству, не являются смежными. Ациклический неориентированный граф называют лесом, а связный лес называют деревом.

Взвешенный граф - граф, на ребрах которого написаны числа, которые называются весами ребер.

Основные задачи, решаемые на графах