Задача №114934. Проверка на списывание
Вы создали очередную платформу для проведения онлайн соревнований по программированию. После первого контеста вы изучили решения участников и заметили, что некоторые списывают друг у друга. После этого вам захотелось написать программу, чтобы быстрее обнаруживать списывания и блокировать нечестных участников.
Пусть есть две строки, описывающие решения. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После этого для рассматриваемого символа \(x\) определим другой символ \(p(x) \neq x\) и заменим некоторые вхождения \(x\) в первое решение на \(p(x)\). Если в ходе такого процесса из первого решения возможно получить второе, то скажем, что второе решение списано с первого.
Иными словами, участник копирует чужое решение и, чтобы списывание не было таким очевидным, один раз рассматривает некоторые различные символы \(x\), которые хотя бы раз встречаются в первом решении. Для каждого такого символа \(x\) он выбирает, на какой другой символ \(p(x)\) он будет заменять его вхождения, после чего проходит по строке и заменяет в ней \(x\) на \(p(x)\), но на некоторых позициях забывает это сделать (или там замена невозможна).
Значения \(p(x)\) участником выбираются независимо для разных \(x\), поэтому они могут и совпасть.
Напишите программу, которая позволит обнаружить списывания такого рода.
Кроме платформы вы создали язык программирования S++ и, чтобы его популяризировать, вы решили разрешить сдавать задачи в своей системе только на нем. Одной из особенностью языка является то, что любая программа записывается в одну строку и может состоять только из строчных и заглавных букв английского алфавита (a-z, A-Z), цифр (0-9), скобок ('(', ')', '{', '}' '[', ']'), знаков сравнения ('<', '>', '=') и символов '+', '-', '*', '/', ';'.
В первой строке вам дано число \(n\) \((1 \leqslant n \leqslant 200\,000)\), равное длине каждой из программ.
Во второй строке вам дана программа первого участника на языке S++.
В третьей строке вам дана программа второго участника на языке S++.
Если вторая программа списана с первой, выведите «YES» (без кавычек), на следующей строке выведите \(m\) – количество различных символов в первой программе, которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots, \ c_m\). После этого выведите \(m\) строк. На \(i\)-й строке необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если вторая программа не списана с первой, то выведите «NO» (без кавычек).
В первом примере списывающий заменил все вхождения 'i' на 'j' и вхождения 'n' на 'm'.
Во втором примере участник заменял 'a' на 'e', 'b' на 'f', 'с' на g' и '-' на '+'.
В третьем примере невозможно осуществить процесс замен так, чтобы из первой строки получилась вторая.
В четвертом примере участник списал, заменив некоторые вхождения 'a' на 'b'.
В пятом примере участник списал, заменив некоторые вхождения 'a' на 'b' и все вхождения 'c' на 'a'.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие, когда обе программы состоят только из символов 'a' и 'b', наберут не менее 20 баллов.
Решения, корректно работающие, когда обе программы состоят только из символов 'a', 'b', 'c', наберут не менее 40 баллов.
Решения, корректно работающие при \(n \leqslant 1\,000\) наберут не менее 60 баллов.
Решения, корректно работающие только для случая, когда обнаружить списывание не удалось, оцениваются в 0 баллов.
16 for(i=0;i
YES 2 i j n m
14 a=1;b=-1;c=a-b e=1;f=+1;g=e+f
YES 4 - + a e b f c g
5 a=a+a a=c+d
NO
4 aaab abbb
YES 1 a b
6 aaabcc abbbaa
YES 2 a b c a
3 abc aaa
YES 2 b a c a