5.1. С одного дерева сняли Х груш, а со второго 5 мальчиков, каждый из которых сидя на дереве, съел по 17 груш. После этого со второго дерева сняли еще Ү груш. Составить
программу, которая определит, сколько груш было на обоих деревьях.
Входные данные: 65 45
Выходные данные: 195
Программа будет иметь примерно такую структуру:
multimap<string, ...> subprefixes
input n
n times:
input s
for j = 0..size of s:
if s[..j] is subprefix of s:
subprefixes.insert(pair<string, ...>(s[..j], ...))
input m
m times:
input s
print subprefixes.count(s)
Остался вопрос, как определять, является ли s[..j] супрефиксом. Конечно, можно это делать наивно: пройти циклом для всех возможных длин подстрок j и проверить, правда ли, что s[0] = s[s.size() - j - 1], s[1] = s[s.size() - j]...
Как можно ускорить всё это?
1) Выберем какое-нибудь достаточно большое (по сравнению с кодами символов) простое число x, например, x = 1009. Вычислим для строки s все хеши по формуле
Теперь если у строки s длины k есть супрефикс длины j, то обязательно
2) Необязательно хранить в multimap-е подстроки, это дорого и по времени и по памяти. Можно хранить хеши.
3) Можно вместо одного multimap-а создать 50 multimap-ов, в каждом хранить только супрефиксы одной длины.
Получаем примерно такое:
pow = new long long[51]
pow[0] = 1
for i = 1..50:
pow[i] = x * pow[i - 1]
suprefixes = new multimap<long long, ...>[51]
input n
n times:
input s
h = hashes(s)
k = len s
for j = 1..k:
if h[j] * pow[k - j] == h[k] - h[k - j - 1]:
suprefixes[j].insert(pair(h[j], ...))
input m
m times:
input s
print puprefixes[len s].count(hash(s))
В принципе, для такого решения multimap не нужен, достаточно иметь map, и хранить для каждого ключа количество вхождений. Это можно делать и для multimap.
n := 7+9*((2570-35) div d + 1)
196 = 7+9*((2570-35) div d + 1)
(196-7)/9-1 = (2570-35) div d
20 = 2535 div d
4 = 507 div d
507/4 =126.75, значит можно взять меньше
подбором 126 125 124 123 122 121 => 6 чисел
или программой
//PascalABC.NET версия 3.2, сборка 1389
//Если программа не запускается, то обновите версию
function f(d: integer): integer;
var
n, s: integer;
begin
n := 7;
s := 35;
while s <= 2570 do
begin
s := s + d;
n := n + 9
end;
f := n;
end;
begin
for var i := 1 to 100000000 do
begin
if f(i) = 196 then writeln(i);
if f(i) <> 7 + 9 * ((2570 - 35) div i + 1) then writeln('not ', i);
end;
end.