Билетики

@lookatthis · Регистрация: 14.07.2018

Студворк — интернет-сервис помощи студентам

Задача только на 50% проходит надо бы полное решение кто может помочь
chapterid=993#1https://informatics.msk.ru/mod... erid=993#1

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

Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N>=K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки — считается, что одно из чисел может исказиться (то есть 0 заменится на 1, или 1 — на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным.

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

Входные данные
В первой строке входного файла записаны числа N и K (1<=N<=50000, 1<=K<=1000, K<=N). Во второй строке записано N чисел, каждое из которых является 0 или 1 — информация, считанная с билета.

Выходные данные
В первой строке выходного файла должно быть записано одно из двух сообщений — OK или FAIL (первое сообщение обозначает, что билет признан подлинным, второе — поддельным). В случае, если билет подлинный, во второй строке выведите 0, если все числа были считаны правильно, или номер числа, в котором при считывании произошла ошибка. Если возможных ответов несколько, выведите любой из них (в частности, если для признания билета подлинным можно считать, что ошибок при считывании не было, а можно считать, что была ошибка в одном из чисел — правильным является любой из вариантов ответа).

Примеры
входные данные
6 2
1 0 1 0 1 0
выходные данные
OK
0
входные данные
6 2
1 1 1 0 1 0
выходные данные
OK
2
входные данные
6 2
1 1 1 0 0 0
выходные данные
FAIL

Рыжий Лис · 26.12.2018, 07:32

И?.. Где ваш код, который

Сообщение от lookatthis

только на 50% проходит

@lookatthis · 26.12.2018, 12:07 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n,k = map(int,input().split())
count,last = 0,-1
arr=list(map(int,input().split()))
for i in range(k,n):
    if(i>=k and arr[i-k]!=arr[i]):
        count+=1
        last=i+1
if(count>1):
    print("FAIL")
else:
    print("OK")
    if(last==-1):
        print(0)
    else:
        print(last)

Добавлено через 19 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n,k = map(int,input().split())
count,last = 0,-1
arr=list(map(int,input().split()))
for i in range(k,n):
    if(i>=k and arr[i-k]!=arr[i]):
        count+=1
        last=i+1
if(count>1):
    print("FAIL")
else:
    print("OK")
    if(last==-1):
        print(0)
    else:
        print(last)

DmitryV555 · 03.07.2019, 16:19

Добрый день! Можете, пожалуйста, объяснить построчно выше приведенный код? или просто описать подход решения данной задачи? Для чего нужна переменная last и почему она равна -1?

@Black Fregat · 03.07.2019, 16:49

Забавная ошибка. Даже не сразу сообразил..
Проблема этого кода в том, при одной реальной ошибке в числе i может быть зафиксировано сразу два несравнения:
(i-k, i) и (i, i+k)

Добавлено через 2 минуты

Сообщение от DmitryV555

Для чего нужна переменная last

Последнее найденное несовпадение

Сообщение от DmitryV555

почему она равна -1

Чтобы отличить случай, когда несовпадений не было

DmitryV555 · 03.07.2019, 17:12

Black Fregat, а count это количество ошибок? и оно наращивается если

Python
1
if(i>=k and arr[i-k]!=arr[i]):

выполняется это? только я несовсем понимаю это условие, можете разъяснить? и параметр k - расстояние (i - j)? ну т.е. допустим есть последовательность 1 0 1 0, 1 - это i, j - 0, а k - это расстояние между ними?
и спасибо большое за предыдущий ответ!!

@Black Fregat · 03.07.2019, 17:18

Сообщение от DmitryV555

это условие

Это в чистом виде условие задачи - проверяем несовпадение числа с предшествующим ему на k мест

DmitryV555 · 03.07.2019, 19:41

Black Fregat, извиняюсь за такие вопросы

а почему в цикле for (k, n), а не (n, k)? это имеет значение?

Добавлено через 2 часа 3 минуты
а все, разобрался с этим вопросом)

Добавлено через 9 минут

Сообщение от Black Fregat

Забавная ошибка. Даже не сразу сообразил..
Проблема этого кода в том, при одной реальной ошибке в числе i может быть зафиксировано сразу два несравнения:
(i-k, i) и (i, i+k)

да, проверил это на примере:
6 2
1 1 1 0 1 0 выводит:
ОК
4
а должен выводить вместо 4 - 2, т.к. ошибка на 2 месте, можно исправить это так:

Сообщение от lookatthis

last=i-1

но по смыслу это неверно, подскажите как лучше сделать, пожалуйста

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@lookatthis 0 / 0 / 0 Регистрация: 14.07.2018 Сообщений: 23

	Билетики 26.12.2018, 06:59. Показов 2894. Ответов 7 Метки олимпиада (Все метки) Задача только на 50% проходит надо бы полное решение кто может помочь chapterid=993#1https://informatics.msk.ru/mod... erid=993#1 В процессе установки турникетов в автобусах, разработчики столкнулись с проблемой проверки подлинности билета. Для ее решения был придуман следующий способ защиты от подделок. Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N>=K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки — считается, что одно из чисел может исказиться (то есть 0 заменится на 1, или 1 — на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным. Напишите программу, которая по информации, считанной с билета, устанавливает его подлинность, и указывает, при считывании какого из чисел могла произойти ошибка. Входные данные В первой строке входного файла записаны числа N и K (1<=N<=50000, 1<=K<=1000, K<=N). Во второй строке записано N чисел, каждое из которых является 0 или 1 — информация, считанная с билета. Выходные данные В первой строке выходного файла должно быть записано одно из двух сообщений — OK или FAIL (первое сообщение обозначает, что билет признан подлинным, второе — поддельным). В случае, если билет подлинный, во второй строке выведите 0, если все числа были считаны правильно, или номер числа, в котором при считывании произошла ошибка. Если возможных ответов несколько, выведите любой из них (в частности, если для признания билета подлинным можно считать, что ошибок при считывании не было, а можно считать, что была ошибка в одном из чисел — правильным является любой из вариантов ответа). Примеры входные данные 6 2 1 0 1 0 1 0 выходные данные OK 0 входные данные 6 2 1 1 1 0 1 0 выходные данные OK 2 входные данные 6 2 1 1 1 0 0 0 выходные данные FAIL 0

DmitryV555 2 / 2 / 0 Регистрация: 14.02.2017 Сообщений: 220
	03.07.2019, 16:19
	Добрый день! Можете, пожалуйста, объяснить построчно выше приведенный код? или просто описать подход решения данной задачи? Для чего нужна переменная last и почему она равна -1? 0