Розв'язник вправ по дискретній математиці/Комбінаторика
Розв'язник вправ по дискретній математиці. Комбінаторика
[ред.]Задача 1
[ред.]а) Яких чисел більше серед цілих чисел першої тисячі (включаючи і 1000): в записі яких є одиниця, або інших? б) Яких семизначних чисел більше: тих, в запису яких є одиниця, або інших?
а) Є тризначних чисел, що не містять 1 і 0. Це вже більше половини чисел першої тисячі.
Відповідь: більше чисел, в запису яких немає одиниці;
б) Підрахуємо кількість чисел, в запису яких немає одиниці. На першому місці може стояти кожна з 8 цифр (0 і не 1), на кожному з решти - будь-яка з 9 цифр, відмінних від 1. Всього отримуємо чисел, що становить менше половини від кількості 9 · 10^6 всіх семизначних чисел.
Відповідь: більше чисел, в запису яких є одиниця.
Задача 2
[ред.]Скількома способами 3 людини можуть розділити між собою 7 однакових яблук, один апельсин, одну сливу і один мандарин?
Формула для розподілу k однакових речей серед n різних людей: F (k, n) = C (n-1, n + k-1);
C(2,9)=9!/(7!*2!)= 36;
"Поодинокі" фрукти можуть дістатися кожному з трьох, тоді: способів.
Відповідь: 972 способів;
Задача 3
[ред.]- Розв'язати завдання з leetcode.com (Count Sorted Vowel Strings). Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.
A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.
Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].
Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.
Input: n = 10
Output: 1001
Задача 4
[ред.]- Розв'язати завдання з leetcode.com (Pairs of Songs With Total Durations Divisible by 60). You are given a list of songs where the ith song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Input: time = [418,204,77,278,239,457,284,263,372,279,476,416,360,18]
Output: 1
Explanation: (457 + 263) - only one pair
Задача 5
[ред.]- Розв'язати завдання з leetcode.com (62. Unique Paths). На сітці m x n знаходиться робот. Спочатку робот знаходиться у лівому верхньому куті (тобто grid[0][0]). Робот намагається переміститись у правий нижній кут (тобто grid[m - 1][n - 1]). У довільний момент часу робот може рухатись лише вниз або праворуч.
За заданими двома цілими числами m та n виведіть кількість можливих унікальних шляхів, якими робот може дістатись до правого нижнього кута.
Вхідні дані: m = 3, n = 2
Результат: 3
Пояснення: З лівого верхнього кута можна дістатись до правого нижнього кута 3 способами:
1. Праворуч -> Вниз -> Вниз
2. Вниз -> Вниз -> Вправо
3. Вниз -> Вправо -> Вниз
Задача 6
[ред.]- Розв'язати завдання з leetcode.com (3185. Count Pairs That Form a Complete Day II). За заданим цілочисельним масивом hours, що представляє час у годинах, поверніть ціле число, яке позначає кількість пар i, j, де i < j за умови, що hours[i] + hours[j] утворюють повний день.
Повна доба визначається як тривалість часу, яка кратна 24 годинам.
Наприклад, 1 день - це 24 години, 2 дні - 48 годин, 3 дні - 72 години і так далі.
Вхід: hours = [12,12,30,24,24]
Результат: 2
Пояснення: Парами індексів, які формують повний день, є (0, 1) та (3, 4).
Вхід: hours = [72,48,24,3]
Результат: 3
Пояснення: Парами індексів, які формують повний день, є (0, 1), (0, 2) та (1, 2).