Задача №114771. Задача для третьеклассника
Примеры корректных выражений:
- \(1\)
- \(1 + 1\)
- \((1 + 1) \cdot (1 + 1) + 1\)
- \((1 + (1 + 1) + (1))\)
Примеры некорректных выражений:
- \((1\)
- \((((()\)
- \(111\)
- \((1+1)^{1+1+1+1}\)
Даны \(q\) запросов из двух чисел \(n_i\), \(a_i\). Для каждого запроса требуется вывести минимальное \(b_i\), такое что \(n_i\) можно породить с помощью не более \(a_i\) сложений и не более \(b_i\) умножений. Если такого \(b_i\) не существует, выведите \(-1\).
В первой строке даны 2 числа \(q\), \(g\) (\(1 \leq q \leq 10^6, 0 \leq g \leq 1\)) — количество запросов и флаг – правда ли, что этот тест относится к первой группе тестов (1 — относится или 0 — не относится).
В следующих \(q\) строках содержатся пары целых чисел \(n_i, a_i\) (\(1 \leq n_i \leq 5 \cdot 10^5, 0 \leq a_i \leq 5 \cdot 10^5\)) — число, которое нужно породить, и максимальное допустимое число сложений для данного запроса.
Для каждого запроса выведите в отдельной строке минимально возможное \(b_i\), или \(-1\), если его не существует.
Возможные варианты для выражений для теста из условия:
- Невозможно используя только \(1\) \(+\) и сколько угодно \(\cdot\) породить \(10\).
- \(((1 + 1) \cdot (1 + 1)) \cdot (1 + 1 + 1) = 12\)
- \((1 + 1 + 1 + 1 + 1) \cdot (1 + 1) = 10\)
- \((1 + 1 + 1 + 1) \cdot (1 + 1 + 1 + 1) + 1 = 17\)
- \((1 + 1 + 1) \cdot (1 + 1 + 1) = 9\)
- \((1 + 1 + 1 + 1) \cdot (1 + 1 + 1) = 12\)
- \(1 + 1 = 2\)
- \((1 + 1 + 1) \cdot (1 + 1) + 1 = 7\)
- \((1 + 1 + 1 + 1) \cdot (1 + 1 + 1) = 12\)
- \((1 + 1 + 1 + 1 + 1 + 1) \cdot (1 + 1 + 1) = 18\)
Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n_i\), \(a_i\) | \(b_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия |
| 1 | 6 | – | \(b_i = 1 \) или ответ \(-1\) | – | |
| 2 | 12 | \(n_i \le 400\), \(a \le 20\) | – | 0 | |
| 3 | 15 | \(a_i \le 20\) | – | 0, 2 | |
| 4 | 13 | \(a_i \le 30\) | – | 0, 2 – 3 | |
| 5 | 12 | \(a_i \le 40\) | – | 0, 2 – 4 | |
| 6 | 11 | \(a_i \le 60\) | – | 0, 2 – 5 | |
| 7 | 31 | – | – | 0 – 6 | |
10 0 10 1 12 4 10 5 17 7 9 4 12 5 2 1 7 4 12 5 18 7
-1 2 1 1 1 1 0 1 1 1