Question

В операционной системе Winux многозадачность реализована следующим образом: каждую секунду задача, которая была активна (то есть находилась в начале списка задач), ставится в конец списка задач, а все остальные задачи сдвигаются на одну к началу. В одной очень секретной лаборатории компьютер под управлением Winux используется для решения вычислительных задач. Вычислениями занимается задача solve. С утра список состоял из N задач, причём задача solve существовала в нескольких экземплярах, каким-то образом распределённых по списку. Вечером в списке по-прежнему было N задач; более того, все экземпляры задачи solve были ровно на тех же местах в списке, что и с утра, но при этом список задач в целом различался (то есть на какой-то позиции с утра и вечером стояли разные задачи). При этом за день ни одна задача не должна была завершиться и ни одна новая задача не должна была быть запущена. Вы — разработчик модуля защиты информации в системе Winux. Ваша задача — по заданному N определить, обязательно ли из полученной информкции следует, что как минимум одна задача завершилась и как минимум одна задача была запущена, или же ситуация могла произойти естественным образом. Так как лаборатория секретная, никакой другой информации, кроме числа задач, у Вас нет. Формат ввода Входные данные содержат одно целое число N ( 2 ≤ N ≤ 1 0 9 ). Формат вывода Выведите “Danger”, если непредвиденный запуск задачи гарантированно произошёл, или “Safe” в противном случае. Пример 1 Ввод Вывод 5 Danger Пример 2 Ввод Вывод 6 Safe Примечания Решением этой задачи должна являться программа на одном из представленных в системе языков программирования, решающая данную задачу. Программа должна считывать данные со стандартного ввода (клавиатуры) и выводить на стандартный вывод (монитор). Никаких дополнительных строк или символов выводить не разрешается.

Answer 1

Само объяснение очень большое. Делится им смысла не вижу. В целом все сводится к проверке числа на простоту. Причем надо это сделать с помощью быстрого алгоритма.

Следующее решение приведено на языке Python 3.4.3:

def is_prime( num ):

   d = 2

   while d * d <= num and num % d != 0:

        d += 1

   return d * d > num

N = int( input() )

if is_prime( N ):

   print( 'Danger' )

else:

   print( 'Safe' )

Answer 2

Для решения данной задачи нужно проанализировать, как поведение задач в списке меняется с течением времени. Мы знаем, что задачи остаются на тех же местах, но в списке по-прежнему остаются N задач. Это значит, что ни одна задача не была завершена, и никакая новая задача не была запущена.

Предположим, что в списке из N задач есть M экземпляров задачи "solve" (где 1 ≤ M ≤ N-1). Рассмотрим два случая:

1. M = 1: В списке есть только один экземпляр задачи "solve". Каждую секунду он будет перемещаться на одну позицию к началу списка, но ни одна другая задача не будет перемещаться в конец. Значит, никогда не возникнет ситуации, когда "solve" окажется на последней позиции, что бы привело к его запуску или завершению. Таким образом, ситуация может произойти естественным образом. Вывод: Safe.

2. M > 1: В списке есть несколько экземпляров задачи "solve". Теперь, каждую секунду, самый ближний к концу списка экземпляр "solve" перемещается на одну позицию к началу, и каждый другой экземпляр смещается к началу на M позиций. Таким образом, если один из экземпляров "solve" находится на позиции i, то через N шагов он окажется на позиции i - M*N. Это означает, что через некоторое количество шагов он окажется на отрицательной позиции, что не возможно, так как индексы задач в списке не могут быть отрицательными.

Таким образом, если в списке более одного экземпляра задачи "solve", то ситуация, в которой никакая задача не была запущена или завершена, невозможна. Вывод: Danger.

Итак, чтобы определить, обязательно ли возникновение новой задачи и завершение текущей, нужно проверить, сколько раз "solve" встречается в списке:

• Если M = 1, то вывод: Safe.
• Если M > 1, то вывод: Danger.

Пример 1: Ввод: 5 Вывод: Danger

Пример 2: Ввод: 6 Вывод: Safe