Участник:Annette

ДЕТАЛИ
[+/-]

Виджеты

Виджеты<bs-widget-edit>

Требуемые страницы
Кто в сети?
Материал из Wiki Лицея
Перейти к: навигация, поиск

Разбор задач муниципального этапа всероссийской олимпиады школьников по информатике.

Задача 1. Система связи
Межпланетное общение в одной далекой-далекой галактике организовано по следующему принципу: планеты могут быть связаны либо напрямую посредством двусторонней линии космической связи, либо опосредованно, т.е. через цепочку планет между которыми установлено прямое сообщение. Подобная распределенная система хороша тем, что при выходе станции связи из строя на одной из планет остальные планеты практически всегда остаются в системе общения, т.к. от одной планеты до другой может быть несколько альтернативных маршрутов связи. Однако в этой системе могут быть критические участки – планеты (они называются ключевыми), на которых выход станций связи из строя может сделать невозможным сообщение между какими-то из оставшихся планет. Ваша задача – составить список ключевых планет, который потребуется при укреплении и модификации системы межпланетной связи.
Входной файл
В первой строке находится два числа: N (3≤N≤20) – количество планет и K (1≤K≤200) – количество прямых линий связи между планетами. Гарантируется, что любые две планеты соединены, по крайней мере, одним маршрутом связи. На каждой из следующих K строк через пробел располагается пара номеров планет, между которыми есть прямая линия связи. Планеты нумеруются последовательными натуральными числами, начиная с единицы.
Выходной файл
В выходном файле в первой строке находится количество ключевых планет, а далее по одному на строку содержатся перечисленные в порядке возрастания номера ключевых планет.
Примеры

Входной файл Выходной файл
4 3
1 2
2 3
3 4
2
2
3
6 8
1 2
1 3
2 3
2 4
3 4
4 5
4 6
5 6
1
4
3 3
1 2
2 3
3 1
0
Решение


Пример кода:
type rect=record a:array[0..100]of integer; n:integer; end;
var used:array of boolean;
r,time,pred:array of integer;
g:array [0..100] of rect;
cnt,res:integer;
i,a,b,n,m:integer; function min(a,b:integer):integer;
begin
if (a<b) then min:=a
else min:=b;
end;
procedure dfs(v:integer; p:integer);
var t,child,i:integer;
begin
used[v]:= true;
inc(cnt);
time[v]:=cnt;
pred[v]:=cnt;
child:=0;
for i:=0 to g[v].n-1 do
begin
t:= g[v].a[i];
if (t <> p) then
begin
if (used[t]) then
pred[v] := min (pred[v], time[t])
else begin
dfs (t, v);
pred[v] := min (pred[v], pred[t]);
if ( (pred[t] >= time[v]) and (p <> -1) and (r[v]=0)) then
begin
inc(res);
r[v] := 1;
end;
inc(child);
end;
end;
end;
if( (p = -1) and (child > 1) ) then
begin
inc(res);
r[v] := 1;
end;
end;
begin
readln(n,m);
setlength(time,n);
setlength(pred,n);
setlength(r,n);
setlength(used,n);
for i:=0 to n-1 do begin
used[i]:=false;
g[i].n:=0;
r[i]:=0;
time[i]:=0;
pred[i]:=0;
end;
for i:=0 to m-1 do
begin
readln(a,b);
g[a-1].a[g[a-1].n]:=b-1; inc(g[a-1].n);
g[b-1].a[g[b-1].n]:=a-1; inc(g[b-1].n);
end;
cnt:= 0;
res:= 0;
dfs(0,-1);
writeln(res);
for i:= 0 to n-1 do
if(r[i]=1) then writeln(i + 1);
end.

Задача 2. Декодирование
Обновленное программное обеспечение для станций связи выполняет шифрование сигнала. Данная операция проходит в три этапа:
1. Каждый символ строки заменяется на код этого символа (см. таблицу кодов). Например, символ «M» заменяется на число 39.
2. Каждое из полученных чисел заменяется на двоичный код длины 8 (например, число 39 заменяется на комбинацию «00100111»). Полученные двоичные коды выписываются подряд без разделителей.
3. Группы из двух или более подряд идущих нулей заменяются на комбинацию, состоящую из двух чисел: количество нулей и число 0. Аналогично группы из двух или более подряд идущих единиц заменяются на комбинацию, состоящую из двух чисел: количество единиц и число 1. Между всеми числами в записи ставится пробел. Например, комбинация «00100111» будет заменена на «2 0 1 2 0 3 1».
Таблица кодов

Символы «a» - «z» Коды 1-26
Символы «A» - «Z» Коды 27-52
Символы «0» - «9» Коды 53-62
Символ « » (пробел) Код 63
Символ «.» (точка) Код 0
Вы входите в команду, ответственную за декодирование поступившей информации на принимающей стороне. На вход Вам поступает уже зашифрованная строка, Ваша задача восстановить исходную строку.

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

