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

شرکت همکاران سیستم قصد دارد برنامه‌های خود را از.NET به Golang تغییر دهد. به همین منظور اخیراً با سندی مواجه شده که پر از رشته‌های .NET‌است و باید همه‌ی آن‌ها را به Golang تغییر دهند. برای همین از شما می‌خواهند برنامه‌ای بنویسید که این کار را انجام دهد.

به طور دقیق‌تر، رشته‌ای از کاراکترها به شما داده می‌شود و باید تمام زیررشته‌های متوالی .NET در آن را به Golang تغییر دهید. برای درک بهتر به مثال‌ها توجه کنید.

ورودی🔗

در تنها سطر ورودی، رشته‌ی $s$ شامل حروف بزرگ و کوچک انگلیسی و کاراکترهای .، ? و ! است.

$1 \leq |s| \leq 100$

خروجی🔗

در یک سطر، رشته‌ی تغییر یافته را چاپ کنید.

توجه کنید که سیستم داوری به بزرگ و کوچک بودن حروف حساس است.

مثال‌ها🔗

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

WeDevelope.NETHere!

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

WeDevelopeGolangHere!

رشته‌ی WeDevelope.NETHere! دارای یک زیرشته‌ی .NET و باید آن را به Golang تغییر دهیم، بنابراین خروجی به صورت WeDevelopeGolangHere!است.

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

WeLove.NETandWeUse.NETinHamkaran.

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

WeLoveGolangandWeUseGolanginHamkaran.

رشته‌ی WeLove.NETandWeUse.NETinHamkaran. دارای دو زیرشته‌ی .NET و باید آن‌ها را به Golang تغییر دهیم، بنابراین خروجی به صورت WeLoveGolangandWeUseGolanginHamkaran.است.

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

.NET.ne.net.NeTNET.NNET

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

Golang.ne.net.NeTNET.NNET

رشته‌ی .NET.ne.net.NeTNET.NNET دارای یک زیرشته‌ی .NET و باید آن را به Golang تغییر دهیم، بنابراین خروجی به صورت Golang.ne.net.NeTNET.NNETاست.

if 1 <= n <= 100:
    # answer of problem
else:
    # print('invalid input')

input('please enter:')

package ir.quera.contest;

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

نقشه‌ی کشور فانو مانند شکل زیر است. این کشور از ۷ شهر با شماره‌های ۱‍ تا ۷ تشکیل شده است. بین این شهرها تعدادی جاده مستقیم و دو طرفه وجود دارد.

در یک روز متوجه می‌شویم که دزدی در شهر $r$ وجود دارد و پلیس این کشور در شهر $c$ مشغول خدمت رسانی است. بازی دزد و پلیس شروع می‌شود.

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

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

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

حال از شما می‌خواهیم کمترین تعداد روزی که باید بگذرد تا دزد دستگیر شود را چاپ کنید و یا اعلام کنید دزد هیچ‌وقت دستگیر نمی‌شود.

ورودی🔗

در سطر اول ورودی، عدد صحیح $c$ آمده که شماره‌ی شهری که پلیس در آن قرار دارد را نشان می‌دهد. در سطر دوم ورودی، عدد صحیح $r$ آمده که شماره‌ی شهری که دزد در آن قرار دارد را نشان می‌دهد.

$1 \leq r \neq c \leq 7$

خروجی🔗

در تنها سطر خروجی، یک عدد صحیح که برابر کمترین تعداد روزی که باید بگذرد، تا پلیس، دزد را بگیرد را چاپ کنید. اگر دزد هیچ‌وقت توسط پلیس دستگیر نمی‌شود -1 چاپ کنید.

مثال‌ها🔗

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

2
6

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

1

در این نمونه، پلیس روز اول، از شهر ۲ وارد شهر ۶ می‌شود و دزد را دستگیر می‌کند.

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

7
1

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

2

در این نمونه، پلیس روز اول، از شهر ۷ وارد شهر ۴ می‌شود. شب اول دزد به یکی از شهرهای ۲ یا ۳ می‌رود و در هر کدام از این شهرها که باشد، پلیس روز دوم آن را دستگیر می‌کند.

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

4
7

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

1

در این نمونه، پلیس روز اول، از شهر ۴ وارد شهر ۷ می‌شود و دزد را دستگیر می‌کند.

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

در زبان برنامه‌نویسی گولنگستان متغیرها حافظه‌های ۱، ۲، ۳ یا ۴ بایتی دارند. وقتی یک شئ با $n$ متغیر به حجم‌های $s_1, s_2, \dots, s_n\,$ تعریف می‌کنیم. حافظه‌ها با قاعده‌ی زیر در بسته‌های ۴ بایتی، پشت سرهم قرار می‌گیرند.

