GrabDuck

Задача о размере карт, Яндекс.Алгоритм.2015

:

Если кто не знает, на днях состоялся квалификационный раунд Яндекс.Алгоритм.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<Long> nMod = new ArrayList<Long>();
        ArrayList<Long> mMod = new ArrayList<Long>();

        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<Long> divsN = new ArrayList<Long>();
        ArrayList<Long> divsM = new ArrayList<Long>();
        long count = 0;

        if (isPrimeN)
        {
            divsN.add(1L);
            if (N != 1) divsN.add(N);
        }
        else
        {
            ArrayList<Long> primeFactorsN = getPrimeFactors(N);
            divsN = getDivs(primeFactorsN);
        }

        if (isPrimeM)
        {
            divsM.add(1L);
            if (M != 1) divsM.add(M);
        }
        else
        {
            ArrayList<Long> 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<Long> getPrimeFactors(long num)
    {   
        ArrayList<Long> primeFactors = new ArrayList<Long>();

        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<Long> getDivs(ArrayList<Long> primeFactors)
    {
        ArrayList<Long> divs = new ArrayList<Long>();
        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 Кстати, задачу о ранжирование документов можно посмотреть тут.