Вам задано два слова, каждое из которых состоит из заглавных английских букв. Удалите из них несколько букв так, чтобы в результате получились одинаковые слова.
Найдите максимально возможную длину полученного слова.
Входные данные
Каждый тест состоит из одной строки, содержащей два заданных слова, разделенных пробелом. Длина каждого слова от $1$ до $200$ символов. Всего имеется не более $10$ тестов.
Выходные данные
Для каждого теста выведите максимально возможную длину полученных одинаковых слов (длину максимального слова, которое можно получить путем удаления некоторых букв). Если одинаковые слова получить невозможно, то выведите $0$.
Тесты
Входные данные
Выходные данные
AAABBB ABABAB
AXYAAZ CCCXCCCYCCCZCC
4
3
AAAAA BBBBB
0
ABABA BCACB
3
STRING GNIRTS
1
String
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
usingnamespacestd;
intmain(){
stringx,y;
intA[2][1001];
while(cin>>x>>y)
{
for(inti=0;i<2;i++){
for(intj=0;j<1001;j++){
A[i][j]=0;
}
}
for(inti=0;i<x.size();i++){
for(intj=0;j<y.size();j++){
if(x[i]==y[j])A[i%2][(j+1)]=1+A[(i+1)%2][j];
elseA[i%2][j+1]=max(A[(i+1)%2][j+1],A[i%2][j]);
}
}
cout<<A[(x.size()+1)%2][y.size()]<<endl;
}
return0;
}
C-String
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstring>
usingnamespacestd;
intmain(){
stringx,y;
intA[2][1001];
while(cin>>x>>y)
{
for(inti=0;i<2;i++){
for(intj=0;j<1001;j++){
A[i][j]=0;
}
}
for(inti=0;i<x.length();i++){
for(intj=0;j<y.length();j++){
if(x[i]==y[j])A[i%2][(j+1)]=1+A[(i+1)%2][j];
elseA[i%2][j+1]=max(A[(i+1)%2][j+1],A[i%2][j]);
}
}
cout<<A[(x.length()+1)%2][y.length()]<<endl;
}
return0;
}
Решение задачи
Алгоритм поиска слова отдаленно напоминает таковой у алгоритма при поиске расстояния Левенштейна. В процессе сравнения буквы первого слова с буквами второго, нам понадобится информация о сравнениях предыдущей буквы слова. Для хранения этой информации создадим двумерный массив. Если буквы равны, увеличим уже полученную длину на один и передадим ее элементу массива, в котором будет храниться информация о сравнениях следующей буквы первого слова, в противном случае оценим максимальную возможную длину на данном этапе.
Ссылки
Условие задачи на сайте E-Olymp
код задачи (string) на Ideone
код задачи (c-string) на Ideone
описание расстояния Левенштейна на Wikipedia
Дан список мин. Требуется составить поле для игры в сапер.
Входные данные
Даны числа $N$ и $M$ (целые, положительные, не превышают $32$) — количество строк и столбцов в поле соответственно, далее число $W$ (целое, неотрицательное, не больше $100$) — количество мин на поле, далее следует $W$ пар чисел, координаты мины на поле (первое число — строка, второе число — столбец).
Выходные данные
Требуется вывести на экран поле. Формат вывода указан в примере.
Для хранения координат мин будем использовать двумерный массив. Все ячейки массива, используемые под поле, и их окружающие следует заблаговременно обнулить, чтобы получить точное количество мин при подсчете.
На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.
Входные данные
В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].
Выходные данные
Искомое число [latex]k[/latex].
Тесты
Входные данные
Выходные данные
5
2 -1
3 0
0 4
-3 0
-2 1
6
5
0 0
2 4
6 6
10 34
-42 -48
10
4
0 0
0 1
1 0
1 1
0
8
0 0
2 2
1 1
3 3
0 1
2 1
1 0
1 2
24
5
0 0
0 1
-1 0
-1 -1
3 -3
3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
usingnamespacestd;
intmain(){
unsignedintn,x1,x2,x3,y1,y2,y3,A[4]={0,0,0,0};
unsignedlonglongc=0;
cin>>n;
for(inti=0;i<n;i++){
cin>>x1>>y1;
if(x1%2==0andy1%2==0)A[0]++;
elseif(x1%2==1andy1%2==0)A[1]++;
elseif(x1%2==0andy1%2==1)A[2]++;
elseA[3]++;
}
for(inti=0;i<4;i++){
for(intj=0;j<4;j++){
if(i==j)c+=A[i]*(A[i]-1)*(A[i]-2)/6;
elsec+=A[i]*(A[i]-1)*A[j]/2;
}
}
cout<<c;
return0;
}
Решение задачи
Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.
В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex]-й для распевки поёт гамму.
Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.
Входные данные
Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex]. ([latex]1 ≤ N, M ≤ 103[/latex]).
Выходные данные
Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».
Пусть у нас есть [latex]N[/latex] певцов. Пронумеруем их по порядку от [latex]0[/latex] до [latex]N — 1[/latex]. Распевается каждый [latex]M[/latex]-й. И пусть НОД ([latex]M, N) = k \geq 2[/latex]. Тогда, например, [latex]k — 1[/latex]-ый певец никогда не распоется. На рисунке ниже приведен пример. [latex]6[/latex] певцов, распевается каждый [latex]2[/latex], начиная из верхнего левого угла при смене по часовой стрелке. Переливающимся кружочком обозначен поющий в данный момент певец.
Докажем, что если [latex]M[/latex] и [latex]N[/latex] взаимно просты, то все участники распоются. Для начала заметим, что при [latex]i[/latex]-ой смене (где [latex]i[/latex] некоторое натуральное число) очередь вернется к участнику, с которого распевка начиналась,то есть смена циклическая. Поскольку НОД ([latex]M, N) = 1 [/latex], то НОК ([latex]M, N) = M*N [/latex], то есть распевающий сменится [latex]N[/latex] раз для завершения цикла. Покажем, что ни один из певцов не споет более [latex]1[/latex] раза. Пусть есть некоторый [latex]k[/latex]-ый распевающий, очередь которого наступила более [latex]1[/latex] раза за время цикла. Однако, как и для первого распевающего, очередь для [latex]k[/latex] наступит через [latex]N[/latex] смен, то есть после завершения цикла. Получили опровержение. Значит каждый распоется не более [latex]1[/latex] раза. Теперь, учитывая количество смен, получим, что каждый распоется ровно [latex]1[/latex] раз. В случае, когда НОД ([latex]M, N) \geq 2 [/latex] получим, что за цикл распоется менее, чем [latex]N[/latex] участников хора.
“Название задачи можно напевать на мотив марша или строевой песни…”
Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?
Входные данные
Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).
Выходные данные
Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].
Тесты
Входные данные
Выходные данные
1
0
10000
30397485
5
9
80
1965
37
431
5168
8119803
9973
30237929
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
usingnamespacestd;
inteuler_f(intn){
intresult=n;
for(inti=2;i*i<=n;++i){
if(n%i==0){
while(n%i==0)n/=i;
result-=result/i;
}
}
if(n>1)result-=result/n;
returnresult;
}
intmain(){
intn;
cin>>n;
intsum=0;
for(inti=2;i<=n;++i){
sum+=euler_f(i);
}
cout<<sum;
return0;
}
Решение задачи
Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).
Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.
Входные данные
Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].
Выходные данные
Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].
Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]H[/latex] — высота картины.
1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой
1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]
1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]H[/latex]
В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]
1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]H[/latex]
в таком случае нам необходимо найти дугу [latex]NX_1[/latex],для этого умножив радиус на величину центрального угла: [latex]NX_1[/latex] =[latex]X_0 X_1 \times \arcsin \frac {H}{X_0 X_1}[/latex]
1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]
1.1.2.1.[latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]
1.1.2.1.1. [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]
В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times \arcsin \frac{X_0 X_3} {X_0 X_1} [/latex]
1.1.2.1.2. [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]
В таком случае искомая величина равна дуге [latex]MN[/latex]= [latex]X_0 X_1 \times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{X_0 X_3} {X_0 X_1}))
1.1.2.2. данный случай аналогичен предыдущему.Единственное различие заключается в том,что точки [latex]X_2[/latex] и [latex]X_3[/latex] меняются местами в формулах.
1.2 [latex]Х_0[/latex] не принадлежит [latex]X_2[/latex][latex]X_3[/latex]
В этом случае длина разрыва будет равна длине отрезка [latex]MN[/latex] либо высоте картины, если она окажется меньше вышеупомянутого отрезка.
Для того, чтобы не рассматривать случаи, в которых искомая величина равна нулю (все оставшиеся), при создании переменной, в которой будем хранить ответ, сразу приравняем ее к нулю.
Ученики 10-Б класса на осенние каникулы решили поехать на экскурсию в столицу. Зная количество мальчиков [latex]n[/latex] и девочек [latex]m[/latex], определить, сколько необходимо заказать комнат в отеле, в котором имеются комнаты на [latex]k[/latex] мест каждая, при условии что мальчиков и девочек поселять вместе запрещено.
Входные данные
В одной строке записаны три числа [latex]n[/latex], [latex]m[/latex], [latex]k[/latex] ([latex]n, m, k ≤ 100[/latex]).
Выходные данные
Вывести одно число — количество комнат, которое необходимо забронировать в отеле. Continue reading →