متغیرها را به ترتیب اضافه می‌کنیم. اگر متغیری که نوبت اضافه شدن آن است، به انتهای بسته‌ی قبلی می‌تواند اضافه شود، آن را اضافه می‌کنیم و به سراغ متغیر بعدی (در صورت وجود) می‌رویم. اما اگر این متغیر نمی‌تواند به انتهای بسته‌ی آخر اضافه شود، همه‌ی فضای خالی آن را رها می‌کنیم و آن بسته را می‌بندیم (اصطلاحاً به این حافظه‌های تلف شده padding space می‌گویند). سپس در یک بسته‌ی ۴ بایتی جدید، حافظه مورد نیاز متغیر بعدی را به بایت‌های اول آن اختصاص می‌دهیم.

برای مثال فرض کنید $n = 3$ متغیر داشته باشیم: $s_1 = 1$، $s_2 = 4$ و $s_3 = 1$. در این صورت متغیر $s_1$ در ابتدای یک بسته قرار می‌گیرد، چون متغیر $s_2$ را نمی‌توان به همان بسته اضافه کرد، پس ۳ بایت باقی‌مانده‌ی بسته‌ی اول را padding space در نظر می‌گیریم. سپس متغیر $s_2$ را در یک بسته‌ی جدید قرار داده و در نهایت $s_3$ را در بایت اول یک بسته قرار می‌دهیم. (در آخرین بسته padding space نداریم.)

به این ترتیب وضعیت نوار حافظه به صورت زیر خواهد بود و در مجموع ۳ حافظه تلف شده خواهیم داشت.

حال می‌دانیم اگر ترتیب این سه متغیر را به این صورت که $s_1 = 4$، $s_2 = 1$ و $s_3 = 1$ عوض می‌کردیم. وضعیت نوار حافظه به این صورت تغییر می‌کرد و هیچ حافظه‌ای تلف نمی‌شود.

حال به شما ترتیب اولیه حافظه متغیرها داده می‌شود از شما می‌خواهیم ترتیب آن‌ها را طوری تغییر دهید که حافظه‌های تلف شده (padding space) کمینه شود و در نهایت این کمینه مقدار را چاپ کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد سناریوها را نشان می‌دهد.

$1 \leq t \leq 1000$

در سطر اول هر سناریو، عدد صحیح $n$ که نشان دهنده‌ی تعداد متغیرها است داده می‌شود.

$1 \leq n \leq 100$

در سطر دوم هر سناریو، $n$ عدد صحیح که مقدار حافظه‌ی متغیرها یعنی $s_1, s_2, \dots, s_n\,$ را نشان می‌دهد.

$1 \leq s_i \leq 4$

خروجی🔗

در $t$ سطر برای هر سناریو، کمینه حافظه‌ی تلف شده (padding space) در بین تمام ترتیب‌های مختلف برای متغیرها را چاپ کنید.

مثال‌ها🔗

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

4
3
1 4 1
4
4 2 3 4
1
1
5
3 3 3 3 3

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

0
1
0
4

سناریو اول در صورت سوال توضیح داده شده.

یک نمونه از ترتیب بهینه، برای سناریو دوم، با ۱ حافظه تلف شده، به صورت زیر است:

تنها ترتیب ممکن، برای سناریو سوم، با ۰ حافظه‌ی تلف شده، به صورت زیر است:

تنها ترتیب ممکن، برای سناریو چهارم، با ۴ حافظه‌ی تلف شده، به صورت زیر است:

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

علی همیشه آرایه‌هایش را گم می‌کند. به همین منظور از روی آرایه‌ها برای خودش یک آرایه‌ی دیگر می‌سازد. به طور دقیق‌تر آرایه‌ای از اعداد صحیح مثل $a_1, a_2, \dots, a_n\,$ را در نظر بگیرید. از روی آن آرایه‌ی $b_1, b_2, \dots, b_n\,$ را می‌سازد. به این صورت که برای هر $i$ از ۱ تا $n$ مقدار $b_i$ از رابطه‌ی زیر بدست می‌آید.

$b_i = \max\{a_1, …, a_i\} + \min\{a_1, …, a_i\}$

حال علی پیش از اینکه دنبال آرایه‌ی $a_1, a_2, \dots, a_n\,$ بگردد، می‌خواهد از روی آرایه‌ی $b_1, b_2, \dots, b_n\,$ بررسی کند چند حالت برای آرایه‌ی اولیه وجود دارد.

به علی کمک کنید تا این تعداد را پیدا کند. چون ممکن است پاسخ مسئله خیلی بزرگ شود، باقی‌مانده این مقدار را به پیمانه‌ی $10^9 + 7$ چاپ کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $n$ داده می‌شود. $1 \leq n \leq 100 \, 000$

در سطر دوم ورودی، $n$ عدد صحیح $b_1, b_2, \dots, b_n\,$ با فاصله از هم داده می‌شود. $1 \leq b_i \leq 10^9$

خروجی🔗

در تنها سطر خروجی، باقی‌مانده‌ی تعداد حالت‌های ممکن برای دنباله‌ی $a$ را به پیمانه‌ی $10^9 + 7$ چاپ کنید.

مثال‌ها🔗

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

5
2 5 5 3 8

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

4