Входной файл Выходной файл
2 0 1 2 0 3 1 M
7 0 1 a
5 0 1 9 0 1 da
Решение


Пример кода:
function getCodeChar(c:integer):char;
begin
if (1 <= c )and( c <= 26) then getCodeChar:=chr(c - 1 + ord('a'));
if (27 <= c )and( c <= 52) then getCodeChar:=chr(c - 27 + ord('A'));
if (53 <= c )and( c <= 62) then getCodeChar:=chr(c - 53 + ord('0'));
if (c = 63) then getCodeChar:=' ';
if (c = 0) then getCodeChar:= '.';
end;
var i,bit,cnt, curNumber,curLength:integer;
begin
bit:=0;
cnt:=0;
curNumber:=0;
curlength:=0;
while not eoln() do
begin
read(bit);
if bit>1 then
begin
cnt:=bit;
read(bit);
end
else
cnt:=1;
for i:=1 to cnt do
begin
curNumber:=(curNumber shl 1)+bit;
curlength:=curlength+1;
if (curlength=8)then
begin
write(getCodeChar(curNumber));
curNumber:=0;
curLength:=0;
end;
end;
end;
if (curlength>0) then
begin
write('Input data is incorrect!');
exit;
end;
end.

Задача 3. Познакомиться с пришельцами

За круглой планетой небольших размеров находится круглый космический корабль пришельцев. Корабль наблюдателей O (корабль очень небольшой, можно считать его точкой), центр корабля пришельцев S и центр планеты P лежат на одной прямой. На какое минимальное расстояние d необходимо переместиться наблюдателям, чтобы увидеть корабль пришельцев?
1.png

Входной файл
В первой строке входного файла через пробел записаны радиусы космического корабля пришельцев и планеты. На второй строке располагается величина OP – расстояние между кораблем наблюдателей и центром планеты, а через пробел – величина OS – расстояние между кораблем наблюдателей и центром корабля пришельцев. Все величины – натуральные числа, меньшие 10000. Поверхности планеты и корабля пришельцев могут касаться друг друга.
Выходной файл
Вывести (с точностью не менее 5 знаков после запятой) значение d – минимальное расстояние, на которое необходимо сдвинуть корабль наблюдателей, чтобы увидеть корабль пришельцев.
Примеры

Входной файл Выходной файл
1 2
3 7
2.75000
5 1
3 9
0.00000
Решение

Обратите внимание! Требуется вывести итоговое значение с точностью не менее 5 знаков после запятой, т.е. если в ответе содержится больше знаков, необходимо вывести их все.

Пример кода:
var p, hp, s, hs,d:extended;
begin
read(s, p, hp, hs);
if (abs(p - s) < 1E-7) then
write( p:0:5)
else
if (s > p*hs / hp - 1E-7) then
write('0.0')
else begin
d := (hs*p - hp*s) / (hs-hp);
write(d:0:5);
end;
end.


Задача 4. Трудности перевода
Простейшие языки существ, населяющих планеты системы Альфа Центавра состоят из двух звуков: «А» и «О». Исследователи различают несколько уровней подобных языков. В языке первого уровня нет никаких ограничений на сочетания исходных звуков. Язык второго уровня не может содержать слов, где встречалось бы два звука «О», идущих подряд. Языки третьего уровня содержат слова такие, что никакие три звука «О» не произносятся подряд. Для составления справочника языков исследователям необходимо уметь определять максимальное количество слов языка заданной длины в зависимости от уровня этого языка.
Например, максимальное количество слов длины 3 языка второго уровня равно пяти. Это слова «ААА», «ААО», «АОА», «ОАА», «ОАО». Слова же «ООА», «АОО», «ООО» не будут допустимыми.
Входной файл
В единственной строке входного файла через пробел записаны два натуральных числа: длина слов n и уровень языка m (1≤n≤20, 1≤m≤10).
Выходной файл
Содержит одно число – максимальное количество слов длины n в языке уровня m.
Примеры

Входной файл Выходной файл
3 2 5
4 1 16
Решение


Пример кода:
var
n,k,i,s,p:longint;
r:array of longint;
begin
read(n,k);
if k=1 then begin
write(1 shl n);
exit;
end;
setlength(r,n);
r[0]:=2;
for i:=1 to k-1 do
begin
r[i]:=r[i-1]*2;
end;
r[k-1]:=r[k-1]-1;
for i:=k to n-1 do
begin
s:=0;
for p:=1 to k do
s:=s+r[i-p];
r[i]:=s;
end;
write(r[n-1]);
end.