Python-сообщество

Novelette · Авг. 6, 2019 15:13:03

На острове Буяне жили N человек, каждый из которых был либо рыцарем либо лжецом, встали в круг. Рыцари говорят только правду, лжецы всегда только лгут. Каждому человеку в кругу задали вопрос: «Кто ты и кто твой сосед слева: рыцарь или лжец?» При этом каждый человек сказал, что он – рыцарь. А ответы всех людей о левом соседе были записаны в следующем формате: 1 – рыцарь 0 – лжец. Все ответы записаны в строку через пробел. Последний спрошенный человек отвечал на вопрос о первом.

Написать программу, которая по ответам жителей определяет, какое количество рыцарей заведомо присутствует в круге.

Входные данные

Первое число ( 1 < N ≤ 255 ) - количество жителей. Следующие N чисел (0 или 1), разделенных пробелами - ответы жителей.

———-
Уже четвертый день пытаюсь составить алгоритм. Может кто подскажет, как к таким задачам подходить нужно?

anton1k2 · Авг. 8, 2019 16:52:43

Я решил ее вот так, возможно есть другой способ, но этот проходит тестирование

 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)

strady · Апрель 17, 2020 00:29:40

У меня решение получилось короче.
Опытным путем получаем, что для каждого ряда чисел подходят 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))

Отредактировано strady (Апрель 17, 2020 00:36:08)

Vashom · Май 6, 2020 22:59:08

Господа -товарищи! Мне кажется, что задача эта не вполне корректна. Быть может я не прав, тогда поправьте меня. Речь о том, что не все входные значения допустимы. Например: жителей - 5, опрос (т.е. входные данные) - 00000. Тогда, следуя условиям задачи, получим, если первый - лжец, истинное распределение - 01010, а если первый -рыцарь, то - 10101. В обоих вариантах получаем противоречие, поскольку последний житель о первом жителе либо, являясь лжецом, сказал правду, либо, являясь рыцарем, соврал. Таких противоречий можно привести в качестве примера бесконечно много. Скажем, N = 4 при входных данных 1000 или N = 6 при 010000.
Приведённые вами алгоритмы - работают, но они не учитывают эти противоречия. Полагаю, что авторы этой задачи также не учли этот почти “расселовский” парадокс.
В общем, либо я, надеюсь, ошибаюсь, либо задачу следует переформулировать.

py.user.next · Май 7, 2020 01:19:36

Vashom
Речь о том, что не все входные значения допустимы. Например: жителей - 5, опрос (т.е. входные данные) - 00000.

Например, жителей двое.
00 - подходит для лжец и рыцарь (лжец говорит, что рыцарь - это лжец, а рыцарь говорит, что лжец - это лжец)
01 - не подходит вообще ни под что
10 - не подходит вообще ни под что
11 - подходит для рыцарь и рыцарь (рыцарь говорит, что рыцарь - это рыцарь, а рыцарь говорит, что рыцарь - это рыцарь)

Так что для двух жителей уже есть неподходящие последовательности. Соответственно, они же есть и для большего числа жителей. Вопрос в том, кто их будет подавать, эти неподходящие последовательности?

Koba_mk2 · Май 18, 2020 17:54:30

Решил задачу вот таким способом, но последний тест я проваливаю. Пару дней не могу понять, где я конкретно ошибся. Помогите понять, что я сделал не так.

 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 (Май 18, 2020 17:58:33)

AKHMEDT · Июнь 9, 2022 14:56:48

Koba_mk2
Решил задачу вот таким способом, но последний тест я проваливаю. Пару дней не могу понять, где я конкретно ошибся. Помогите понять, что я сделал не так.

Скорее всего ты исчерпал лимит по памяти (в данном задании есть такое ограничение), потому что дублируешь в память список A = answers.split(' '). При вводе/сборе данных используй:
answers = input().split() #список формируется без ограничений
либо:
answers = input().split() #список формируется из не более N элементов
Ну и далее в параметрах функций используй answers.

KEKIs · Июнь 19, 2022 20:39:34

Мне кажется, я придумал отличнейшее, элегантнейшее решение, но оно не проходит тест 8
Есть подозрение, что в нем некорректные входные данные. Как уже ранее писали тут, не каждая комбинация 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))

Python-сообщество

Уведомления

#1 Авг. 6, 2019 15:13:03

Задача про рыцарей и лжецов

#2 Авг. 8, 2019 16:52:43

Задача про рыцарей и лжецов

#3 Апрель 17, 2020 00:29:40

Задача про рыцарей и лжецов

#4 Май 6, 2020 22:59:08

Задача про рыцарей и лжецов

#5 Май 7, 2020 01:19:36

Задача про рыцарей и лжецов

#6 Май 18, 2020 17:54:30

Задача про рыцарей и лжецов

#7 Июнь 9, 2022 14:56:48

Задача про рыцарей и лжецов

#8 Июнь 19, 2022 20:39:34

Задача про рыцарей и лжецов

Board footer