#алгоритм #яндекс
Если кто не знает, на днях состоялся квалификационный раунд Яндекс.Алгоритм.2015.
Формат раунда такой, что дается 100 минут и 7 задач, которые необходимо решить. Собственно,
не сказать, что задачи сложные, но тем не менее трудности возникли.
Вообще интересно было бы устроить обсуждение вместе с участниками соревнования по
поводу решения задач. В данной теме обсуждается задача о "Размере карты".
Впрочем, любой желающий, может поучаствовать в решение данной задачи.
Условие:
Алексей — обычный пользователь интернета. Однажды, пользуясь сервисом Яндекс.Карты,
Алексей задумался: ведь наверняка итоговое изображение на экране формируется из нескольких
прямоугольных изображений меньшего размера, получаемых с сервера. Алексею стало интересно:
сколько существует возможных размеров изображений таких, что из них можно составить
картинку, видимую на экране.
Видимая область карты занимает N × M пикселей на экране Алексея. Его интересует количество
пар (A, B) (1 ≤ A ≤ N, 1 ≤ B ≤ M) таких, что прямоугольниками A × B можно выложить
прямоугольник N × M, размещая их вплотную друг с другом, без накладываний и поворотов.
При этом Алексей уверен, что посылать большие картинки с сервера очень накладно, и
поэтому его не интересуют пары (A, B), для которых A ⋅ B > R. Также Алексей понимает,
что посылать большое количество маленьких картинок тоже невыгодно, поэтому его не интересуют
пары (A, B), для которых A ⋅ B < L.
Помогите Алексею ответить на интересующий его вопрос.
Формат ввода:
Единственная строка входного файла содержит четыре целых числа N, M, L, R (1 ≤ N,
M ≤ 10^9, 1 ≤ L ≤ R ≤ N ⋅ M), разделённых пробелами.
Формат вывода:
Выведите единственное число: количество возможных пар, удовлетворяющих требованиям
Алексея.
Пример 1
Ввод
4 4 1 7
Вывод
6
Пример 2
Ввод
1 30 10 17
Вывод
2
Пример 3
Ввод
5 5 10 20
Вывод
0
Примечания:
В первом тесте возможными вариантами являются 1× 1, 1× 2, 2× 1, 2× 2, 1× 4 и 4× 1.
В во втором тесте возможными вариантами являются 1× 10 и 1× 15.
В третьем тесте произошла магия, и Алексей увидел изображение, которое никак не могло
быть составлено, если его предположения верны.
Ограничение времени: 1 секунда
Ограничение памяти: 64Mb
Ввод: стандартный ввод или input.txt
Вывод: стандартный вывод или output.txt
Ниже мой вариант решения задачи на java:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Task5
{
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int N = Integer.valueOf(line[0]);
int M = Integer.valueOf(line[1]);
int L = Integer.valueOf(line[2]);
int R = Integer.valueOf(line[3]);
int count = 0;
for (int ab = L; ab <= R; ab++)
{
//long nm = N * M;
if ((N * M) % ab == 0)
{
for (int a = 1; a <= N; a++)
{
if ((ab % a == 0) && ( ab / a <= M) && (M % (ab / a) == 0) && (N
% a == 0))
{
//System.out.println(a + " x " + ab / a);
count++;
}
}
}
}
System.out.println(count);
}
}
Заваливается он на 15 тесте, с ошибкой RE ("Ошибка во время исполнения"), подумал
я, что ошибка в размерности int, но нет, по заданию числа не превышают 10^9.
Но все же, попробовав long вместо int, 14 тест завалился с сообщением TL ("Лимит
времени исполнения"). Тогда я попробовал реализовать задачу на c++, но так и не преодолел
15 тест.
Надеюсь, что это тема не останется не замеченной.
#UPD1
Нашел еще более эффективное решение по времени:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Task5_2
{
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
long N = Integer.valueOf(line[0]);
long M = Integer.valueOf(line[1]);
long L = Integer.valueOf(line[2]);
long R = Integer.valueOf(line[3]);
ArrayList nMod = new ArrayList();
ArrayList mMod = new ArrayList();
for (long n = 1; n <= N / 2; n++)
if (N % n == 0)
nMod.add(n);
nMod.add(N);
for (long m = 1; m <= M / 2; m++)
if (M % m == 0)
mMod.add(m);
mMod.add(M);
int count = 0;
for(long n : nMod)
for (long m : mMod)
if ((n * m >= L) && (n * m <= R))
count++;
System.out.println(count);
}
}
Хотя этот вариант не решил проблему прохождения 15-го теста. По прежнему RE.
#UPD2 Собственно программа, которая проходит все 54 теста.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Task5_5_1
{
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
long N = Long.valueOf(line[0]);
long M = Long.valueOf(line[1]);
long L = Long.valueOf(line[2]);
long R = Long.valueOf(line[3]);
boolean isPrimeN = isPrime(N);
boolean isPrimeM = isPrime(M);
ArrayList divsN = new ArrayList();
ArrayList divsM = new ArrayList();
long count = 0;
if (isPrimeN)
{
divsN.add(1L);
if (N != 1) divsN.add(N);
}
else
{
ArrayList primeFactorsN = getPrimeFactors(N);
divsN = getDivs(primeFactorsN);
}
if (isPrimeM)
{
divsM.add(1L);
if (M != 1) divsM.add(M);
}
else
{
ArrayList primeFactorsM = getPrimeFactors(M);
divsM = getDivs(primeFactorsM);
}
for (long divN : divsN)
for (long divM : divsM)
{
long divNM = divN * divM;
if (divNM >= L && divNM <= R)
{
//System.out.println(divN + " x " + divM);
count++;
}
}
System.out.println(count);
}
public static boolean isPrime(long num)
{
long sqrtNum = (long) Math.sqrt(num);
for (long i = 2; i <= sqrtNum; i++)
{
if (sqrtNum % i == 0)
return false;
}
return true;
}
public static ArrayList getPrimeFactors(long num)
{
ArrayList primeFactors = new ArrayList();
for (long i = 2; i <= num / i; i++)
{
while(num % i == 0)
{
primeFactors.add(i);
num /= i;
}
}
if (num > 1)
primeFactors.add(num);
return primeFactors;
}
public static ArrayList getDivs(ArrayList primeFactors)
{
ArrayList divs = new ArrayList();
long n = primeFactors.size();
long rank = (long) Math.pow(2, n);
for (long i = 0; i < rank; i++)
{
String bin = Long.toBinaryString(i);
while (bin.length() != n)
bin = '0' + bin;
long num = 1;
for (int j = 0; j < bin.length(); j++)
{
if (bin.charAt(j) == '1')
num *= primeFactors.get(j);
}
if (!divs.contains(num))
divs.add(num);
}
return divs;
}
}
P.S. Я немного подстраховался, заведя все переменный и контейнеры типом long, хотя
по сути, можно было бы для переменный M и N выбрать тип int, но в таком случае постоянно
заваливался 15 тест, хз почему (плохо, что не предоставляется содержимое заваленных
тестов).
#UPD3 Кстати, задачу о ранжирование документов можно посмотреть тут.
Ответы
Ответ 1
Вот эта прога прошла все тесты, максимальное время 3 мс (тест #40) Program E; Type TPrime = record P: Cardinal; A, B: Integer; end; Var N, M, D: Cardinal; LL, RR: Int64; Primes: array[0..10000]of TPrime; PrimesCtr, Res: Integer; Procedure TestD; begin if (N mod D = 0) or (M mod D = 0) then with Primes[PrimesCtr] do begin P := D; A := 0; B := 0; while N mod D = 0 do begin N := N div D; inc(A); end; while M mod D = 0 do begin M := M div D; inc(B); end; inc(PrimesCtr); end; inc(D, 1 + D mod 2); end; Function Min2(x,y: Integer): Integer; begin if x < y then Result := x else Result := y; end; Function Min4(x,y,z,t: Integer): Integer; begin Result := Min2(Min2(x,y), Min2(z,t)); end; Procedure Recurs(Index: Integer; Prod: Int64; R: Integer); var L: Integer; begin if Index > 0 then begin dec(Index); with Primes[Index] do begin for L := 0 to A + B do begin if L > 0 then Prod := Prod * P; if Prod <= RR then Recurs(Index, Prod, R * (1 + Min4(L, A, B, A+B-L))); end; end; end else if Prod >= LL then inc(Res, R); end; Begin Readln(N, M, LL, RR); D := 2; PrimesCtr := 0; repeat TestD until (D*D > N) and (D*D > M); D := N; if D > 1 then TestD; D := M; if D > 1 then TestD; Res := 0; Recurs(PrimesCtr, 1, 1); Writeln(Res); End.Ответ 2
Для решения задачи необходимо так или иначе найти все делители чисел(факторизовать) N и M. Это автоматически означает экспоненциальную сложность алгоритма. Чтобы её решить быстро(за полиномиальное время или меньше) Вам необходимо либо воспользоваться 64 мегабайтной таблицей простых делителей либо раздобыть квантовый компьютер и запустить на нем алгоритм Шора. Других вариантов я не знаю и всякие выкрутасы с заменой языков программирования или переиначиванием потока управления и типов данных в наивном экспоненциальном алгоритме перебора делителей, который вы по сути предлагаете Вам никак не помогут. Скорее всего это просто шутка Яндекса.(Или может они просто все еще надеются, что какой-нибудь математик мирового уровня ВНЕЗАПНО прибежит к ним на конкурс с доказательством P=NP) Также на всякий случай прилагаю список хороших субэкспоненциальных алгоритмов факторизации, позаимствованный мной с большого SO: Число порядка 2^16: Таблица делителей. Число порядка 2^70: Модификация Ричарда Брента Ρ-алгоритма Полларда. Число порядка 10^50: Эллиптическими кривыми. Число порядка 10^100: Метод квадратичного решета. Число порядка и больше 10^100: Общий метод решета числового поля. Также рекомендую ознакомиться с хитроумной математической проблемой P=NPОтвет 3
1 ≤ N, ≤ 10^9, 1 ≤ L ≤ R ≤ N ⋅ M На M ограничение не дано. Но я предполагаю, что тоже 10^9. Тогда L и R до 10^18. Но даже если я не заметил, и где-то оговаривается, что все числа до 10^9, то if ((N * M) % ab == 0) их произведение всё равно до 10^18.Ответ 4
Факты: Найти все делители числа T можно за время O(sqrt(T)). link Для любого натурального числа T <= 10^9 количество делителей не превосходит 1500. Можете проверить... Решение: Находим делители a1,a2...an числа N. Находим делители b1,b2...bn числа M. Перебираем все возможные пары ai*bj и проверяем, что они удовлитворяют заданным условиям. Итоговая сложность O(sqrt(N*M))
Комментариев нет:
Отправить комментарий