قام شربات وجيلاتو بتشفير الرسالة
Problem
تعلم شربات وجيلاتو بيانات مهمة. هذه البيانات سر لا يمكن الكشف عنه ، لكن حجمها كان كبيرًا لدرجة أنه لم يكن من الممكن تذكرها تمامًا. لذلك قرروا تشفيرها.
قام شربات بتجميع رسالة من البيانات. بعد الرقمنة ، كانت الرسالة عبارة عن سلسلة M من n أعداد صحيحة غير سالبة. للتشفير ، أنشأ Sorbet مفتاحًا عشوائيًا K ، والذي كان أيضًا سلسلة من n أعداد صحيحة غير سالبة.
بعد ذلك ، قام بحساب الرسالة المشفرة A كـ XOR أحاديًا لكل عنصر مناظر للرسالة الأصلية والمفتاح (A
i = M
i & oplus؛ K
i ).
احتفظ شربات بالرسالة المشفرة لنفسه ، ولضمان الأمان ، تم إرسال المفتاح إلى جيلاتو وقام بمحوها. ومع ذلك ، تبين أن قناة الإرسال غير موثوقة وتلقى Gelato المفتاح P ، حيث تم تبديل بعض العناصر من K. وهذا يعني أنني حصلت على بعض التقليب للمفتاح الأصلي K.
عندما حان الوقت لفك تشفير الرسالة مرة أخرى ، أصيبوا بالرعب من إدراك المشكلة. ومع ذلك ، تذكر شربات أن الرسالة الأصلية كانت صغيرة جدًا من حيث المعجم (ولكنها تحتوي فقط على أرقام غير سالبة).
لذلك قرر شربات وجيلاتو اكتشاف أصغر رسالة يمكن تشفيرها من حيث المعجمية. ساعدهم في اكتشاف ذلك.
الإدخال:
يحتوي السطر الأول على عدد صحيح واحد n (1 & thinsp؛ & le؛ & thinsp؛ n & thinsp؛ & le؛ & thinsp؛ 300000) & mdash؛ طول الرسالة.
السطر الثاني يحتوي على n أعداد صحيحة A 1 ، & thinsp؛ A 2 ، & thinsp؛ ...، & thinsp؛ A n (0 & thinsp؛ & le؛ & thinsp؛ Ai & thinsp؛ & lt؛ & thinsp؛ 2 30 ) & mdash؛ رسالة مشفرة.
السطر الثالث يحتوي على n أعداد صحيحة P 1 ، & thinsp؛ P 2 ، & thinsp؛ ...، & thinsp؛ P n (0 & thinsp؛ & le؛ & thinsp؛ Pi & thinsp؛ & lt؛ & thinsp؛ 2 30 ) & mdash؛ مفتاح تشفير يتم إعادة ترتيب عناصره بشكل عشوائي.
الإخراج:
طباعة سطر واحد بأعداد صحيحة n & [مدش] ؛ أصغر رسالة أصلية ممكنة من الناحية المعجمية. تذكر أن جميع الأرقام الموجودة فيه يجب أن تكون غير سالبة.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
3
8 4 13
17 2 7
| 10 3 28 |
5
12 7 87 22 11
18 39 9 12 16
| 0 14 69 6 44 |
الشرح:
في المثال الأول ، الحل هو (10، & thinsp؛ 3، & thinsp؛ 28) لأن 8 & oplus؛ 2 = 10، 4 & oplus؛ 7 = 3 و 13 & oplus ؛ 17 = 28. نبسب ؛
تعطي تباينات المفاتيح الأخرى الممكنة الرسائل (25، & thinsp؛ 6، & thinsp؛ 10)، (25، & thinsp؛ 3، & thinsp؛ 15)، (10، & thinsp؛ 21، & thinsp؛ 10)، (15، & thinsp؛ 21، & thinsp ؛ ؛ 15) و (15 ، & thinsp ؛ 6 ، & thinsp ؛ 28) ، وكلها أكبر من الناحية المعجمية من الحل الأمثل.