Теория:
Рассмотрим задание.
Ниже приведена программа, записанная на пяти языках программирования.
Ниже приведена программа, записанная на пяти языках программирования.
Алгоритмический язык | Python | C++ |
| алг нач цел s, t, A ввод s ввод t ввод A если \(s>5\) или \(t<A\) то вывод "YES" иначе вывод "NO" все кон | s = int(input()) t = int(input()) A = int(input()) if (\(s > 5\)) or (\(t < A\)): print("YES") else: print("NO") | #include <iostream> using namespace std; int main() { int s, t, A; cin >> s; cin >> t; cin >> A; if (\(s > 5\) || \(t < A\)) cout << "YES" << endl; else cout << "NO" << endl; return 0; } |
Было проведено \(9\) запусков программы, при которых в качестве значений переменных \(s\) и \(t\) вводились следующие пары чисел: \((5, 2)\); \((10, –5)\); \((3, 8)\); \((6, 4)\); \((1, 1)\); \((4, 10)\); \((8, 6)\); \((2, 9)\); \((7, 3)\). Укажи наибольшее целое значение параметра \(А\), при котором для указанных входных данных программа должна напечатать «YES» ровно шесть раз.
Из текста программы мы видим, что программа печатает «YES» всякий раз, когда выполняется условие: \(s > 5\) или \(t < A\).
Чтобы не запутаться в условии, составим таблицу, куда занесём все вводимые данные. Но здесь есть особенность: у нас есть параметр \(A\), значение которого мы подбираем. Поэтому сначала проанализируем ту часть условия, которая не зависит от \(A\) — это \(s > 5\).
Составим таблицу для всех \(10\) пар (\(s\), \(t\)), отметив истинность первого условия:
Чтобы не запутаться в условии, составим таблицу, куда занесём все вводимые данные. Но здесь есть особенность: у нас есть параметр \(A\), значение которого мы подбираем. Поэтому сначала проанализируем ту часть условия, которая не зависит от \(A\) — это \(s > 5\).
Составим таблицу для всех \(10\) пар (\(s\), \(t\)), отметив истинность первого условия:
№ | (s,t) | s\(>5\)? | Комментарий |
\(1\) | \((5,2)\) | \(0\) | \(5>5\)? — нет, это строгое равенство. |
\(2\) | \((10,-5)\) | \(1\) | |
\(3\) | \((3,8)\) | \(0\) | |
\(4\) | \((6,4)\) | \(1\) | |
\(5\) | \((1,1)\) | \(0\) | |
\(6\) | \((4,10)\) | \(0\) | |
\(7\) | \((8,6)\) | \(1\) | |
\(8\) | \((2,9)\) | \(0\) | |
\(9\) | \((7,3)\) | \(1\) | |
\(10\) | \((0,7)\) | \(0\) |
Важное наблюдение:
Если \(s > 5 = 1\), то программа напечатает «YES» при любом \(A\), потому что первая часть условия уже истинна (логическое «ИЛИ»).
Таких пар у нас \(4\): №\(2\), №\(4\), №\(7\), №\(9\). Это гарантированные «YES».
Если \(s > 5 = 1\), то программа напечатает «YES» при любом \(A\), потому что первая часть условия уже истинна (логическое «ИЛИ»).
Таких пар у нас \(4\): №\(2\), №\(4\), №\(7\), №\(9\). Это гарантированные «YES».
Теперь рассмотрим оставшиеся \(6\) пар (где \(s > 5 = 0\)). Для них результат программы зависит только от второго условия: \(t < A\).
Если \(t < A\) — истинно, то будет «YES».
Если \(t < A\) — ложно (т.е. \(t ≥ A\)), то будет «NO».
Нам нужно, чтобы общее количество «YES» было ровно \(6\). У нас уже есть \(4\) «YES» из первой группы. Значит, среди этих \(6\) пар должно быть ровно \(2\) «YES», а остальные \(4\) — «NO».
Выпишем значения \(t\) для этих \(6\) пар и отсортируем их:
Пары: \((5,2)\), \((3,8)\), \((1,1)\), \((4,10)\), \((2,9)\), \((0,7)\).
\(t\) \(=\) \(2\), \(8\), \(1\), \(10\), \(9\), \(7\).
Отсортированные \(t\): \(1\), \(2\), \(7\), \(8\), \(9\), \(10\).
Теперь подберём \(A\) так, чтобы ровно \(2\) из этих чисел были меньше \(A\) (и дали «YES»), а остальные \(4\) были больше или равны \(A\) (и дали «NO»).
Рассмотрим положение \(A\) на числовой прямой относительно этих чисел:
Чтобы \(t = 1\) и \(t = 2\) были меньше \(A\), нужно, чтобы \(A > 2\).
Чтобы \(t = 7\) не было меньше \(A\) (т.е. было \(≥ A\) и дало «NO»), нужно, чтобы \(A ≤ 7\).
Таким образом, искомый интервал для \(A\): \(2 < A ≤ 7\).
Нас просят указать наименьшее целое значение \(A\).
В интервале (\(2, 7\)] целые числа: \(3\), \(4\), \(5\), \(6\), \(7\).
Наименьшее из них — \(3\).
Проверка для \(A = 3\):
Достроим нашу таблицу, вычислив второе условие и итоговое «ИЛИ».
№ | (s,t) | \(s>5\) | \(t<3\) | \(s > 5\) или \(t < A\) | Результат |
\(1\) | \((5,2)\) | \(0\) | \(1\) | \(1\) | YES |
\(2\) | \((10,-5)\) | \(1\) | \(1\) | \(1\) | YES |
\(3\) | \((3,8)\) | \(0\) | \(0\) | \(0\) | NO |
\(4\) | \((6,4)\) | \(1\) | \(0\) | \(1\) | YES |
\(5\) | \((1,1)\) | \(0\) | \(1\) | \(1\) | YES |
\(6\) | \((4,10)\) | \(0\) | \(0\) | \(0\) | NO |
\(7\) | \((8,6)\) | \(1\) | \(0\) | \(1\) | YES |
\(8\) | \((2,9)\) | \(0\) | \(0\) | \(0\) | NO |
\(9\) | \((7,3)\) | \(1\) | \(0\) | \(1\) | YES |
\(10\) | \((0,7)\) | \(0\) | \(0\) | \(0\) | NO |
Считаем количество «YES» в последнем столбце: \(6\) (пары № \(1\), \(2\), \(4\), \(5\), \(7\), \(9\)). Всё верно.
Правильный ответ: \(3\).
На что стоит обратить внимание
- В условии задачи переменные (s, t) могут вводиться в обратном порядке. Всегда проверяем, чтобы ввод s, ввод t в самой программе совпадали с порядком переменных в задании: «...вводились следующие пары чисел (s, t)».
- Обращаем внимание на знаки неравенств — включены ли границы интервалов? В нашем примере \(5\) не удовлетворяет условию \(s > 5\), так как неравенство строгое. А условие \(t < A\) — тоже строгое.
- Если в задаче спрашивают конкретное значение параметра \(A\), удобно сначала отделить пары, где первая часть условия (не зависящая от \(A\)) уже даёт «YES», а затем работать со второй частью как с самостоятельным условием.
- При ответе на вопрос «Наибольшее/наименьшее целое \(A\)» обязательно проверяем граничные значения интервала.