На острове Буяне жили N человек, каждый из которых был либо рыцарем либо лжецом, встали в круг. Рыцари говорят только правду, лжецы всегда только лгут. Каждому человеку в кругу задали вопрос: «Кто ты и кто твой сосед слева: рыцарь или лжец?» При этом каждый человек сказал, что он – рыцарь. А ответы всех людей о левом соседе были записаны в следующем формате: 1 – рыцарь 0 – лжец. Все ответы записаны в строку через пробел. Последний спрошенный человек отвечал на вопрос о первом.
Написать программу, которая по ответам жителей определяет, какое количество рыцарей заведомо присутствует в круге.
Входные данные
Первое число ( 1 < N ≤ 255 ) - количество жителей. Следующие N чисел (0 или 1), разделенных пробелами - ответы жителей.
———-
Уже четвертый день пытаюсь составить алгоритм. Может кто подскажет, как к таким задачам подходить нужно?
Полная версия: Задача про рыцарей и лжецов
Я решил ее вот так, возможно есть другой способ, но этот проходит тестирование
n = int(input()) answer = input().split() res, res1, flag, flag1 = 0, 0, True, False for i in range(n): # ПЕРВЫЙ ГОВОРИТ ПРАВДУ if i != n-1: if flag: # проверяемый говорит правду if answer[i] == '0': # если проверяемый говорит что следующий врет res += 1 flag = False # не важно что скажет следующий потому что это будет лож и нужно сменить flag elif answer[i] == '1': # если проверяемый говорит что следующий говорит правду res += 1 # то flag не меняется потому что следующий говорит правду else: # если проверяющий врет if answer[i] == '0': # если проверяемый говорит что следующий врет и сам при этом что врет, то следующий говорит правду flag = True # меняем флаг # если проверяемый говорит что следующий говорит правду и сам при этом врет, то следующий врет else: # проверяем последнего с первым if flag: # проверяемый говорит правду if answer[i] == '1': # если проверяемый говорит что первый говорит правду res += 1 elif answer[i] == '0': # если проверяемый говорит что первый врет flag = False # не важно что скажет первый потому что это будет лож и нужно сменить flag for i in range(n): # ПЕРВЫЙ ВРЕТ if i != n-1: if not flag1: # проверяемый заведомо врет if answer[i] == '0': # если проверяемый говорит что следующий врет и сам при это врет, то следующий говорит правду flag1 = True # меняем флаг # если проверяемый говорит что следующий говорит правду и сам при этом врет и сам при это врет, то следующий врет else: # проверяемый говорит правду if answer[i] == '0': # если проверяемый говорит что следующий врет и сам при это говорит правду, то следующий врет res1 += 1 flag1 = False # меняем флаг elif answer[i] == '1': # если проверяемый говорит что следующий говорит правду и сам при говорит правду, то следующий говорит правду res1 += 1 else: # проверяем последнего с первым if not flag1: # проверяемый заведомо врет if answer[i] == '0': # если проверяемый говорит что следующий врет и сам при это врет, то следующий говорит правду flag1 = True # меняем флаг # если проверяемый говорит что следующий говорит правду и сам при этом врет и сам при это врет, то следующий врет else: # проверяемый говорит правду if answer[i] == '0': # если проверяемый говорит что следующий врет и сам при это говорит правду, то следующий врет res1 += 1 flag1 = False # меняем флаг elif answer[i] == '1': # если проверяемый говорит что следующий говорит правду и сам при говорит правду, то следующий говорит правду res1 += 1 print(res if res <= res1 else res1)
У меня решение получилось короче.
Опытным путем получаем, что для каждого ряда чисел подходят 2 варианта расположения. Например для 1111 - РРРР и ЛЛЛЛ, для 1001 - ЛРЛЛ и РЛРР. Можно заметить, что инвертируются значения. Поэтому считаем 2 варианта, когда первый лжец и первый рыцарь. В результат выводим минимальное.
Опытным путем получаем, что для каждого ряда чисел подходят 2 варианта расположения. Например для 1111 - РРРР и ЛЛЛЛ, для 1001 - ЛРЛЛ и РЛРР. Можно заметить, что инвертируются значения. Поэтому считаем 2 варианта, когда первый лжец и первый рыцарь. В результат выводим минимальное.
n = int(input()) answer = list(map(int, input().split())) #first - lier cur_p = 0 #first person type knights_1 = 0#counter for i in reversed(answer): next_p = abs(i-1) if cur_p==0 else i #next person type knights_1 += next_p cur_p = next_p #for next iteration #first - knight cur_p = 1 #first person type knights_2 = 0#counter for i in reversed(answer): next_p = abs(i-1) if cur_p==0 else i #next person type knights_2 += next_p cur_p = next_p #for next iteration print(min(knights_1,knights_2))
Господа -товарищи! Мне кажется, что задача эта не вполне корректна. Быть может я не прав, тогда поправьте меня. Речь о том, что не все входные значения допустимы. Например: жителей - 5, опрос (т.е. входные данные) - 00000. Тогда, следуя условиям задачи, получим, если первый - лжец, истинное распределение - 01010, а если первый -рыцарь, то - 10101. В обоих вариантах получаем противоречие, поскольку последний житель о первом жителе либо, являясь лжецом, сказал правду, либо, являясь рыцарем, соврал. Таких противоречий можно привести в качестве примера бесконечно много. Скажем, N = 4 при входных данных 1000 или N = 6 при 010000.
Приведённые вами алгоритмы - работают, но они не учитывают эти противоречия. Полагаю, что авторы этой задачи также не учли этот почти “расселовский” парадокс.
В общем, либо я, надеюсь, ошибаюсь, либо задачу следует переформулировать.
VashomНапример, жителей двое.
Речь о том, что не все входные значения допустимы. Например: жителей - 5, опрос (т.е. входные данные) - 00000.
00 - подходит для лжец и рыцарь (лжец говорит, что рыцарь - это лжец, а рыцарь говорит, что лжец - это лжец)
01 - не подходит вообще ни под что
10 - не подходит вообще ни под что
11 - подходит для рыцарь и рыцарь (рыцарь говорит, что рыцарь - это рыцарь, а рыцарь говорит, что рыцарь - это рыцарь)
Так что для двух жителей уже есть неподходящие последовательности. Соответственно, они же есть и для большего числа жителей. Вопрос в том, кто их будет подавать, эти неподходящие последовательности?
Решил задачу вот таким способом, но последний тест я проваливаю. Пару дней не могу понять, где я конкретно ошибся. Помогите понять, что я сделал не так.
def num_knights(A, flag=True): knights = 0 for i in range(len(A)): if flag: if A[i] == '0': knights += 1 flag = False else: knights += 1 else: if A[i] == '0': flag = True return knights N = int(input()) answers = str(input()) A = answers.split(' ') x = num_knights(A) y = num_knights(A, False) if x >= y: print(y) else: print(x)
Koba_mk2
Решил задачу вот таким способом, но последний тест я проваливаю. Пару дней не могу понять, где я конкретно ошибся. Помогите понять, что я сделал не так.
Скорее всего ты исчерпал лимит по памяти (в данном задании есть такое ограничение), потому что дублируешь в память список A = answers.split(' '). При вводе/сборе данных используй:
answers = input().split() #список формируется без ограничений
либо:
answers = input().split() #список формируется из не более N элементов
Ну и далее в параметрах функций используй answers.
Мне кажется, я придумал отличнейшее, элегантнейшее решение, но оно не проходит тест 8 
Есть подозрение, что в нем некорректные входные данные. Как уже ранее писали тут, не каждая комбинация 0 и 1 подходит для решения задачи. Если нулей будет нечетное кол-во, то задачку не решить, получится эдакая последовательность Мебиуса. Короче, функция:
Есть подозрение, что в нем некорректные входные данные. Как уже ранее писали тут, не каждая комбинация 0 и 1 подходит для решения задачи. Если нулей будет нечетное кол-во, то задачку не решить, получится эдакая последовательность Мебиуса. Короче, функция:
def counter(n, answers): roles = [0] * n roles[0] = 1 for i in range(1, len(answers)): roles[i] = int(answers[i] == roles[i - 1]) if answers[0] != roles[-1]: return ("неверные входные данные") return min(sum(roles), len(answers) - sum(roles))