2017-11-30
755
Имя входного файла input.txt
В файле INPUT.TXT записано два числа N и M
(0 < N<= 100, 0 <= M <= N*(N-1)/2). В следующих M строках записаны по два числа i и j (1<= i,j<= N), которые означают, что перекрестки i и j соединены тоннелем.
Формат выходных данных
Имя выходного файла output.txt
В файл OUTPUT.TXT вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.
Примечание: Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.
Пример
| input.txt | output.txt |
| 7 10 | 3 3 2 2 5 2 3 |
| 5 1 | |
| 3 2 | |
| 7 1 | |
| 5 2 | |
| 7 4 6 5 6 4 7 5 2 1 5 3 |
Решение
Program Svetofor;
var n, i, j, k: longint;
a: array [1..100] of integer;
b: array [1..5000, 1..2] of integer;
num: char;
t: integer;
f: text;
procedure swap (var a, b: integer); {замена}
var t: integer;
begin
t:= a;
a:= b;
b:= t;
end;
begin
for num:= '1' to '9' do begin
randomize; {случайным образом формируем матрицу}
writeln('Test #', num, ', n = ');
readln(n);
fillchar(a, sizeof(a), 0);
k:= 0;
for i:= 1 to n do
for j:= 1 to i - 1 do
if random(MaxInt) >MaxInt div 2 then begin
inc(a[i]);
inc(a[j]);
inc(k);
b[k, 1]:= i;
b[k, 2]:= j;
|
|
|
end;
for i:= 1 to k do begin
j:= random(k)+1;
t:= random(k)+1;
swap(b[t, 1], b[j, 1]);
swap(b[t, 2], b[j, 2]);
end;
assign(f, 'y_' + num + 'input.txt');
rewrite(f);
writeln(f, n, ' ', k);
for i:= 1 to k do
writeln(f, b[i, 1], ' ', b[i, 2]);
close(f);
assign(f, 'y_' + num + 'output.txt');
rewrite(f);
for i:= 1 to n do
write(f, a[i], ' ');
writeln(f);
close(f);
end;
end.
Тема: Метод перебора вариантов.
Задача 3: Зернышки
Имя входного файла: Input.txt.
Имя выходного файла: Output.txt.
В банке находятся белые и черные зернышки. Каждый раз из банки вынимают наугад два зернышка. Если они одинакового цвета, то их выбрасывают, а в банку кладут черное зернышко (черных зернышек достаточное количество). Если же зернышки разного цвета, то черное зернышко выбрасывают, а белое возвращают в банку. Эти действия повторяют, пока не останется одно зернышко.
Задание. Напишите программу, которая по известному количеству черных и белых зернышек определяет цвет последнего зернышка.
Входные данные. В единственной строке записаны два числа – количество белых и черных зернышек.
Выходные данные. Единственная строка выходного текстового файла должна содержать цвет оставшегося зернышка: white – если зернышко белое, black – если зернышко черное.
Пример входных и выходных данных:
| Input.txt | Output.txt |
| 4 3 | black |
program grain;
var white, black:longint;
begin
assign(input, 'input.txt');
reset(input);
assign(output, 'output.txt');
rewrite(output);
read(white, black);
if odd(white) then writeln('white') else {проверка чётности числа}
writeln('black');
close(input);
close(output);
end.
Тема: Работа с большими числами.
Задача 4: Простые гири
Существуют гири массой 1 г, 2г, …, N г (N ≤ 500000). Напишите программу, которая распределяет эти гири на максимально возможное количество пар, так чтобы общий вес гирь в каждой паре выражался простым числом.
|
|
|
Формат входящих данных: входной файл Input.txt содержит одно число N.
Формат выходящих данных: в выходной файл Output.txt выведите список найденных пар, по одной паре в ряду.
Решение
Program Prost_g;
var N:LongInt;
Procedure Read_data; {Процедура чтения начальных данных }
begin
assign(Input, 'Input.txt');
reset(Input);
readln(N);
close(Input)
end;
Function Prost(x:LongInt): Boolean; {Функция определения, является ли число простым}
var
q:Boolean;
i:LongInt;
begin
q:=False;
if Odd(x) then
begin
q:=True;
i:=3;
while (i*i<=x) and q do
if x mod i=0 then q:=False
else inc(i,2)
end;
Prost:=q
end; {End Prost}
Procedure Solve_Write; {Процедура поиска и записи «простых» пap}
var
flag:Boolean;
i, j: LongInt;
begin
assign(Output, 'Output.txt');
rewrite(Output);
repeat
i:=l;
while not Prost(n+i) do inc(i);
j:=i-l;
while i<n do
begin
writeln(i, ‘ ‘,n);
inc(i);
dec(n)
end;
n:=j
until n<=l;
close(Output)
end; {End Solve_Write}
BEGIN
Read_Data;
Solve_Write;
END.
Тема: Метод перебора вариантов.
