Задача
Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.
Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.
Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).
Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.
Входные данные
В первой строке заданы числа $n$ и $m$ $(1 ≤ n, m ≤ 1000)$.
Выходные данные
Выведите одно число — количество учеников, которые в результате пересадки остануться сидеть на тех же местах.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 3 3 | 3 |
| 2 | 3 4 | 2 |
| 3 | 6 3 | 2 |
| 4 | 5 9 | 5 |
| 5 | 7 5 | 3 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; int main() { int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) arr[i][j] = count1++; for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) { if (arr[i][j] == count2) result++; count2++; } } cout << result << "\n"; } |
Код программы с линейным массивом
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> using namespace std; int main() { int arr[1000 * 1000], n, m, result = 0; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) arr[i * m + j] = i * m + j; for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) if (arr[i * m + j] == j * n + i) result++; cout << result << "\n"; } |
Код программы без массива
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int main() { int n, m, result = 0; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (i * m + j == j * n + i) result++; cout << result << "\n"; } |
Решение задачи
Для решения задачи проверяем значения до пересадки и после, если они совпадут соответственно, то инкрементируем счётчик. А в конце выводим результат.
У данной задачи есть решение за $O(1)$. Было бы интересно подумать над ним.
Ну почти, за $O(log(max(n, m)))$, но по сравнению с $O(n\cdot m)$, это действительно выглядит как $O(1)$.
Пожалуйста, исправьте отступы и подумайте над предложением Олега.
Большое спасибо, исправила. Обещаю подумать.
Отступы вы не исправили.
Вы правы, уже исправила 🙂
Не всё правильно исправили.
Спасибо, учла все замечания.
Отступы!
То сколько раз Вам об этом пишут, наталкивает меня на мысль, что вы используете и пробелы, и табудяции одновременно. Поскольку нет закона природы, который устанавливает количество пробелов в табуляции, то у вас от редактора к редактору все и пляшет.
Хорошо. Если будет время, подумайте над вопросом Олега — как быстро решить эту задачу без массивов. Циклы или рекурсия все же понадобятся.
А в качестве технического упражнения сделайте еще один вариант кода с линейным массивом, хорошо?
Спасибо за замечание, все сделала.
Молодец. Решение о котором писал Олег можно посмотреть здесь.