Решения заданий заочного тура (Интернет-тура)
XI Республиканской олимпиады имени
ИНФОРМАТИКА
8-9 классы
1. «Фигурное катание»
Необходимо считать данные в три одномерных массив, состоящий из трех строк и n столбцов, следующим образом. Номер столбца – есть номер фигуриста. В первой строке содержится сумма первых трех баллов, во второй строке – сумма баллов с 4-го по 6-й баллы, в третьей – сумма с 7-го по 9-й баллы соответствующего фигуриста. Затем найти максимальные элементы в массивах.
Если же несколько максимальных элементов, то занести номера элементов с максимальным значением в другой массив для каждого такого массива. Провести сортировку элементов получившихся массивов. И вывести значения данных в в массивах (уже отсортированном).
2. «Модные числа»
import java. io.*;
import java. util.*;
public class beauty_ft implements Runnable {
public final static int MAX_N = (int) 2e5;
private Scanner in;
private PrintWriter out;
String fname = "beauty";
private void myAssert(boolean e, String message) {
if (!e) {
throw new Error("Assertion failure!!! " + message);
}
}
public void solve() {
int n = in. nextInt();
myAssert(1 <= n && n <= "");
int x = 1;
while (true) {
int t = x;
int c = 0;
int s = 0;
while (t > 0) {
c++;
s += t % 10;
t /= 10;
}
if (s % c == 0) {
n--;
}
if (n == 0) {
out. println(x);
break;
}
x++;
}
}
public void run() {
try {
solve();
} catch (Exception e) {
e. printStackTrace();
System. exit(1);
} finally {
out. close();
}
}
public beauty_ft() {
try {
in = new Scanner(new File(fname + ".in"));
out = new PrintWriter(new File(fname + ".out"));
} catch (Exception e) {
e. printStackTrace();
System. exit(1);
}
}
public static void main(String[] args) {
Locale. setDefault(Locale. US);
new Thread(new beauty_ft()).start();
}
}
3. «Забавные преобразования»
Задачу можно решать непосредственно путем перевода исходного числа в двоичную систему счисления, получения всех его циклических сдвигов, перевода их в десятичную систему и выбора максимального из них:
Var I, J, Maх, Мax, NumDigits, Digit :Integer;
Digits: Array[1..20] Of Integer;
Begin
<ввод исходвого числа в переменную>
Мах := Nira; KiraDigits := 0; {перевод в двоичную систему}
While Kim > 0 Do Begin Inc(NuaDigits);
Digits[KumDigits] := Кurn Mod 2;
Nira := Num Div 2
End;
For I:=l To NumDigits - 1 Do Begin {сдвиг}
Digit := Digits[1];
For J := 2 To KumDigits Do Digits[J-l] := Digits[J];
Digits[KumDigits] := Digit; {перевод в десятичную систему}
Hun := 0;
For J := KumDigits DownTo 1 Do
Kum := Kum*2 + Digits [J] ;
If Kum > Max Then Max := Kum
End;
<вывод значения переменной Max в качестве ответа>
End;
Естественно, можно было решать эту задачу с использованием операции побитового сдвига SHR, не переводя число явно в двоичную систему.
4. «Точки»
Const
MaxN = 1000;
Type
Float = Extended;
TPoint = Record
x, y: Longint;
End;
Var N: Integer;
P: Array [1..MaxN] Of TPoint;
Sc: Array [1..MaxN] Of Longint;
Best: Float;
Procedure Init;
Var i: Integer;
Begin
Assign(input,'d. in'); Reset(input);
Read(N); For i := 1 To N Do With p[i] Do Read(x, y);
Close(input);
End;
Function GLine(Const p1,p2,p: TPoint): Longint;
Begin
GLine := (p. x-p1.x)*(p2.y-p1.y) - (p. y-p1.y)*(p2.x-p1.x);
End;
Function Search(a, b: Integer): Integer;
Var i: Integer;
Begin
i := 1; While (i < n) And (GLine(p[a],p[b],p[i]) = 0) Do inc(i);
Search := i;
End;
Procedure Swap(i, j: Integer);
Var c: TPoint; t: Longint;
Begin
c := p[i]; p[i] := p[j]; p[j] := c;
t := sc[i]; sc[i] := sc[j]; sc[j] := t;
End;
Procedure QSort(b, l: Integer);
Var i, j: Integer; x: Longint;
Begin
i := b; j := l; x := Sc[(i+j) shr 1];
Repeat
While (x > sc[i]) Do inc(i);
While (x < sc[j]) Do dec(j);
If i<=j Then
Begin
Swap(i, j); Inc(i); Dec(j);
End;
Until i>j;
If i < l Then QSort(i, l);
If b < j Then QSort(b, j);
End;
Function Len(a, b: Integer): Float;
Begin
Len := Sqrt(Sqr(p[a].x-p[b].x)+Sqr(p[a].y-p[b].y));
End;
Function Min(a, b: Float): Float;
Begin
If a < b Then Min := a Else Min := b;
End;
Procedure Solve;
Var r, i: Integer; t: Float;
Begin
If GLine(p[1],p[2],p[3]) = 0 Then r := Search(1,2)
Else If N > 3 Then
Begin
If GLine(p[1],p[2],p[4]) = 0 Then r := Search(1,2) Else
If GLine(p[2],p[3],p[4]) = 0 Then r := Search(2,3) Else
If GLine(p[1],p[3],p[4]) = 0 Then r := Search(1,3) Else
WriteLn('Error');
End
Else r := 3;
Swap(n, r);
For i := 1 To n-1 Do
sc[i] := (p[2].x-p[1].x)*(p[i].x-p[1].x) +
(p[2].y-p[1].y)*(p[i].y-p[1].y);
QSort(1, n-1);
Best := Len(1,n-1) + Min(Len(n,1), Len(n, n-1));
For i := 1 To N-2 Do
Begin
t := Len(1,i) + Len(i+1,n-1);
Best := Min(Best, t+Len(i, n)+Len(i+1,n));
Best := Min(Best, t+Len(i, n)+Len(n-1,n));
Best := Min(Best, t+Len(1,n)+Len(i+1,n));
Best := Min(Best, t+Len(1,n)+Len(n-1,n));
End;
End;
Procedure Done;
Begin
Assign(output, 'd. out'); Rewrite(output);
WriteLn(Best:0:15);
Close(output);
End;
BEGIN
Init; Solve; Done;
END.
5. «Размерность строки»
import java. io.*;
import java. util.*;
public class string_ft implements Runnable {
public final static int MAX_N = (int) 2e5;
private Scanner in;
private PrintWriter out;
String fname = "string";
private void myAssert(boolean e, String message) {
if (!e) {
throw new Error("Assertion failure!!! " + message);
}
}
public void solve() {
String s = in. next();
int n = s. length();
char[] c = s. toCharArray();
myAssert(1 <= n && n <= 2e5, "");
for (int i = 0; i < n; i++) {
myAssert('a' <= c[i] && c[i] <= 'z', "");
}
int max = Integer. MIN_VALUE;
int min = Integer. MAX_VALUE;
for (int i = 0; i < n; i++) {
max = Math. max(max, c[i]);
min = Math. min(min, c[i]);
}
int lastMin = -1;
int lastMax = -1;
int ansLen = Integer. MAX_VALUE;
int ansPos = -1;
for (int i = 0; i < n; i++) {
if (c[i] == max) {
if (lastMin!= -1) {
int cl = i - lastMin + 1;
if (cl < ansLen) {
ansPos = lastMin;
ansLen = cl;
}
}
lastMax = i;
}
if (c[i] == min) {
if (lastMax!= -1) {
int cl = i - lastMax + 1;
if (cl < ansLen) {
ansPos = lastMax;
ansLen = cl;
}
}
lastMin = i;
}
}
out. println(s. substring(ansPos, ansPos + ansLen));
}
public void run() {
try {
solve();
} catch (Exception e) {
e. printStackTrace();
System. exit(1);
} finally {
out. close();
}
}
public string_ft() {
try {
in = new Scanner(new File(fname + ".in"));
out = new PrintWriter(new File(fname + ".out"));
} catch (Exception e) {
e. printStackTrace();
System. exit(1);
}
}
public static void main(String[] args) {
Locale. setDefault(Locale. US);
new Thread(new string_ft()).start();
}
}
6. «Несовпадения»
Необходимо сформировать двумерный массив a[n, m] из элементов – соответствующих цифр на карточках.
Для подсчета «несовпадений» необходимо иметь счетчик s, который увеличивать на единицу при выполнении следующего условия: a[i, j]+a[i+1,j]+a[i, j+1]+a[i+1,j+1]=18.
9. «Слова»
Заметим, что нам не важно, где именно находятся буквы, которые вычеркивает Мегамозг. Поэтому не обязательно искать именно те буквы, которые составляют слова: мы можем вычеркивать такие же буквы из любой клетки таблицы. После этого наблюдения решение задачи уже становится делом техники. Приведем два способа решения задачи.
Первый способ.
Воспользуемся стандартными функциями для работы со строками, чтобы сделать код лаконичным. Сначала мы запишем все символы из таблицы в одну строку (их не более 100. поэтому в Паскале можно воспользоваться стандартным типом string):
S:=";
for I:=l to H do begin
ReadLn(V);
S:=S+V;
end;
Теперь будем читать слова по одному и удалять каждую букву каждого слова из строки S:
for J:=l to М do begin
ReadLn(V);
for I:=l to Length(V) do Delete (S, Роs(V[i], S), 1);
end;
Напомним, что функция Pos возвращает позицию первого вхождения символа в строку, а процедура Delete удаляет из данной строки символ (в общем случае — подстроку) в данной позиции. После выполнения этого фрагмента программы в строке S останутся ровно те символы, которые нам требуется вывести:
write (s);
Второй способ.
Заведем массив:
a: array ['A'..'Z'] of integer;
Подсчитаем, сколько раз встречается каждая буква латинского алфавита в исходном квадрате:
for i:=l to n do begin for j:=l to n do begin
read (с);
inc(a.[c]) end; readln; end;
Теперь будем считывать слова и «вычеркивать» встречающиеся в них буквы, уменьшая соответствующие счетчики:
for i:=l to m do begin readln (s);
for j:=l to length(s) do dec(a.[s[j]])
end;
Теперь напечатаем оставшиеся буквы:
for с: = 'А' to 'Z' do for i:=l to a.[c] do write (c);
10. «Змеи Горынычи»
Помимо двух - и трёхголовых драконов, введём новую породу – одноголовых (такие драконы получаются, если отрубить одну голову у двухголового или две головы у трёхголового).
Пусть в данный момент у нас имеется A – одноголовых драконов, B – двухголовых и C – трёхголовых.
Отметим, что каждая тройка чисел (A, B,C) однозначно задаёт: выиграем мы, стартуя из этой позиции, или проиграем.
Если все три числа равны 0, то в этой позиции мы проиграли (противник уже успел перерубить оставшихся драконов).
Иначе есть несколько возможных вариантов развития событий:
Если A > 0
можно перейти в (A-1,B, C) //Отрубаем 1 голову у одноголового
Если B > 0
можно перейти в (A+1,B-1,C) //Отрубаем 1 голову у двухглавого
можно перейти в (A, B-1,C) //Отрубаем 2 головы у двухглавого
Если С > 0
можно перейти в (A, B+1,C-1) //Отрубаем 1 голову у трёхглавого
можно перейти в (A+1,B, C-1) //Отрубаем 2 головы у трёхглавого
можно перейти в (A, B,C-1) //Отрубаем 3 головы у трёхглавого
Если хотя бы в одном из рассмотренных случаев нам удастся перейти в проигрышное положение, то это значит, что текущая позиция выигрышная для «М…мозга» (он сможет перевести противника в заведомо проигрышное положение), в противном случае – он сам проиграл.
Создадим трёхмерный массив W размерами [N+M+1][N+1][M+1], описывающий состояние для данного количества драконов, где в ячейке W[i][j][k] хранится
1, если начиная из такой позиции «М…мозг» выигрывает
-1, если проигрывает
0, если результат для данной ячейки ещё не определён.
(Из-за маленького объёма предоставляемой памяти размер ячейки массива не должен превышать 1 байта).
Как мы уже отметили W[0][0][0] = -1.
Так как суммарное количество голов у драконов конечно, и после каждого удара «М…мозга» оно уменьшается, то рано или поздно кто-то из «М…мозгов» окажется в этой позиции. Следовательно, запустив рекурсивно функцию заполнения массива по описанному выше алгоритму, мы сможем определить выигрышность или проигрышность исходной позиции W[0][N][M].
Таким образом, если после заполнения массива W[0][N][M] равно 1, то выигрывает первый «М…мозг», иначе – второй.
Чтобы вывести удовлетворяющие начальные ходы надо ещё раз просмотреть содержимое ячеек, описывающих события, возможно, следующие за исходным и вывести описание ударов, переводящих противника в проигрышное положение.
Сложность программы: так как, узнав значение для ячейки W[i][j][k] мы больше его не пересчитываем и 0 <= i <= N+M, 0 <= j <= N, 0 <= k <= M, то всего придётся обрабатывать не более (N+M)*N*M следовательно данная программа требует O((N+M)*N*M) времени и
O((N+M)*N*M) памяти.
//Если всего драконов четное количество, то выигрывает второй, а если нечетное – первый. Просто сложите два числа и проверьте на четность.