برای مثال اگر آرایه‌ی $a$ برابر $\langle 1, 4, 2, -1, 9 \rangle,$ باشد، دنباله‌ی $b$ی داده شده، بدست می‌آید (۳ آرایه‌ی اولیه دیگر نیز وجود دارد).

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

4
2 1 2 1

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

1

آرایه‌ی $a$ فقط می‌تواند $\langle 1, 0, 2, -1 \rangle$ باشد.

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

1
1403

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

0

هیچ آرایه‌ی $a$ با یک عنصر وجود ندارد.

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

امین یک معادله ساده به فرم $A + B = C$ روی تخته نوشته بود. یک روز مهلا تصمیم می‌گیرد کاراکترهای + و = را پاک کند و سه قسمت $A$، $B$ و $C$ را بهم بچسباند. حالا امین به سراغ تخته می‌آید و می‌خواهد از روی این رشته‌ی ارقام معادله را بازسازی کند.

در واقع امین با یک رشته $n$ رقمی از ارقام ۱ تا ۹ مواجه است و می‌خواهد این رشته را به سه بازه‌ی متوالی $A$، $B$ و $C$ تقسیم کنیم به طوری که معادله‌ی $A + B = C$ برقرار باشد. او از شما می‌خواهد بررسی کنید آیا انجام چنین افرازی ممکن است یا نه.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $t$ که تعداد سناریوها را نشان می‌دهد، داده می‌شود.

$1 \leq t \leq 100 \, 000$

در سطر اول هر سناریو، عدد صحیح و مثبت $n$ آمده که طول رشته را نشان می‌دهد.

$1 \leq n \leq 500 \, 000$

در سطر دوم هر سناریو، یک رشته از ارقام 1 تا 9 به نام $s$ داده می‌شود.

تضمین می‌شود که $\sum n \leq 1000\,000$ باشد.

خروجی🔗

در $t$ سطر برای هر سناریو، در صورتی که می‌توان چنین تقسیمی انجام داده YES و در غیر این صورت NO چاپ کنید.

مثال‌ها🔗

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

3
3
123
6
123456
11
14323242467

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

YES
NO
YES

معادله‌ی سناریو اول به صورت $1 + 2 = 3$ بوده است. بنابراین پاسخ YES می‌شود.

معادله‌ای برای سناریو دوم وجود ندارد

معادله‌ی سناریو سوم به صورت $143 + 2324 = 2467$ بوده است. بنابراین پاسخ YES می‌شود.

کد شما باید روی PostgreSQL قابل اجرا باشد.

در این سوال، دیتاست مربوط به ورزشکاران و مربیان المپیک ۲۰۱۶ در اختیار شما قرار گرفته است.

جزئیات پایگاه‌داده🔗

داده‌های اولیه را از این لینک دانلود کنید.

psql -U postgres -f /path/to/initial.sql

مطلوبات🔗

کوئری‌هایی بنویسید که خروجی‌های مطلوب زیر را به‌دست آورد (توجه کنید که هر کوئری نمره‌ای جداگانه دارد و اگر کوئری یک قسمت را نتوانستید بنویسید، کوئری‌هایی که حل کردید را بفرستید و کوئری آن قسمت را خالی بگذارید):

1. نام و تعداد مدال‌های سه ورزش برتر ایران، که در المپیک بیشترین مدال را آورده‌اند، به ترتیب نزولی ستون تعداد مدال بیابید.

2. نام و نوع مدالِ مدال‌آوران ایرانی حاضر در المپیک ۲۰۱۶ را به ترتیب مرغوبیت مدال و سپس صعودی نام به دست آورید.

3. نام ده مربی، تیم‌ مربوطه، مجموع تعداد مدال‌های طلا، نقره و برنز و همچنین مجموع امتیازی که ورزشکاران تحت هدایت آن مربی توانسته‌اند در کشتی مردان به دست آورند را در ابتدا به ترتیب نزولی مجموع امتیاز و در صورت برابر بودن به ترتیب صعودی نام مربی به دست آورید.

4. لیست ۲۲ تیم برتر که حداقل هفت ورزشکار زن آن‌ها موفق به کسب مدال شده‌اند، به همراه تعداد زنان و مردان مدال‌آور و نسبت تعداد زنان مدال‌آور به مردان مدال‌آور را نمایش دهید. نتایج بر حسب نزولی تعداد ورزشکاران زن، که مدال کسب کرده‌اند مرتب شود و در صورت تساوی، بر اساس نسبت زنان به مردان مدال‌آور به صورت نزولی مرتب گردد.

نکته: برای حل کامل سوال و دریافت امتیاز کوئری‌ها حتما توضیحات مربوط به هر کوئری را مطالعه بفرمایید.

آن‌چه باید آپلود کنید🔗

پس از پیاده‌سازی کوئری‌ها، آن را در قالب یک فایل با پسوند .sql آپلود کنید. کوئری‌های شما باید به صورت زیر باشد و هیچ گونه تغییری در کامنت‌ها ندهید.

-- Section1
   Your first query here
-- Section2
   Your second query here
-- Section3
   Your third query here
-- Section4
   Your fourth query here