Question

СРОЧНО ПОЖАЛУЙСТА Хулиганы Первый и Второй очень не любят доску почёта своей школы. Поэтому они решили наглым образом украсть оттуда школьную стенгазету, сделанную отличниками, и порвать на части. Первый хулиган брал кусочек газеты и рвал его на 4 части, а Второй хулиган – на 7. Однако очень скоро дежурные нашли N кусочков этой газеты. Им стало интересно, все ли кусочки они нашли. Помогите им. Дежурные так старались, что упустить из виду они могли не более 2 кусочков. Входные данные Натуральное число N < 1018. Выходные данные Выведите “Yes”, если все кусочки найдены, и “No” – в противном случае. Пример Вход Выход 4 Yes 67 Yes 11 No

Answer 1

Ответ: Алгоритм, вроде как, нашёл (N-1/b). 

#include <iostream>

using namespace std;

int main()

{

int n, b=3, x;

start:

setlocale (LC_ALL, "Russian");

cout << "Введите число собранных кусочков: ";

cin >> n;

x=n-1;

if (x%b==0)

cout << "Yes" << endl;

else

cout << "No" << endl;

goto start;

system ("pause");

}

Answer 2

Это задача на проверку того, можно ли из заданного числа кусочков восстановить исходную газету, разорванную двумя хулиганами на определенное количество частей.

Давайте рассмотрим данную проблему. Первый хулиган разрывал газету на 4 части, а Второй на 7 частей. Чтобы найти, можно ли восстановить исходную газету из найденных дежурными кусочков, нужно использовать китайскую теорему об остатках.

Первый хулиган получает остатки от деления на 4 (0, 1, 2, 3), а Второй - на 7 (0, 1, 2, 3, 4, 5, 6). Таким образом, если мы можем найти остаток от деления количества найденных кусочков на 4 и на 7, то сможем понять, можно ли их объединить обратно в исходную газету.

Пример: - Пусть N = 4. Остаток от деления 4 на 4 равен 0. Также, остаток от деления 4 на 7 равен 4. - Пусть N = 67. Остаток от деления 67 на 4 равен 3. Остаток от деления 67 на 7 равен 5. - Пусть N = 11. Остаток от деления 11 на 4 равен 3. Остаток от деления 11 на 7 равен 4.

Теперь рассмотрим условие задачи: "Входные данные - натуральное число N < 10^18." Нам нужно определить, можно ли из этого числа вывести ответ.

Если остаток от деления числа N на 4 и на 7 соответственно равен (0, 0), то ответ "Yes". Иначе, если остаток от деления числа N на 4 и на 7 не равен (0, 0), и при этом разница между количеством найденных кусочков и нужным числом кусочков, чтобы получить остатки (0, 0), не превышает 2, то также ответ "Yes". В противном случае ответ "No".

Таким образом, если остаток от деления N на 4 и на 7 одновременно равен 0 или разница между этими остатками составляет не более 2, ответ будет "Yes", иначе - "No".