Problem
Şerbet ve Gelato önemli verileri öğrendi. Bu veriler ifşa edilemeyecek bir sırdır, ancak hacimleri o kadar büyüktü ki, onları tam olarak hatırlamak mümkün değildi. Bu yüzden onları şifrelemeye karar verdiler.
Sorbet verilerden bir mesaj derledi. Sayısallaştırmadan sonra mesaj, negatif olmayan n tam sayıdan oluşan bir M dizisiydi. Sorbet, şifreleme için, aynı zamanda negatif olmayan n tam sayıdan oluşan bir dizi olan rastgele bir K anahtarı oluşturdu.
Bundan sonra, şifreli mesaj A'yı, orijinal mesajın karşılık gelen her öğesinin ve anahtarın (A
i = M
i ⊕ K
) bitsel XOR'u olarak hesapladı. i) .
Sorbet şifreli mesajı kendine sakladı ve güvenliği sağlamak için anahtarı Gelato'ya gönderdi ve o da onu sildi. Bununla birlikte, iletim kanalının güvenilmez olduğu ortaya çıktı ve Gelato, K'den bazı öğelerin değiştirildiği P anahtarını aldı. Yani, orijinal K anahtarının bazı permütasyonlarına sahibim.
Mesajın kodunu çözme zamanı geldiğinde, sorunu fark ettikleri için dehşete kapıldılar. Ancak Sorbet, orijinal mesajın sözlük açısından oldukça küçük olduğunu (ancak yalnızca negatif olmayan sayılar içerdiğini) hatırladı.
Böylece Sorbet ve Gelato sözlüksel olarak şifrelenebilecek en küçük mesajın ne olduğunu bulmaya karar verdiler. Anlamalarına yardımcı olun.
Giriş:
İlk satır tek bir tamsayı içerir n (1 ≤ n ≤ 300000) — mesaj uzunluğu.
İkinci satır n tam sayı A
1, A
2, ..., A
n (0 ≤ Ai < 2
30) — şifreli mesaj.
Üçüncü satır n tamsayı içerir P
1, P
2, ..., P
n (0 ≤ Pi < 2
30) — öğeleri keyfi olarak yeniden düzenlenen bir şifreleme anahtarı.
Çıktı:
n tam sayı içeren bir satır yazdır — sözlüksel olarak mümkün olan en küçük orijinal mesaj. İçindeki tüm sayıların negatif olmaması gerektiğini hatırlayın.
Örnekler:
| Giriş |
Çıktı |
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 |
Açıklama:
İlk örnekte, çözüm (10, 3, 28) çünkü 8 ⊕ 2 = 10, 4 + artı; 7 = 3 ve 13 + 17 = 28.
Diğer olası tuş permütasyonları (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21,) mesajlarını verir. ;15) ve (15, 6, 28), bunların tümü sözlüksel olarak en uygun çözümden daha büyüktür.