Задача 572А

Даны два отсортированных по неубыванию массива A и B, состоящих из целых чисел. Проверьте, можно ли в массиве Aвыбрать k чисел, а в массиве B — выбрать m чисел так, что любое число, выбранное в первом массиве, строго меньше любого числа, выбранного во втором массиве.

Входные данные

В первой строке заданы два целых числа nA, nB (1 ≤ nA, nB ≤ 105), разделенные пробелом — размеры массивов A и B, соответственно.

Во второй строке записаны два челых числа k и m (1 ≤ k ≤ nA, 1 ≤ m ≤ nB), разделенные пробелом.

В третьей строке записаны nA чисел a1, a2, … anA ( - 109 ≤ a1 ≤ a2 ≤ … ≤ anA ≤ 109), разделенных пробелами — элементы массива A.

В четвертой строке записаны nB чисел b1, b2, … bnB ( - 109 ≤ b1 ≤ b2 ≤ … ≤ bnB ≤ 109), разделенных пробелами — элементы массива B.

Выходные данные

Выведите «YES» (без кавычек), если в массиве A можно выбрать k чисел, а в массиве Bm чисел так, любое выбранное в массиве A число строго меньше любого выбранного в массиве B числа. В противном случае выведите «NO» (без кавычек).

Примеры тестов
входные данные

выходные данные

входные данные

выходные данные

входные данные

выходные данные

Примечание

В первом тестовом примере, можно например, выбрать числа 1 и 2 из массива A и число 3 из массива B (1 < 3 и 2 < 3).

Во втором тестовом примере единственный способ выбрать k элементов в первом массиве и m элементов во втором — выбрать все числа в обоих массивах, но тогда не все выбранные числа в A будут меньше, чем все выбранные в B: .

Моё решение:

Сперва слегка смутило «по неубыванию», но потом включилась алгебра логики и выражение легко превратилось в «по возрастанию». Ошибкой было то, что я опять позабыл про то, что JavaScript не обязательно переведет строку в число перед сравнением.  Только утром на дорешивании исправил свою оплошность. Теперь всякий раз, когда нужно будет получить числа, а не строки то просто на всякий случай ввод переведу явно из строк в числа.

Само решение простое. сравниваем k самых маленьких чисел первого массива с самыми большими m числами второго массива. Учитывая, что оба массивы уже отсортированными к нам приходят, то проблем вообще ни каких нет.

 

Оригинал задачи

(Просмотров всего: 168, просмотров сегодня: 1)

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *