+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- کریم یک کودک ۵ ساله است و در گردهمایی مهدکودکی‌ها شرکت می‌کند. کریم و $n - 1$ نفر از هم مهدی‌هایش دور یک میز دایره‌ای شکل جهت صرف دوغ گرد هم آمده‌اند. آن‌ها را با شروع از کریم و بصورت ساعتگرد، با اعداد 1 تا $n$ شماره‌گذاری می‌کنیم. بین برخی از این کودکان رابطه‌ی دوطرفه‌ی دوستی برقرار است. پس از انتظارهای بسیار، یک عدد پارچ دوغ به کنار میز آورده می‌شود. همه‌ی این $n$ نفر می‌خواهند از این دوغ بنوشند. روند دوغ‌رسانی در این قبیل گردهمایی‌ها به این صورت است که پارچ دوغ ابتدا به یکی از افراد دور میز داده می‌شود. هرکسی که پارچ به دستش میرسد پس از نوشیدن مقداری از آن، پارچ دوغ را به یکی از دوستانش که هنوز دوغ نخورده است می‌دهد تا وقتی که همه از آن بنوشند. دقت کنید که بخاطر سن کم، هیچ کس پارچ دوغ را به کسی که با او دوست نیست نمی‌دهد. به دلیل بزرگ بودن میز و کوچک بودن کودکان، هرکس برای رساندن دوغ به نفر بعدی به روی میز میرود و هنگام راه رفتن روی مسیر بین جایگاه نشستن خود و نفر بعدی، خطی از دوغ روی میز باقی می‌گذارد. روی هیچ نقطه‌ای از مسیری که یک کودک به سمت کودک بعدی طی می‌کند نباید از قبل دوغی ریخته شده باشد؛ چون کودک هنگام حمل دوغ لیز خورده و خاطره‌ی بدی از گردهمایی بجا خواهد ماند. حال با دانستن روابط دوستی بین این کودکان، بگویید که این ها به چه ترتیبی می‌توانند دوغ بخورند که به همه دوغ برسد و هیچکس هنگام حمل دوغ زمین نخورد. (یا بگویید که امکان ندارد.) # ورودی خط اول ورودی شامل عدد $n$ است. در خط دوم ورودی عدد $m$ که بیانگر تعداد رابطه های دوستی بین کودکان است. هریک از $m$ خط بعدی یک جفت عدد $u, v$ آمده که یعنی کودک شماره $u$ و کودک شماره $v$ با هم دوست هستند. $$3 \le n \le 1000$$ $$0 \le m \le \frac{n \times (n-1)}2$$ # خروجی اگر امکان ندارد که به همه با شرایط گفته شده دوغ برسد، تنها خط خروجی باید شامل عدد $-1$ باشد. در غیر این صورت خروجی برنامه باید ترتیبی صحیح از دوغ خوردن افراد باشد که در $n$ خط آمده است. در صورت وجود چند ترتیب درست، یکی را به دلخواه خروجی دهید. # ورودی نمونه ۱ ``` 7 9 1 4 5 1 1 7 5 6 2 3 3 4 2 6 4 6 6 7 ``` # خروجی نمونه ۱ ``` 2 3 4 1 7 6 5 ``` # ورودی نمونه ۲ ``` 4 3 1 2 2 4 1 3 ``` # خروجی نمونه ۲ ``` -1 ```

گردهمایی

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۶۴ مگابایت

کریم یک کودک ۵ ساله است و در گردهمایی مهدکودکی‌ها شرکت می‌کند.

کریم و $n - 1$ نفر از هم مهدی‌هایش دور یک میز دایره‌ای شکل جهت صرف دوغ گرد هم آمده‌اند. آن‌ها را با شروع از کریم و بصورت ساعتگرد، با اعداد 1 تا $n$ شماره‌گذاری می‌کنیم. بین برخی از این کودکان رابطه‌ی دوطرفه‌ی دوستی برقرار است.

پس از انتظارهای بسیار، یک عدد پارچ دوغ به کنار میز آورده می‌شود. همه‌ی این $n$ نفر می‌خواهند از این دوغ بنوشند. روند دوغ‌رسانی در این قبیل گردهمایی‌ها به این صورت است که پارچ دوغ ابتدا به یکی از افراد دور میز داده می‌شود. هرکسی که پارچ به دستش میرسد پس از نوشیدن مقداری از آن، پارچ دوغ را به یکی از دوستانش که هنوز دوغ نخورده است می‌دهد تا وقتی که همه از آن بنوشند. دقت کنید که بخاطر سن کم، هیچ کس پارچ دوغ را به کسی که با او دوست نیست نمی‌دهد.

به دلیل بزرگ بودن میز و کوچک بودن کودکان، هرکس برای رساندن دوغ به نفر بعدی به روی میز میرود و هنگام راه رفتن روی مسیر بین جایگاه نشستن خود و نفر بعدی، خطی از دوغ روی میز باقی می‌گذارد. روی هیچ نقطه‌ای از مسیری که یک کودک به سمت کودک بعدی طی می‌کند نباید از قبل دوغی ریخته شده باشد؛ چون کودک هنگام حمل دوغ لیز خورده و خاطره‌ی بدی از گردهمایی بجا خواهد ماند.

حال با دانستن روابط دوستی بین این کودکان، بگویید که این ها به چه ترتیبی می‌توانند دوغ بخورند که به همه دوغ برسد و هیچکس هنگام حمل دوغ زمین نخورد. (یا بگویید که امکان ندارد.)

ورودی🔗

خط اول ورودی شامل عدد $n$ است.

در خط دوم ورودی عدد $m$ که بیانگر تعداد رابطه های دوستی بین کودکان است. هریک از $m$ خط بعدی یک جفت عدد $u, v$ آمده که یعنی کودک شماره $u$ و کودک شماره $v$ با هم دوست هستند.

$3 \le n \le 1000$

$0 \le m \le \frac{n \times (n-1)}2$

خروجی🔗

اگر امکان ندارد که به همه با شرایط گفته شده دوغ برسد، تنها خط خروجی باید شامل عدد $-1$ باشد. در غیر این صورت خروجی برنامه باید ترتیبی صحیح از دوغ خوردن افراد باشد که در $n$ خط آمده است.

در صورت وجود چند ترتیب درست، یکی را به دلخواه خروجی دهید.

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

-1

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کیانوش متقاضی عضویت در سازمان OC است. در روز سوم مصاحبه، سازمان ادبیات او را مورد بررسی قرار داده است. در این مصاحبه، پنچ نفر روبروی کیانوش مینشینند. آن‌ها شعری انتخاب کرده‌اند. هریک از آن‌ها یکبار ابیات آن شعر را به هم میریزد و با ترتیبی تصادفی به کیانوش میگوید؛ به این صورت که ابتدا شعر انتخاب شده‌ی اولیه را درنظر گرفته و سپس تعدادی از ابیات آنرا انتخاب کرده، از شعر حذف میکند و در جای دیگری به شعر اضافه میکند. کیانوش باید ترتیب ابیات در شعر اصلی را بیابد. میدانیم که هر بیت در حداکثر یکی از این ۵ شعر حذف و جابجا شده است. هنگام به‌هم ریختن ابیات، بیت‌ها پس از حذف شدن به ترتیب دلخواه و در جایگاه دلخواه اضافه میشوند. ممکن است جایگاه ابیات حذف نشده نیز در این حرکت تغییر کند. با ورودی گرفتن ابیات خوانده شده بگویید که ترتیب اولیه چه بوده است. تضمین میشود که در ورودی‌های داده‌شده ترتیب اولیه بصورت یکتا مشخص میشود. # ورودی سطر اول ورودی تنها شامل عدد $n$ است که نمایانگر تعداد ابیات داخل شعر خوانده شده است. سپس در $5n$ سطر بعدی، پنج بار و هر بار در $n$ سطر و در هر سطر یک بیت از شعر آمده است. ابیات را با اعداد صحیح متمایز بین ۰ و $10^9$ مشخص میکنیم. $$1 \le n \le 20000$$ # خروجی خروجی برنامه باید شامل $n$ سطر باشد که هر سطر شامل یک بیت از شعر بشود. ترتیب ابیات باید برابر ترتیب انتخاب شده‌ی اولیه باشد. # ورودی نمونه ``` 5 1 2 3 4 5 2 1 3 4 5 3 1 2 4 5 4 1 2 3 5 5 1 2 3 4 ``` # خروجی نمونه ``` 1 2 3 4 5 ``` در این مثال هر فرد قبل از خواندن شعر یک بیت را از آن حذف کرده و به ابتدای شعر منتقل میکند و سپس آن را میخواند؛ پس هر بیت در حداکثر یک شعر جابجا شده است.

ترتیب ابیات

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

کیانوش متقاضی عضویت در سازمان OC است. در روز سوم مصاحبه، سازمان ادبیات او را مورد بررسی قرار داده است.

در این مصاحبه، پنچ نفر روبروی کیانوش مینشینند. آن‌ها شعری انتخاب کرده‌اند. هریک از آن‌ها یکبار ابیات آن شعر را به هم میریزد و با ترتیبی تصادفی به کیانوش میگوید؛ به این صورت که ابتدا شعر انتخاب شده‌ی اولیه را درنظر گرفته و سپس تعدادی از ابیات آنرا انتخاب کرده، از شعر حذف میکند و در جای دیگری به شعر اضافه میکند. کیانوش باید ترتیب ابیات در شعر اصلی را بیابد. میدانیم که هر بیت در حداکثر یکی از این ۵ شعر حذف و جابجا شده است.

هنگام به‌هم ریختن ابیات، بیت‌ها پس از حذف شدن به ترتیب دلخواه و در جایگاه دلخواه اضافه میشوند. ممکن است جایگاه ابیات حذف نشده نیز در این حرکت تغییر کند.

با ورودی گرفتن ابیات خوانده شده بگویید که ترتیب اولیه چه بوده است. تضمین میشود که در ورودی‌های داده‌شده ترتیب اولیه بصورت یکتا مشخص میشود.

ورودی🔗

سطر اول ورودی تنها شامل عدد $n$ است که نمایانگر تعداد ابیات داخل شعر خوانده شده است.

سپس در $5n$ سطر بعدی، پنج بار و هر بار در $n$ سطر و در هر سطر یک بیت از شعر آمده است. ابیات را با اعداد صحیح متمایز بین ۰ و $10^9$ مشخص میکنیم.

$1 \le n \le 20000$

خروجی🔗

خروجی برنامه باید شامل $n$ سطر باشد که هر سطر شامل یک بیت از شعر بشود. ترتیب ابیات باید برابر ترتیب انتخاب شده‌ی اولیه باشد.

ورودی نمونه🔗

خروجی نمونه🔗

در این مثال هر فرد قبل از خواندن شعر یک بیت را از آن حذف کرده و به ابتدای شعر منتقل میکند و سپس آن را میخواند؛ پس هر بیت در حداکثر یک شعر جابجا شده است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول پرست است، جهت صرفه‌جویی در تعداد حروف پیامک‌هایش به فشرده‌سازی رشته‌ها روی آورده. روش عمو برای فشرده‌سازی به این صورت است: که او در ابتدا جایگشتی از اعداد ۱, ۲, ..., $k$ انتخاب میکند. سپس رشته‌ی خود را به دسته های پشت سر هم $k$ حرفی تقسیم میکند (طول رشته باید به $k$ بخش‌پذیر باشد) و روی هر دسته از حروف، جایگشت خود را اعمال میکند. سپس رشته‌ی بدست آمده را بوسیله‌ی روش RLE که در ادامه توضیح داده خواهد شد، فشرده میکند. اعمال جایگشت $p$ روی یک دسته از $k$ حرف یعنی حرف $p_1$م را در جایگاه اول قرار داده، حرف $p_2$م را در جایگاه دوم و... برای مثال اعمال جایگشت {۲ ,۴ ,۱ ,۳} روی رشته‌ی $abcd$ آن را تبدیل به $cadb$ میکند. اعمال این جایگشت با دسته دسته کردن روی رشته‌ی $abcdefgh$، رشته‌ی $cadbgehf$ را نتیجه میدهد. رشته‌ی جایگشت داده شده توسط RLE (یا run-length encoding) فشرده میشود. جهت جلوگیری از محاسبات پیچیده، طول رشته‌ی فشرده‌شده را برابر تعداد گروه حرف‌های برابر پشت سر هم درنظر میگیریم. برای مثال طول رشته‌ی $aabcaa$ پس از فشرده‌شدن توسط RLE را ۴ در نظر میگیریم. (یک گروه ۲ حرفی a، یک گروه تک حرفی b، یک گروه تک حرفی c و یک گروه ۲ حرفی a) عمو میخواهد پیامکی را با روش گفته شده فشرده کرده و بفرستد. واضح است که طول رشته‌ی نهایی به جایگشت انتخاب‌شده مربوط است. شما با داشتن متن پیامک عمو، جایگشتی انتخاب کنید که پس از فشرده‌سازی بوسیله‌ی آن طول پیامک کمینه شود و این طول کمینه را خروجی دهید. # ورودی سطر اول تنها شامل عدد $k$ است. در سطر بعدی پیامک عمو بصورت یک رشته از حروف کوچک انگلیسی به طول حداکثر ۵۰۰۰۰ آمده است. $$2 \le k \le 16$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین طول ممکن برای پیامک عمو است. # ورودی نمونه ``` 4 abcabcabcabc ``` # خروجی نمونه ``` 7 ``` در این مثال با انتخاب جایگشت {۲ ,۳ ,۴ ,۱} نتیجه‌ی بهینه بدست می‌آید.

فشرده‌سازی

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

عمو که فردی بسیار پول پرست است، جهت صرفه‌جویی در تعداد حروف پیامک‌هایش به فشرده‌سازی رشته‌ها روی آورده.

روش عمو برای فشرده‌سازی به این صورت است:

که او در ابتدا جایگشتی از اعداد ۱, ۲, ..., $k$ انتخاب میکند. سپس رشته‌ی خود را به دسته های پشت سر هم $k$ حرفی تقسیم میکند (طول رشته باید به $k$ بخش‌پذیر باشد) و روی هر دسته از حروف، جایگشت خود را اعمال میکند. سپس رشته‌ی بدست آمده را بوسیله‌ی روش RLE که در ادامه توضیح داده خواهد شد، فشرده میکند.

اعمال جایگشت $p$ روی یک دسته از $k$ حرف یعنی حرف $p_1$ م را در جایگاه اول قرار داده، حرف $p_2$ م را در جایگاه دوم و... برای مثال اعمال جایگشت {۲ ,۴ ,۱ ,۳} روی رشته‌ی $abcd$ آن را تبدیل به $cadb$ میکند. اعمال این جایگشت با دسته دسته کردن روی رشته‌ی $abcdefgh$ ، رشته‌ی $cadbgehf$ را نتیجه میدهد.

رشته‌ی جایگشت داده شده توسط RLE (یا run-length encoding) فشرده میشود. جهت جلوگیری از محاسبات پیچیده، طول رشته‌ی فشرده‌شده را برابر تعداد گروه حرف‌های برابر پشت سر هم درنظر میگیریم. برای مثال طول رشته‌ی $aabcaa$ پس از فشرده‌شدن توسط RLE را ۴ در نظر میگیریم. (یک گروه ۲ حرفی a، یک گروه تک حرفی b، یک گروه تک حرفی c و یک گروه ۲ حرفی a)

عمو میخواهد پیامکی را با روش گفته شده فشرده کرده و بفرستد. واضح است که طول رشته‌ی نهایی به جایگشت انتخاب‌شده مربوط است. شما با داشتن متن پیامک عمو، جایگشتی انتخاب کنید که پس از فشرده‌سازی بوسیله‌ی آن طول پیامک کمینه شود و این طول کمینه را خروجی دهید.

ورودی🔗

سطر اول تنها شامل عدد $k$ است.

در سطر بعدی پیامک عمو بصورت یک رشته از حروف کوچک انگلیسی به طول حداکثر ۵۰۰۰۰ آمده است.

$2 \le k \le 16$

خروجی🔗

در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین طول ممکن برای پیامک عمو است.

ورودی نمونه🔗

4
abcabcabcabc

خروجی نمونه🔗

در این مثال با انتخاب جایگشت {۲ ,۳ ,۴ ,۱} نتیجه‌ی بهینه بدست می‌آید.

انجام دادن تکالیف معمولاً موجب می‌شود دانش‌آموزان درک عمیق‌تری نسبت به درس داشته باشند. هری پاتر به عنوان یکی از دانش‌آموزان هاگوارتز، خیلی وقت‌ها تکالیف زیادی را باید انجام دهد. او هر روز، به عنوان تکلیف، یک مجموعه مسئله از استادانش می‌گیرد. مسئله‌ی $i$ به اندازه‌ی $t_i$ زمان لازم دارد تا کامل انجام شود. با فرض داشتن یک برنامه (یا به عبارت دیگر یک ترتیب از مسئله‌ها)، هر مسئله‌ی $i$ یک «زمان پایان»ای دارد که آن را با $C_i$ نمایش می‌دهیم. برای مثال اگر مسئله‌ی $j$ اولین مسئله‌ای باشد که حل می‌شود آنگاه زمان پایان آن برابر $C_j=t_j$ است. هر مسئله‌ی $i$ همچنین یک «وزن» مشخص‌شده‌ی $W_i$ دارد که اهمیت آن مسئله را در ایجاد تسلط بر دانش مربوطه نشان می‌هد. هری می‌خواهد مسئله‌هایش را طوری مرتب کند که جمع وزن‌دار زمان پایان مسئله‌ها یعنی $W_1\times C_1+W_2 \times C_2+\ldots +W_n\times C_n$ کمینه شود. برنامه‌ای بنویسید که با گرفتن مجموعه‌ای از $n$ مسئله و هزینه‌ی زمانی هرمسئله ($t_i$) و وزنش ($W_i$) کمترین مقدار ممکن را برای جمع وزن‌دار زمان پایان‌ها یعنی $$ \sum_{i=1}^{n} W_i*C_i $$ پیدا کند. برای مثال فرض کنید دو مسئله داریم: مسئله‌ی اول به اندازه‌ی $t_1=2$ زمان می‌برد و وزن آن $w_1=12$ است و مسئله‌ی دوم به اندازه‌ی $t_2=3$ زمان می‌برد و وزن آن $w_2=4$ است. در این صورت، اگر مسئله‌ی اول ابتدا حل شود مجموع وزن‌دار زمان‌ها $12 \times 2+4 \times 5=44$ می‌شود و اگر مسئله‌ی دوم ابتدا حل شود، مجموع وزن‌دار برابر $4 \times 3+12 \times 5=72$ می‌شود که به وضوح کمترین مقدار مجموع وزن‌دار زمان‌ها برابر $44$ است. # محدودیت‌ها $$ 1 \leq n \leq 20000 $$ $$ 1 \leq t_i, W_i, \leq 10000 $$ + زبان C و C++ + محدودیت زمان: ۵۰۰ میلی‌ثانیه + محدودیت حافظه: ۱۵۰ مگابایت + زبان پایتون و جاوا + محدودیت زمان: ۱۲۵۰ میلی‌ثانیه + محدودیت حافظه: ۲۰۰ مگابایت # ورودی در خط اول ورودی $n$ آمده است که تعداد مسئله‌ها را نشان می‌دهد. در هر یک از $n$ خط بعد دو عدد $t_i$ و $W_i$ که به ترتیب زمان حل شدن و وزن مسئله است آمده است. # خروجی در تنها سطر خروجی فقط یک عدد صحیح بنویسید که نشان‌دهنده‌ی کمترین مقدار ممکن برای مجموع وزن‌دار زمان پایان‌ها مسئله‌ها باشد. # مثال ## نمونه ورودی ``` 2 2 12 3 4 ``` ## نمونه خروجی ``` 44 ```

هری پاتر

انجام دادن تکالیف معمولاً موجب می‌شود دانش‌آموزان درک عمیق‌تری نسبت به درس داشته باشند. هری پاتر به عنوان یکی از دانش‌آموزان هاگوارتز، خیلی وقت‌ها تکالیف زیادی را باید انجام دهد. او هر روز، به عنوان تکلیف، یک مجموعه مسئله از استادانش می‌گیرد. مسئله‌ی $i$ به اندازه‌ی $t_i$ زمان لازم دارد تا کامل انجام شود. با فرض داشتن یک برنامه (یا به عبارت دیگر یک ترتیب از مسئله‌ها)، هر مسئله‌ی $i$ یک «زمان پایان»ای دارد که آن را با $C_i$ نمایش می‌دهیم. برای مثال اگر مسئله‌ی $j$ اولین مسئله‌ای باشد که حل می‌شود آنگاه زمان پایان آن برابر $C_j=t_j$ است. هر مسئله‌ی $i$ همچنین یک «وزن» مشخص‌شده‌ی $W_i$ دارد که اهمیت آن مسئله را در ایجاد تسلط بر دانش مربوطه نشان می‌هد. هری می‌خواهد مسئله‌هایش را طوری مرتب کند که جمع وزن‌دار زمان پایان مسئله‌ها یعنی $W_1\times C_1+W_2 \times C_2+\ldots +W_n\times C_n$ کمینه شود. برنامه‌ای بنویسید که با گرفتن مجموعه‌ای از $n$ مسئله و هزینه‌ی زمانی هرمسئله ( $t_i$ ) و وزنش ( $W_i$ ) کمترین مقدار ممکن را برای جمع وزن‌دار زمان پایان‌ها یعنی $\sum_{i=1}^{n} W_i*C_i$ پیدا کند.

برای مثال فرض کنید دو مسئله داریم: مسئله‌ی اول به اندازه‌ی $t_1=2$ زمان می‌برد و وزن آن $w_1=12$ است و مسئله‌ی دوم به اندازه‌ی $t_2=3$ زمان می‌برد و وزن آن $w_2=4$ است. در این صورت، اگر مسئله‌ی اول ابتدا حل شود مجموع وزن‌دار زمان‌ها $12 \times 2+4 \times 5=44$ می‌شود و اگر مسئله‌ی دوم ابتدا حل شود، مجموع وزن‌دار برابر $4 \times 3+12 \times 5=72$ می‌شود که به وضوح کمترین مقدار مجموع وزن‌دار زمان‌ها برابر $44$ است.

محدودیت‌ها🔗

$1 \leq n \leq 20000$ $1 \leq t_i, W_i, \leq 10000$

زبان C و C++
- محدودیت زمان: ۵۰۰ میلی‌ثانیه
- محدودیت حافظه: ۱۵۰ مگابایت
زبان پایتون و جاوا
- محدودیت زمان: ۱۲۵۰ میلی‌ثانیه
- محدودیت حافظه: ۲۰۰ مگابایت

ورودی🔗

در خط اول ورودی $n$ آمده است که تعداد مسئله‌ها را نشان می‌دهد. در هر یک از $n$ خط بعد دو عدد $t_i$ و $W_i$ که به ترتیب زمان حل شدن و وزن مسئله است آمده است.

خروجی🔗

در تنها سطر خروجی فقط یک عدد صحیح بنویسید که نشان‌دهنده‌ی کمترین مقدار ممکن برای مجموع وزن‌دار زمان پایان‌ها مسئله‌ها باشد.

مثال🔗

نمونه ورودی🔗

2
2 12
3 4

نمونه خروجی🔗

شهر زنبورها بر روی یک شاخه از یک درخت تنومند ساخته شده است. این شهر از $n$ ستون کنار هم تشکیل شده که آن‌ها را به ترتیب از ۱ تا $n$ شماره‌گذاری کرده‌ایم. در هر ستون تعدادی کندو وجود دارد، به طوری که کندوی اول به شاخه متصل است و کندوهای بعدی هر کدام به کندوی بالایی خود متصلند. در نتیجه هر ستون ارتفاعی دارد که آن را با $h_i$ نمایش می‌دهیم. (تعداد کندوهایی که در آن ستون وجود دارد) ملکهٔ زنبورها برای کاهش ضرر در حمله‌ٔ خرس‌ها به تازگی دست به کار شده و گروهی را به سردستگی «هاچ زنبور عسل» مسئول این کار کرده است. در حملهٔ یک خرس به شهر زنبور‌ها، خرس تا جایی که می‌تواند می‌پرد و در نتیجه تمام کندوهایی که دستش به آنها می‌رسد را می‌کند؛ ضرر یک حمله برابر تعداد کندوهایی است که خرس کنده است. در نتیجه هاچ باید کاری کند که در حملهٔ یک خرس کمترین تعداد کندو در دسترس خرس باشد. در هر حرکت هاچ و دستهٔ زنبورها می‌توانند یک کندو از پایین‌ترین جا در یک ستون را بردارند و به پایین‌ترین کندو در یکی از دو ستون مجاور متصل کنند؛ دقت کنید که تنها می‌توان در ستون‌های ۱ تا $n$ کندویی اضافه کرد. دراین صورت ارتفاع این ستون یکی کم شده و به ارتفاع ستونی که کندو در آن قرار داده شده، یک واحد اضافه می‌شود. به دلیل حجم زیاد کار و کمبود زمان هاچ می‌خواهد در کمترین تعداد حرکت، با جابجا کردن کندوها به شیوهٔ گفته شده کاری کند که در حملهٔ یک خرس کمترین خسارت ممکن به شهر وارد شود. شما باید به دست آورید کمترین تعداد حرکت برای اینکه هاچ این کار را انجام دهد چقدر است. برنامه‌ای بنویسید که تعداد و ارتفاع ستون‌های شهر را از ورودی بخواند و کمترین تعداد حرکت برای اینکه هاچ ضرر را به حداقل برساند را در خروجی بنویسد. ## محدودیت‌ها $$ 1 \leq n \leq 1000 $$ $$ 1 \leq h_i \leq 10^6 $$ + زبان C و C++ + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۵۰ مگابایت + زبان پایتون و جاوا + محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۰۰ مگابایت ## ورودی سطر نخست ورودی شامل یک عدد صحیح است: $n$ که تعداد ستون‌های یک شهر را مشخص می‌کند. سطر بعدی محتوی $n$ عدد صحیح می‌باشد؛ عدد $i$اُم نشان‌دهندهٔ ارتفاع ستون $i$اُم ($h_i$) است. ## خروجی در تنها سطر خروجی یک عدد که نشانگر کمترین تعداد حرکات لازم می‌باشد بنویسید. ## مثال ## نمونه ورودی ``` 5 4 1 1 2 2 ``` ## نمونه خروجی ``` 3 ```

شهر زنبورها

شهر زنبورها بر روی یک شاخه از یک درخت تنومند ساخته شده است. این شهر از $n$ ستون کنار هم تشکیل شده که آن‌ها را به ترتیب از ۱ تا $n$ شماره‌گذاری کرده‌ایم. در هر ستون تعدادی کندو وجود دارد، به طوری که کندوی اول به شاخه متصل است و کندوهای بعدی هر کدام به کندوی بالایی خود متصلند. در نتیجه هر ستون ارتفاعی دارد که آن را با $h_i$ نمایش می‌دهیم. (تعداد کندوهایی که در آن ستون وجود دارد)

ملکهٔ زنبورها برای کاهش ضرر در حمله‌ٔ خرس‌ها به تازگی دست به کار شده و گروهی را به سردستگی «هاچ زنبور عسل» مسئول این کار کرده است. در حملهٔ یک خرس به شهر زنبور‌ها، خرس تا جایی که می‌تواند می‌پرد و در نتیجه تمام کندوهایی که دستش به آنها می‌رسد را می‌کند؛ ضرر یک حمله برابر تعداد کندوهایی است که خرس کنده است. در نتیجه هاچ باید کاری کند که در حملهٔ یک خرس کمترین تعداد کندو در دسترس خرس باشد.

در هر حرکت هاچ و دستهٔ زنبورها می‌توانند یک کندو از پایین‌ترین جا در یک ستون را بردارند و به پایین‌ترین کندو در یکی از دو ستون مجاور متصل کنند؛ دقت کنید که تنها می‌توان در ستون‌های ۱ تا $n$ کندویی اضافه کرد. دراین صورت ارتفاع این ستون یکی کم شده و به ارتفاع ستونی که کندو در آن قرار داده شده، یک واحد اضافه می‌شود. به دلیل حجم زیاد کار و کمبود زمان هاچ می‌خواهد در کمترین تعداد حرکت، با جابجا کردن کندوها به شیوهٔ گفته شده کاری کند که در حملهٔ یک خرس کمترین خسارت ممکن به شهر وارد شود.

شما باید به دست آورید کمترین تعداد حرکت برای اینکه هاچ این کار را انجام دهد چقدر است. برنامه‌ای بنویسید که تعداد و ارتفاع ستون‌های شهر را از ورودی بخواند و کمترین تعداد حرکت برای اینکه هاچ ضرر را به حداقل برساند را در خروجی بنویسد.

محدودیت‌ها🔗

$1 \leq n \leq 1000$ $1 \leq h_i \leq 10^6$

زبان C و C++
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۱۵۰ مگابایت
زبان پایتون و جاوا
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۰۰ مگابایت

ورودی🔗

سطر نخست ورودی شامل یک عدد صحیح است: $n$ که تعداد ستون‌های یک شهر را مشخص می‌کند. سطر بعدی محتوی $n$ عدد صحیح می‌باشد؛ عدد $i$ اُم نشان‌دهندهٔ ارتفاع ستون $i$ اُم ( $h_i$ ) است.

خروجی🔗

در تنها سطر خروجی یک عدد که نشانگر کمترین تعداد حرکات لازم می‌باشد بنویسید.

مثال🔗

نمونه ورودی🔗

5
4 1 1 2 2

نمونه خروجی🔗

نردبان کلمات یک دنباله از کلمات است که که هر دو تا کلمه‌ی پشت‌سر‌هم صرفا فقط در یک حرف تفاوت داشته باشند.. یک مثال از این نردبان کلمات (‌البته به صورت افقی نوشته‌ایم!!) می‌تواند $todo, food, wood, word, down$ باشد. توجه کنید که حروف دو کلمه‌ی پشت‌سر‌هم می‌تواند جابه‌جا شود ولی دقیقا یک حرف باید تغییر کند. برای این مسئله به شما یک فرهنگ لغات از کلمات مختلف داده می‌شود که همگی طولشان یکسان است. شما باید یک برنامه بنویسید که کوتاه‌ترین نردبان از کلمات را بیابد که کلمه‌ی اول و کلمه‌ی آخر آن هیچ حرف یکسانی نداشته باشد. ## توجه اگر $s$ و $t$ دو رشته از حروف باشند، که تعداد حروفشان یکسان است و $s_i$ حرف $i$ام رشته‌ی $s$ را نشان دهد آنگاه گوییم $s$ از $t$ به صورت الفبایی کوچکتر است اگر برای یک $i$ داشته باشیم $s_i < t_i$ و برای تمام $j<i$ داشته باشیم $s_j=t_j$ # محدودیت‌ها $$ 1 \leq n \leq 100 $$ $$ 1 \leq l \leq 20 $$ + زبان C و C++ + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۵۰ مگابایت + زبان پایتون و جاوا + محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۰۰ مگابایت # ورودی سطر نخست ورودی شامل دو عدد صحیح به ترتیب $n$ و $l$ می‌باشد که نشان‌دهنده‌ی تعداد کلمات فرهنگ لغات و طول هر کدام می‌باشد. در هر کدام از $n$ سطر بعد یک کلمه با حروف $a-z$ به طول $l$ آمده است. # خروجی در تنها سطر خروجی کوچکترین نردبان الفبایی با شرایط خواسته شده را چاپ کنید و بین هر دو کلمه‌ی پشت سر هم فاصله چاپ کنید. ورودی به گونه‌ای داده می‌شود که تضمین شود حتما نردبان خواسته شده وجود دارد و اگر چندین نردبان با طول یکسان وجود داشت، نردبانی را انتخاب کنید که با توجه به تعریف داده شده به صورت الفبایی کوچکتر باشد. # مثال ## نمونه ورودی ``` 9 3 alt spy sea opt pea ape spa apt ale ``` ## نمونه خروجی ``` ale alt apt opt ```

نردبان الفبایی

نردبان کلمات یک دنباله از کلمات است که که هر دو تا کلمه‌ی پشت‌سر‌هم صرفا فقط در یک حرف تفاوت داشته باشند.. یک مثال از این نردبان کلمات (‌البته به صورت افقی نوشته‌ایم!!) می‌تواند $todo, food, wood, word, down$ باشد. توجه کنید که حروف دو کلمه‌ی پشت‌سر‌هم می‌تواند جابه‌جا شود ولی دقیقا یک حرف باید تغییر کند. برای این مسئله به شما یک فرهنگ لغات از کلمات مختلف داده می‌شود که همگی طولشان یکسان است. شما باید یک برنامه بنویسید که کوتاه‌ترین نردبان از کلمات را بیابد که کلمه‌ی اول و کلمه‌ی آخر آن هیچ حرف یکسانی نداشته باشد.

توجه🔗

اگر $s$ و $t$ دو رشته از حروف باشند، که تعداد حروفشان یکسان است و $s_i$ حرف $i$ ام رشته‌ی $s$ را نشان دهد آنگاه گوییم $s$ از $t$ به صورت الفبایی کوچکتر است اگر برای یک $i$ داشته باشیم $s_i < t_i$ و برای تمام $j<i$ داشته باشیم $s_j=t_j$

محدودیت‌ها🔗

$1 \leq n \leq 100$ $1 \leq l \leq 20$

زبان C و C++
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۱۵۰ مگابایت
زبان پایتون و جاوا
- محدودیت زمان: ۲.۵ ثانیه
- محدودیت حافظه: ۲۰۰ مگابایت

ورودی🔗

سطر نخست ورودی شامل دو عدد صحیح به ترتیب $n$ و $l$ می‌باشد که نشان‌دهنده‌ی تعداد کلمات فرهنگ لغات و طول هر کدام می‌باشد. در هر کدام از $n$ سطر بعد یک کلمه با حروف $a-z$ به طول $l$ آمده است.

خروجی🔗

در تنها سطر خروجی کوچکترین نردبان الفبایی با شرایط خواسته شده را چاپ کنید و بین هر دو کلمه‌ی پشت سر هم فاصله چاپ کنید. ورودی به گونه‌ای داده می‌شود که تضمین شود حتما نردبان خواسته شده وجود دارد و اگر چندین نردبان با طول یکسان وجود داشت، نردبانی را انتخاب کنید که با توجه به تعریف داده شده به صورت الفبایی کوچکتر باشد.

مثال🔗

نمونه ورودی🔗

9 3
alt
spy
sea
opt
pea
ape
spa
apt
ale

نمونه خروجی🔗

ale alt apt opt

در يک منطقه‌ى اروپايى باستان‌شناسان اخيراً نسخى خطى را يافته‌اند که فهم متن کتیبه، برای آن‌ها دستیابی به فرهنگ منطقه حیاتی ارزیابی شده است. در رمزگشايى بخش نوشتارى اين کتيبه‌ها دانشمندان با چالشى جدى مواجه شده‌اند. علاوه‌بر اين‌که نمى‌دانند کتيبه به چه زبانى نوشته شده، بعضى حروف آن طى زمان از بين رفته و قابل تشخيص نيست. يکى از دانشمندان با مطالعه‌ى کتيبه زبانى را به خاطر آورده که در آن حداکثر $V_C$ حرف صدادار پشت‌سرهم و $C_C$ حرف بى‌صداى متوالى ممکن است بيايد. همچنين در اين زبان حداکثر $V_E$ حرف صدادار متوالى مى‌توانند يکسان باشند و نيز $C_E$ حرف بى‌صداى متوالى. اين دانشمند براى کسب اطلاعات بيشتر در مورد اين زبان گروه را ترک کرده است. ديگران سعى دارند که تا بازگشت او کتيبه‌ها را بررسى کرده و ببينند که آيا با نظريه‌ى دانشمند تناقض دارد يا خير. آن‌ها مى‌خواهند که درصورت سازگارى نظريه با کتيبه‌ها ميزان کار پيشروى خود را تخمين بزنند. به عبارت ديگر، مى‌خواهند بدانند که متن را به چند صورت مى‌توان به صورت سازگار با نظريه رمزگشايى کرد. از شما براى کمک در اين کار دعوت رسمى به‌عمل آمده است. حروف مورد استفاده در اين کتيبه‌ها، بر حسب اتفاق، همان حروف کوچک الفباى انگليسى است. از بين آن‌ها حروف "aeiou" حروف صدادار هستند. # محدودیت‌ها $$ 1 \leq V_E \leq V_C \leq 4 $$ $$ 1 \leq C_E \leq C_C \leq 4 $$ + زبان C و C++ + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۵۰ مگابایت + زبان پایتون و جاوا + محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۰۰ مگابایت # ورودی سطر اول ورودی چهار عدد صحيح $C_C, C_E, V_C, V_E$ به ترتیب آمده‌اند. سطر دوم شامل يک کلمه از کتيبه است و حروف ناخواناى آن با * نشان داده شده است. هر کلمه از کتیبه حداکثر ۱۵ حرف است. # خروجی يک عدد صحيح در آن بنويسيد که تعداد روش‌هايى است که مى‌توان کلمه‌ى ورودى را با توجه به شرايط مذکور ساخت. فرض کنيد که پاسخ همواره در عدد صحيح علامت‌دار ۶۴ بیتی جای می‌گیرد. # مثال ## نمونه ورودی ۱ ``` 1 1 1 1 a** ``` ## نمونه خروجی ۱ ``` 105 ``` ## نمونه ورودی ۲ ``` 1 1 1 1 b*i ``` ## نمونه خروجی ۲ ``` 0 ``` ## نمونه ورودی ۳ ``` 1 2 1 2 ancient ``` ## نمونه خروجی ۳ ``` 1 ``` ## نمونه ورودی ۴ ``` 4 4 4 4 man****ipt ``` ## نمونه خروجی ۴ ``` 261870 ```

کتیبه‌ی باستانی

در يک منطقه‌ى اروپايى باستان‌شناسان اخيراً نسخى خطى را يافته‌اند که فهم متن کتیبه، برای آن‌ها دستیابی به فرهنگ منطقه حیاتی ارزیابی شده است. در رمزگشايى بخش نوشتارى اين کتيبه‌ها دانشمندان با چالشى جدى مواجه شده‌اند. علاوه‌بر اين‌که نمى‌دانند کتيبه به چه زبانى نوشته شده، بعضى حروف آن طى زمان از بين رفته و قابل تشخيص نيست. يکى از دانشمندان با مطالعه‌ى کتيبه زبانى را به خاطر آورده که در آن حداکثر $V_C$ حرف صدادار پشت‌سرهم و $C_C$ حرف بى‌صداى متوالى ممکن است بيايد. همچنين در اين زبان حداکثر $V_E$ حرف صدادار متوالى مى‌توانند يکسان باشند و نيز $C_E$ حرف بى‌صداى متوالى. اين دانشمند براى کسب اطلاعات بيشتر در مورد اين زبان گروه را ترک کرده است. ديگران سعى دارند که تا بازگشت او کتيبه‌ها را بررسى کرده و ببينند که آيا با نظريه‌ى دانشمند تناقض دارد يا خير. آن‌ها مى‌خواهند که درصورت سازگارى نظريه با کتيبه‌ها ميزان کار پيشروى خود را تخمين بزنند. به عبارت ديگر، مى‌خواهند بدانند که متن را به چند صورت مى‌توان به صورت سازگار با نظريه رمزگشايى کرد. از شما براى کمک در اين کار دعوت رسمى به‌عمل آمده است. حروف مورد استفاده در اين کتيبه‌ها، بر حسب اتفاق، همان حروف کوچک الفباى انگليسى است. از بين آن‌ها حروف "aeiou" حروف صدادار هستند.

محدودیت‌ها🔗

$1 \leq V_E \leq V_C \leq 4$ $1 \leq C_E \leq C_C \leq 4$

زبان C و C++
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۱۵۰ مگابایت
زبان پایتون و جاوا
- محدودیت زمان: ۲.۵ ثانیه
- محدودیت حافظه: ۲۰۰ مگابایت

ورودی🔗

سطر اول ورودی چهار عدد صحيح $C_C, C_E, V_C, V_E$ به ترتیب آمده‌اند. سطر دوم شامل يک کلمه از کتيبه است و حروف ناخواناى آن با * نشان داده شده است. هر کلمه از کتیبه حداکثر ۱۵ حرف است.

خروجی🔗

يک عدد صحيح در آن بنويسيد که تعداد روش‌هايى است که مى‌توان کلمه‌ى ورودى را با توجه به شرايط مذکور ساخت. فرض کنيد که پاسخ همواره در عدد صحيح علامت‌دار ۶۴ بیتی جای می‌گیرد.

مثال🔗

نمونه ورودی ۱🔗

1 1 1 1
a**

نمونه خروجی ۱🔗

نمونه ورودی ۲🔗

1 1 1 1
b*i

نمونه خروجی ۲🔗

نمونه ورودی ۳🔗

1 2 1 2
ancient

نمونه خروجی ۳🔗

نمونه ورودی ۴🔗

4 4 4 4
man****ipt

نمونه خروجی ۴🔗

زیررشته

رشته‌ي $s$ و عدد $m$ و $k$ به شما داده شده است. از بین زیررشته‌های به طول $m$ اولین زیررشته‌ای که حداقل $k$ بار آمده است را پیدا کنید.

ورودی🔗

رشته‌ي $s$ و عدد $m$ و $k$

خروجی🔗

مکان اولین زیررشته‌ی خواسته شده را در خروجی چاپ کنید. درصورتی که چنین زیررشته‌ای وجود نداشت، NoSolution چاپ کنید.(اندیس رشته از صفر شروع می‌شود)

محدودیت‌ها🔗

$|s| < 10^6$

مثال🔗

ورودی نمونه

‪uvklkjwqiosqpiucplkjwqpqwzvbiwlkjwq‬‬‫‪rtashgdfjdfsjshiertq‬‬
5 3

خروجی نمونه

خانم دکتر دنباله‌ای از اعداد طبیعی دارد. همان‌طور که می‌دانید دکتر‌ها برعکس مهندس‌ها از صعودی‌بودن دنباله‌ها لذت می‌برند ولی بلد نیستند دنباله‌هایشان را صعودی کنند. برای همین خانم دکتر از آقای مهندس خواسته‌است تا دنباله‌اش را برایش صعودی کند. (منظور از دنباله‌‌ی صعودی دنباله‌ای است که هیچ عضوی از آن از عضو قبلی‌اش کمتر نیست) آقای مهندس در هر حرکت می‌تواند یکی از ارقام یکی از اعداد دنباله را حذف کند. دقت کنید که وقتی تمامی ارقام یکی از اعداد دنباله را حذف کنیم مقدارش صفر خواهد شد. او به عنوان یک مهندس **مجبور است** در کم‌ترین تعداد حرکت دنباله‌ را صعودی کند. این کم‌ترین تعداد حرکت چقدر است؟ هم‌چنین او می‌خواهد جمع اعداد دنباله‌ی نهایی که با کمترین تعداد حرکات به آن می‌رسد کمینه باشد. (در عین استفاده از کمترین تعداد حرکت) این مجموع کمینه را نیز پیدا کنید. ## ورودی سطر اول ورودی شامل عدد طبیعی $n$، تعداد اعداد دنباله، است. در سطر بعد $n$ عدد طبیعی $a_i$ آمده‌است که اعداد دنباله را نشان می‌دهند. + $1\leq n \leq 50000$ + $1\leq a_i \leq 10^18$ + هیچ کدام از اعداد دنباله رقم $0$ ندارند. ## خروجی در سطر اول خروجی کمترین تعداد حرکت برای صعودی کردن دنباله را چاپ کنید. در سطر دوم $n$ عدد چاپ کنید که اعداد دنباله نهایی را نشان می‌دهند که هم باید صعودی باشند و هم مجموع‌شان کمینه شود. در صورت وجود چندین جواب هر کدام از آن‌ها را می‌توانید چاپ کنید. ## مثال ورودی نمونه ۱ ``` 4 63 54 45 36 ``` خروجی نمونه ۱ ``` 3 3 4 4 36 ``` ورودی نمونه ۲ ``` 6 8 16 16 1393 6 19 ``` خروجی نمونه ۲ ``` 6 0 1 1 1 6 19 ``` ۲۴امین دوره‌ المپیاد کامپیوتر - آزمون هفتم - ۱۳۹۳/۰۶/۱۹

حذف ارقام

خانم دکتر دنباله‌ای از اعداد طبیعی دارد. همان‌طور که می‌دانید دکتر‌ها برعکس مهندس‌ها از صعودی‌بودن دنباله‌ها لذت می‌برند ولی بلد نیستند دنباله‌هایشان را صعودی کنند. برای همین خانم دکتر از آقای مهندس خواسته‌است تا دنباله‌اش را برایش صعودی کند. (منظور از دنباله‌‌ی صعودی دنباله‌ای است که هیچ عضوی از آن از عضو قبلی‌اش کمتر نیست) آقای مهندس در هر حرکت می‌تواند یکی از ارقام یکی از اعداد دنباله را حذف کند. دقت کنید که وقتی تمامی ارقام یکی از اعداد دنباله را حذف کنیم مقدارش صفر خواهد شد.

او به عنوان یک مهندس مجبور است در کم‌ترین تعداد حرکت دنباله‌ را صعودی کند. این کم‌ترین تعداد حرکت چقدر است؟ هم‌چنین او می‌خواهد جمع اعداد دنباله‌ی نهایی که با کمترین تعداد حرکات به آن می‌رسد کمینه باشد. (در عین استفاده از کمترین تعداد حرکت) این مجموع کمینه را نیز پیدا کنید.

ورودی🔗

سطر اول ورودی شامل عدد طبیعی $n$ ، تعداد اعداد دنباله، است.

در سطر بعد $n$ عدد طبیعی $a_i$ آمده‌است که اعداد دنباله را نشان می‌دهند.

$1\leq n \leq 50000$
$1\leq a_i \leq 10^18$
هیچ کدام از اعداد دنباله رقم $0$ ندارند.

خروجی🔗

در سطر اول خروجی کمترین تعداد حرکت برای صعودی کردن دنباله را چاپ کنید.

در سطر دوم $n$ عدد چاپ کنید که اعداد دنباله نهایی را نشان می‌دهند که هم باید صعودی باشند و هم مجموع‌شان کمینه شود. در صورت وجود چندین جواب هر کدام از آن‌ها را می‌توانید چاپ کنید.

مثال🔗

ورودی نمونه ۱

4
63 54 45 36

خروجی نمونه ۱

3
3 4 4 36

ورودی نمونه ۲

6
8 16 16 1393 6 19

خروجی نمونه ۲

6
0 1 1 1 6 19

۲۴امین دوره‌ المپیاد کامپیوتر - آزمون هفتم - ۱۳۹۳/۰۶/۱۹

موضوع امنیت در اینترنت یکی از مهم‌ترین موضوع‌های مورد مطالعه‌ی سال‌های اخیر است. یکی از روش‌های امنیت، رمزنگاری داده‌ها است. الگوریتم «پفکی» یکی از پرکاربردترین روش‌ها برای رمزنگاری است. این الگوریتم برای رمزنگاری داده‌ها، از دو دنباله‌ی $a_0,a_1,\cdots,a_{n-1}$ و $b_0,b_1,\cdots,b_{n-1}$ استفاده می‌کند. میزان امنیت الگوریتم «پفکی» با استفاده از روش زیر قابل محاسبه است: «جدولی با $n$ سطر و $32 \times m$ ستون در نظر بگیرید که در خانه‌ی $(i,j)$ $(0 \leq i \leq n-1 , \, 0 \leq j \leq 32 \times m-1)$ از آن $getBit(a_i \bigoplus b_{\lfloor \frac{j}{32} \rfloor}, j \, mod \, 32)$ نوشته شده است. در این‌جا تابع $getBit(x,p)$ بیت $p$ام از عدد $x$ را برمی‌گرداند، برای مثال $getBit(6,0) = 0$ و $getBit(6,1) = 1$ و $getBit(6,2) = 1$ هستند. تمام جدول‌هایی که از جدول ساخته شده با جابه‌جایی ستون‌ها می‌توان ساخت را در نظر بگیرید(حداکثر $32m!$ جدول متفاوت) و به ازای هر کدام از این جدول‌ها اندازه‌ي بزرگترین زیر جدولی (بزرگترین از لحاظ تعداد خانه‌های تشکیل دهنده) که تمام خانه‌هایش ۱ است را محاسبه کنید. بیشینه اعداد محاسبه شده برابر با میزان امنیت الگوریتم پفکی به ازای ورودی‌های $a_0,a_1,\cdots,a_{n-1}$ و $b_0,b_1,\cdots,b_{n-1}$ است. دقت کنید که تنها جابه‌جایی ستون‌ها مجاز است و جابه‌جایی سطر‌ها مجاز نیست.» شما باید برنامه‌ای بنویسید که باتوجه به ورودی‌های الگوریتم پفکی، میزان امنیت آن را مشخص کند. **علامت $\bigoplus$ نشان‌دهنده عملگر $xor$ است. عبارت $a\, mod\, b$ نیز نشان‌دهنده باقی مانده عدد $a$ بر $b$ است.** ## ورودی در سطر اول ورودی به ترتیب دو عدد طبیعی $n$ و $m$ آمده است. در سطر دوم $n$ عدد صحیح آمده است که عدد $i$ام $(1\leq i \leq n)$ آن نشان‌دهنده‌ي $a_{i-1}$ است. در سطر سوم $m$ عدد صحیح آمده است که عدد $i$ام $(1 \leq i \leq m)$ آن نشان‌دهنده‌ی $b_{i-1}$ است. ## خروجی در تنها سطر خروجی میزان امنیت روش پفکی را به ازای دنباله‌هایی که در ورودی آمده است، چاپ کنید. ## محدودیت‌ها + $1 \leq n,m \leq 10^6$ + $ 0 \leq a_i,b_i \leq 2^{30}$ ## مثال ورودی نمونه ۱ ``` 2 2 1 2 1 2 ``` خروجی نمونه ۱ ``` 2 ``` ورودی نمونه ۲ ``` 4 4 1 3 2 10 4 1 7 15 ``` خروجی نمونه ۲ ``` 16 ``` ۲۵امین دوره المپیاد کامپیوتر - آزمون نهایی اول - ۱۳۹۴/۶/۱۸

رمزنگاری

موضوع امنیت در اینترنت یکی از مهم‌ترین موضوع‌های مورد مطالعه‌ی سال‌های اخیر است. یکی از روش‌های امنیت، رمزنگاری داده‌ها است. الگوریتم «پفکی» یکی از پرکاربردترین روش‌ها برای رمزنگاری است. این الگوریتم برای رمزنگاری داده‌ها، از دو دنباله‌ی $a_0,a_1,\cdots,a_{n-1}$ و $b_0,b_1,\cdots,b_{n-1}$ استفاده می‌کند. میزان امنیت الگوریتم «پفکی» با استفاده از روش زیر قابل محاسبه است:

«جدولی با $n$ سطر و $32 \times m$ ستون در نظر بگیرید که در خانه‌ی $(i,j)$ $(0 \leq i \leq n-1 , \, 0 \leq j \leq 32 \times m-1)$ از آن $getBit(a_i \bigoplus b_{\lfloor \frac{j}{32} \rfloor}, j \, mod \, 32)$ نوشته شده است. در این‌جا تابع $getBit(x,p)$ بیت $p$ ام از عدد $x$ را برمی‌گرداند، برای مثال $getBit(6,0) = 0$ و $getBit(6,1) = 1$ و $getBit(6,2) = 1$ هستند. تمام جدول‌هایی که از جدول ساخته شده با جابه‌جایی ستون‌ها می‌توان ساخت را در نظر بگیرید(حداکثر $32m!$ جدول متفاوت) و به ازای هر کدام از این جدول‌ها اندازه‌ي بزرگترین زیر جدولی (بزرگترین از لحاظ تعداد خانه‌های تشکیل دهنده) که تمام خانه‌هایش ۱ است را محاسبه کنید. بیشینه اعداد محاسبه شده برابر با میزان امنیت الگوریتم پفکی به ازای ورودی‌های $a_0,a_1,\cdots,a_{n-1}$ و $b_0,b_1,\cdots,b_{n-1}$ است. دقت کنید که تنها جابه‌جایی ستون‌ها مجاز است و جابه‌جایی سطر‌ها مجاز نیست.»

شما باید برنامه‌ای بنویسید که باتوجه به ورودی‌های الگوریتم پفکی، میزان امنیت آن را مشخص کند.

علامت $\bigoplus$ نشان‌دهنده عملگر $xor$ است. عبارت $a\, mod\, b$ نیز نشان‌دهنده باقی مانده عدد $a$ بر $b$ است.

ورودی🔗

در سطر اول ورودی به ترتیب دو عدد طبیعی $n$ و $m$ آمده است.

در سطر دوم $n$ عدد صحیح آمده است که عدد $i$ ام $(1\leq i \leq n)$ آن نشان‌دهنده‌ي $a_{i-1}$ است.

در سطر سوم $m$ عدد صحیح آمده است که عدد $i$ ام $(1 \leq i \leq m)$ آن نشان‌دهنده‌ی $b_{i-1}$ است.

خروجی🔗

در تنها سطر خروجی میزان امنیت روش پفکی را به ازای دنباله‌هایی که در ورودی آمده است، چاپ کنید.

محدودیت‌ها🔗

$1 \leq n,m \leq 10^6$
$0 \leq a_i,b_i \leq 2^{30}$

مثال🔗

ورودی نمونه ۱

2 2
1 2
1 2

خروجی نمونه ۱

ورودی نمونه ۲

4 4
1 3 2 10
4 1 7 15

خروجی نمونه ۲

۲۵امین دوره المپیاد کامپیوتر - آزمون نهایی اول - ۱۳۹۴/۶/۱۸