إذا كنت تتابع الأخبار على شبكات التواصل الاجتماعي، فلا بد أنك سمعت عدة نظريات مؤامرة مختلفة عن منظمات سرية تخطط لزرع شرائح في البشر باستخدام اللقاحات، وتسميم سوائل الجسم بالفلور، وما شابه ذلك. وقد أمّنت إحدى هذه المنظمات مؤخرًا للشاب Martin وظيفة مدير صحيفة كرواتية معروفة.
لم تهتم المنظمة بالصحيفة بلا سبب. فهي تحتاج إلى طريقة لإرسال الرسائل ببطء وبشكل غير فعّال إلى جميع أعضائها، مع إثارة أكبر عدد ممكن من نظريات المؤامرة. وبسبب بعض الخصائص العددية الغامضة، أمرت المنظمة Martin باستخدام وسيط غير معتاد لإرسال الرسائل. فبدلًا من إخفاء الرسائل في نصوص المقالات، عليه إخفاؤها في قسم الألغاز في الصحيفة، وتحديدًا في ألغاز سودوكو.
لغز سودوكو هو مصفوفة من $9\times 9$ خانات، تُكتب في بعضها أعداد من واحد إلى تسعة. ينقسم اللغز إلى $9$ صفوف و$9$ أعمدة و$9$ مربعات بحجم $3\times 3$. يُعد اللغز محلولًا عندما تُملأ جميع الخانات بأعداد من واحد إلى تسعة، بحيث لا يتكرر أي عدد في أي صف أو عمود أو مربع.
مهمة Martin هي كتابة برنامج يرمّز سلسلة من $N$ كلمات $s_i$ إلى $N$ ألغاز سودوكو، ثم يفك ترميز هذه الألغاز لإعادتها إلى الكلمات.
لن يسمح محررو الألغاز في الصحيفة لـ Martin بوضع أي لغز سودوكو كيفما اتفق، بل سيصنعون اللغز بحذف عدد من الأعداد من اللغز المحلول الذي يقترحه Martin، بحسب مستوى الصعوبة المطلوب. لذلك يجب أن يرمّز برنامج Martin الكلمات إلى ألغاز سودوكو محلولة.
يعتقد رؤساء Martin أن كل عضو في المنظمة ينبغي أن يستطيع حل هذا اللغز، ولذلك لا يحتاج جزء فك الترميز من البرنامج إلا إلى فك ترميز الألغاز المكتملة.
ليست البرمجة من نقاط قوة Martin، لذا يطلب منك كتابة هذا البرنامج.
الإدخال
يحتوي السطر الأول على عددين صحيحين موجبين $M$ و$N$ ($M=1$ أو $M=2$، و$1\le N\le 30$). إذا كان $M=1$، فعلى البرنامج ترميز $N$ سلاسل نصية إلى ألغاز سودوكو؛ وإذا كان $M=2$، فعليه فك ترميز $N$ ألغاز سودوكو وإعادتها إلى سلاسل نصية.
إذا كان $M=1$، فإن السطر رقم $i$ من الأسطر الـ $N$ التالية يحتوي على عدد صحيح موجب $l_i$ وسلسلة نصية $s_i$ ($1\le |s_i|=l_i\le 15$). تتكون السلاسل $s_i$ حصريًا من الحروف الإنجليزية الصغيرة.
إذا كان $M=2$، فإن الأسطر الـ $9N$ التالية تحتوي على $N$ مصفوفات بحجم $9\times 9$، تمثل ألغاز سودوكو المطلوب فك ترميزها. ستكون المصفوفات دائمًا ألغازًا صحيحة، أي إنها تتكون من المحارف 1 إلى 9، ولا يتكرر أي عدد في أي مربع بحجم $3\times 3$ أو صف أو عمود من المصفوفة.
الإخراج
إذا كان $M=1$، فاطبع في $9N$ سطرًا $N$ ألغاز سودوكو تمثل القيم المرمّزة للسلاسل $s_i$ في الإدخال. يجب أن تتكون الألغاز المطبوعة حصريًا من المحارف 1 إلى 9، وألا تتكرر الأعداد في الصفوف أو الأعمدة أو المربعات بحجم $3\times 3$.
إذا كان $M=2$، فاطبع في $N$ سطرًا السلاسل النصية الناتجة عن فك ترميز ألغاز سودوكو في الإدخال.
المهام الفرعية
سيُختبر حلك على مرحلتين. أولًا، سيُشغّل باستخدام بيانات الإدخال الرسمية التي يكون فيها $M=1$. إذا كان خرج حلك سلسلة من $N$ مصفوفات صحيحة، فسيُشغّل حلك مرة أخرى في المرحلة الثانية باستخدام المصفوفات المطبوعة في المرحلة الأولى. إذا كانت السلاسل التي يطبعها برنامجك في المرحلة الثانية مطابقة للسلاسل في بيانات الإدخال الرسمية، فستحصل على جميع النقاط الخاصة بهذا الإدخال الرسمي.
زمن تنفيذ حلك هو مجموع زمنَي تنفيذ مرحلتَي التقييم.
| المهمة الفرعية | النقاط | القيود |
|---|---|---|
| 1 | 10 | $1\le l_i\le 3$ |
| 2 | 10 | $1\le l_i\le 7$ |
| 3 | 4 | $1\le l_i\le 11$، والسلاسل في الإدخال مولّدة عشوائيًا. |
| 4 | 6 | $1\le l_i\le 11$ |
| 5 | 4 | $1\le l_i\le 12$، والسلاسل في الإدخال مولّدة عشوائيًا. |
| 6 | 6 | $1\le l_i\le 12$ |
| 7 | 7 | $1\le l_i\le 13$، والسلاسل في الإدخال مولّدة عشوائيًا. |
| 8 | 8 | $1\le l_i\le 13$ |
| 9 | 9 | $1\le l_i\le 14$، والسلاسل في الإدخال مولّدة عشوائيًا. |
| 10 | 11 | $1\le l_i\le 14$ |
| 11 | 12 | $1\le l_i\le 15$، والسلاسل في الإدخال مولّدة عشوائيًا. |
| 12 | 13 | $1\le l_i\le 15$ |
أمثلة
الإدخال 1
1 1 6 sudoku
الإخراج 1
139245678 628137459 457689123 214356897 375498216 896712345 541873962 763921584 982564731
الإدخال 2
2 1 139245678 628137459 457689123 214356897 375498216 896712345 541873962 763921584 982564731
الإخراج 2
sudoku