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

زانا سالی یک بار یک جشن خاص برگزار می‌کند و تعدادی از دوستانش را به این جشن دعوت می‌کند. اسم این جشن «جشن هدیه‌ها» است! هر فردی که در این جشن شرکت می‌کند مقداری پول به همراه خود دارد و به تعدادی از دوستانش هدیه می‌دهد. روش هدیه دادن در این جشن کمی عجیب است! هر کدام از افراد یک لیست هدیه دارد که در آن لیست، نام تعدادی از دوستانش که در جشن شرکت کرده‌اند نوشته شده است و تمام پولی که همراه دارد را بین افراد این لیست به طور مساوی تقسیم می‌کند و این پول را به آنها هدیه می‌دهد! چون پول اعشاری (کوچکتر از یک) نداریم ، این تقسیم‌ها تقسیم صحیح هستند و اگر تقسیم پول بین اعضای لیست باقیمانده‌ای داشته باشد ، فرد هدیه دهنده این باقیمانده را برای خود نگه می‌دارد. به طور مثال اگر ساینا ۱۱ واحد پول داشته باشد و در لیست او فقط سه نفر باشند ، به هر کدام از آنها ۳ واحد پول میدهد و ۲ واحد از پول خود را برای خود نگه می‌دارد.

حال شما برنامه‌ای بنویسید که پس از گرفتن اسامی شرکت کنندگان، مقدار پول اولیه‌ی هر کدام و لیست هدیه هر کس، مشخص کند که هرکسی چقدر سود یا زیان کرده است!

ورودی🔗

• خط 1 : عدد n که برابر است با تعداد شرکت کنندگان در جشن.
• خط 2 تا n+1 : در هر خط اسم یکی از شرکت کنندگان.
• خط n+1 الی آخر : از این خط به بعد ورودی به n دسته تقسیم می‌شود که هرکدام مطابق زیر است: خط اول نام فردی که قرار است هدیه بدهد. در خط دوم دو عدد می‌آید: عدد اول مقدار پول آن فرد، عدد دوم (k) تعداد افراد موجود در لیست هدیه‌ی آن فرد در k خط بعدی در هر خط نام یکی از افراد موجود در لیست هدیه‌ی آن فرد.

می‌توانید فرض کنید نام هر دو نفر از افراد شرکت‌کننده در جشن متمایز است و $2 \leq n \leq 10$

خروجی🔗

در خروجی باید n خط چاپ کنید که در هر ابتدای هر خط نام هر شخص و بعد از آن مقدار سود او آورده شود. (اگر آن شخص ضرر کرده است، باید منفی مقدار ضرر چاپ شود.) ترتیب نام‌ها در خروجی باید مانند ترتیب نام‌ها در خطوط 2 تا n+1 ورودی باشد.

مثال🔗

ورودی نمونه🔗

5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0

خروجی نمونه🔗

dave 302
laura 66
owen -359
vick 141
amr -150

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

برنامه‌ای بنویسید که عدد $n$ را از ورودی گرفته و دو لوزی به قطر $n$ را در کنار هم با استفاده از کاراکتر * (مطابق خروجی نمونه) چاپ کند.

ورودی🔗

در یک خط عدد فرد $n$ به شما داده می‌شود. $1 \le n \le 19$

خروجی🔗

لوزی‌های کنار هم را در خروجی چاپ کنید.

مثال🔗

ورودی نمونه🔗

5

خروجی نمونه🔗

  *    *
 ***  ***
**********
 ***  ***
  *    *

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

برنامه‌ای بنویسید که به ترتیب دو عدد $n$ و $m$ را از کاربر بگیرد و حاصل مقدار زیر را به دست آورد:

$\sum_{i=-10}^{m} \sum_{j=1}^{n} \frac{(i+j)^3}{j^2}$

ورودی🔗

در خط اول عدد $n$ و در خط بعد عدد $m$ به شما داده می‌شود. $0 \le n , m \le 10$

خروجی🔗

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

مثال🔗

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

3
2

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

-2349

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

1
-10

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

-729

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

چندی پیش سازمان اطلاعاتی جمهوری کره(ساجک) اعلام کرد با همکاری SSIS(Sharif Security Intelligence Service سازمان اطلاعات امنیت شریف، سیستم انتقال پیام ETA(گروهک تروریستی باسکی) را رمزگشایی کرده است. سیستم انتقال اطلاعات در این شبکه به طرز قابل تحسینی تر و تمیز و شگفت آور بود. این گروه براي انتقال یک متن، پس از انتقال خود کلمات پیام (که شیوه ي آن در این مسئله بررسی نمی شود)، ترتیب و جایگشت آن ها را تبدیل به یک رشته ي باینري می کرد که در عملیاتی ترین شرایط هم به سادگی قابل انتقال بود. (در آخرین مورد درگیري، جاسوس محاصره شده با دنباله اي از شلیک کردن/ نکردن با تفنگ خالیش، لو رفتن عملیات را به اعضاي گروهک خبر داد) در حقیقت، رشته ي باینري حاوي اطلاعات فرایند مرتب سازي ادغامی بر روي جایگشت اولیه و اصلی کلمات بود که در نهایت کلمات را به حالت مرتب شده در می آورد. گیرنده ي پیام، باید با مهندسی معکوس جایگشت اولیه از کلمات که در حقیقت اصل پیغام بوده را بازیابی می کرد. نحوه ي تولید رشته در شبه کد زیر توضیح داده شده است:

mergeSort(array a)
    array b = a.subarray (0, a.size / 2),
    array c = a.subarray(a.size() / 2, a.size())
    mergeSort(b)
    mergeSort(c)
    a = merge(b, c)
merge(array a, array b)
    do the famous merge method. in each step:
    if the element is chosen from a
        add '0' to the binary string
    else
        add 1 to the binary string

فرستنده در ابتدا تابع mergeSort را روي کل آرایه ي رشته ها (که همان متن اصلیست) صدا می زد و در نهایت با کد بالا، رشته‌ي دودویی مورد نظر تولید و آماده ي ارسال می گردد. کد رمزنگار رشته ها را هم با شیوه ي خاصی مقایسه و نهایتا مرتب می کرد. به این ترتیب که اگر یکی از رشته ها شامل زیررشتهmoji بود، زود تر از رشته ي دیگر می آید. کوچکی و بزرگی حروف مهم نیست؛ MojI یا mOJI هم همین طور هستند (کسی هنوز معناي دقیق این کلمه ي محلی را نمی داند!). اگر هر دو رشته این زیر دنباله را داشتند یا هر دو نداشتند رشته ها معمولی (lexicographically) مقایسه می شوند؛ به همان سیستمی که در لغتنامه ها لغت ها را مرتب می کنند. سازمان امنیت اطلاعات دانشگاه، بعد از رسانه اي کردن این موضوع براي بازیابی اطلاعات آرشیو شده از مکالمات رمزي این گروه، از شما یک برنامه ي رمزگشایی تقاضا کرده. شما باید با دریافت یک پیام رمزنگاري شده، اصل متن را بازیابی کنید.

ورودی🔗

در ورودی ابتدا عدد n تعداد رشته ها ، و سپس به همین تعداد رشته، و سپس رشته‌ی دودویی که باید رمزگشایی شود می‌آید. رشته‌ها شامل حروف کوچک و بزرگ انگلیسی هستند و تعداد آن‌ها حداکثر ۱۰۰۰۰۰ تاست.

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

7
ACSmojicLm
mOJICVKnHLYJs
NHCpGb
uRcGD
ZxMOjIC
cUUbXcf
RdEt
01110010101010010111 

خروجی نمونه🔗

NHCpGb
ACSmojicLm
ZxMOjIC
mOJICVKnHLYJs
cUUbXcf
RdEt
uRcGD

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

شما بایستی از الگوریتم $A*$ برای حل مسئله راه‌بندان استفاده کنید.

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

هدف این است که با کمترین تعداد حرکت، خودروی قرمز رنگ را که همواره به صورت افقی و روبروی درب خروجی (که در ضلع شرقی پارکینگ قرار دارد) پارک شده است، از پارکینگ خارج نماییم.

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

ورودی🔗

ورودی شامل مشخصات پارکینگ و خودروهای پارک شده در آن به همراه موقعیت خودروی قرمز رنگ است. خط اول ورودی عدد $T$ است که تعداد پارکینگ‌ها را مشخص می‌کند. پس از آن مشخصات $T$ پارکینگ به صورت پشت سر هم در ورودی می‌آید. برای هر پارکینگ، در خط اول سه عدد $N$ ،$M$ و $V$ قرار دارد که به ترتیب تعداد سطرها و ستون‌های پارکینگ و تعداد خودروهای درون آن (شامل خودروی قرمز رنگ) را مشخص می‌کند. $V$ خط بعدی هر یک مشخصات یک خودرو را نشان می‌دهد. در هر خط، ابتدا دو عدد $R$ و $C$ قرار دارند که به ترتیب سطر و ستون قسمت بالا و سمت چپ خودرو را مشخص می‌کنند. در ادامه راستای خودرو با یک کاراکتر $h$ برای افقی و یا $v$ برای عمودی مشخص می‌شود. در انتهای خط نیز عدد $L$ طول خودرو را نشان می‌دهد.

لازم به ذکر است که خانه بالای سمت چپ در سطر ١ و ستون ١ قرار داشته و خانه پایین سمت راست در سطر $N$ و ستون $M$ قرار دارد. ضمناً اولین خط از لیست مشخصات خودروها متعلق به خودروی قرمز رنگ است. نمونه ورودی متناسب با شکل در زیر آمده است.

خروجی🔗

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

ورودی نمونه🔗

1
6 6 13
3 1 h 2
1 1 v 2
1 2 v 2
1 4 h 3
2 3 h 2
2 5 h 2
3 4 v 2
4 2 v 2
5 3 h 2
5 5 v 2
5 6 v 2
6 1 h 2
6 3 h 2

خروجی نمونه🔗

Test #1: 16

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

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

$ax+by+c=0$

برای $x$ یک کران پایین و یک کران بالا $(x_1,x_2)$ و برای $y$ هم یک کران پایین و یک کران بالا $(y_1,y_2)$ تعیین می‌کنند، سپس هر کدام اعدادی برای $a, b, c$ تعیین می‌کنند. بازیکنی که به ازای اعداد انتخابی‌اش تعداد جواب بیشتری برای معادله به دست آمد، برنده است و دیگری باید مشق‌هایش را بنویسد!

جواب‌های معادله‌ی بالا زوج مرتب‌های $(x,y)$ هستند که $x$ و $y$ عدد صحیح هستند و $x_1 < x < x_2$ و $y_1 < y < y_2$ برنامه‌ای بنویسید تا به آن‌ها کمک کند برنده را مشخص کنند.

ورودی🔗

در خط اول به ترتیب $x_1$ و $x_2$ و $y_1$ و $y_2$ داده می‌شود (این اعداد می‌توانند صحیح یا اعشاری باشند)، در خط دوم $a$ و $b$ و $c$ که بیژن تعیین می‌کند و در خط سوم $a$ و $b$ و $c$ که منیژه تعیین می‌کند داده می‌شود.

تمام اعداد ورودی از ۱۰۰۰ کوچک‌ترند.

خروجی🔗

در خط اول تعداد جواب‌هایی که بیژن به دست می‌آورد، در خط دوم تعداد جواب‌هایی که منیژه به دست می‌آورد ، در خط سوم اگر تعداد جواب‌ها مساوی بود Tie اگر بیژن برنده شده بود bizhan won و اگر منیژه برنده شده بود manizhe won چاپ شود.

مثال🔗

ورودی نمونه🔗

-1 1 0 5
1 0 0
5 4 3

خروجی نمونه🔗

4
0
bizhan won

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

شما عدد صحیح مثبت $m$ و نیز عدد صحیح نامنفی $s$ را در اختیار دارید ، وظیفه شما یافتن کوچکترین و بزرگترین عددی است که دارای طول $m$ و مجموع ارقام s باشد ، اعداد مورد نیاز باید صحیح ، غیر منفی ، در مبنای ۱۰ و با صفر آغاز نشود.

ورودی🔗

ورودی در یک خط دو عدد $m$ و $s$ که به صورت زیر هستند به شما داده می‌شود.

$1 \leq m \leq 100$$0 \leq s \leq 900$

خروجی🔗

در خروجی دو عدد صحیح غیرمنفی در یک خط چاپ میشود که به ترتیب کوچکترین عدد موجود و بزرگترین عدد موجود میباشد. اگر هیچ عددی با توجه به شرایط مطلبوب وجود نداشت خروجی باید به شکل $-1 \ -1$ باشد.

مثال🔗

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

2 15

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

69 96

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

3 0

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

-1 -1

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

برنامه‌ای بنویسید که 2 عدد صحیح $a$و $b$ را از ورودی گرفته و عدد $a$ را به مبنای $b$ ببرد.

عدد حاصل را $c$ می‌نامیم. در عدد $c$ سمت‌چپ‌ترین رقم(باارزشترین رقم) را در نظر گرفته و با شروع از این رقم، ارقام عدد را یک درمیان جمع می‌کنیم و مجموع را برابر $sum1$ قرار می‌دهیم. مجموع بقیه ارقام را $sum2$ می‌نامیم. اگر $sum1$ برابر با $sum2$ بود $Yes$ در غیراینصورت $No$ چاپ کنید.

ورودی🔗

در یک خط اعداد $a$ و $b$ به شما داده می‌شود.

$1 \le a \le 10^5$ $1 \le b \le 10$

خروجی🔗

پاسخ را در یک خط چاپ کنید.

مثال🔗

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

15 2

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

Yes

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

23 3

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

No

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

مثلث شکل زیر به مثلث خیام-پاسکال مشهور است. هر عضو این مثلث برابر با مجموع دو عضو بالایی آن در سطر بالاست؛ به عنوان مثال، در سطر چهارم، عدد 3 از مجموع اعداد 1 و 2 در سطر بالایی به دست آمده است.

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

ورودی🔗

در یک خط عدد $n$ به شما داده می‌شود. $1 \le n \le 10$

خروجی🔗

مثلث خیام را مانند خروجی نمونه چاپ کنید.

مثال🔗

ورودی نمونه🔗

6

خروجی نمونه🔗

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

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

حالا که وقت فرزاد بیشتر است، او می تواند بیشتر برای پروژه وقت بگذارد. از این رو فرزاد به دانیال گفت که در روز شنبه به مکان همیشگی خود بروند و بر روی صورت پروژه کار کنند. آنها در زمان ذکر شده به محل قرار آمدند و شروع به کار بر روی صورت پروژه کردند. اما طبق معمول سر اینکه کدام یک زمین بازی را درست کنند بین آنها دعوایی پیش آمد. بلاخره پس از مشاجره های طولانی، بازی زیر را اختراع کردند:

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

ورودی🔗

در اولین خط ورودی ابعاد ماتریس های ورودی و در ادامه دو ماتریس گرفته می‌شود. طول ماتریس ها از ۱۰ کوچکتر است.

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

2
2 1
4 -3
-1 0
5 -2

خروجی نمونه🔗

Farzad

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

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

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

ورودی🔗

در یک خط عدد $n$ به شما داده میشود. $1 \le n \le 10^6$

خروجی🔗

در تنها خط خروجی مختصات را جدا شده با فاصله چاپ کنید.

مثال🔗

ورودی نمونه🔗

14

خروجی نمونه🔗

4 -3

توضیح:

شماره‌ی یک در مبدأ مختصات قرار می‌گیرد و شماره دو در نقطه‌ی (1,0) و شماره‌ی سه در نقطه‌ی (1,1) و به همین ترتیب پیش‌می‌رود تا درنهایت، نقطه‌ی 14 در (3-,4) قرار می‌گیرد.

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

مسئله‌ای به شما داده شده است که بایستی به صورت یک مسئله $CSP$ آن را فرموله کرده و پیاده‌سازی نمایید. فرض کنید گرافی در اختیار داریم که گره‌های آن می‌توانند هر یک از اشکال مثلث، مربع، پنج ضلعی، شش ضلعی و یا دایره باشند. می‌خواهیم به هر گره از این گراف، یک عدد بین ١ تا ٩ نسبت دهیم به صورتی که شروط زیر برقرار باشند:

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

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

ورودی🔗

خط اول ورودی عدد $T$ است که تعداد تست‌ها را نشان می‌دهند. خط اول هر تست، شامل اعداد $V$ و $E$ است که اولی نشان دهنده تعداد گره‌ها و دومی نشان دهنده تعداد یال‌های گراف است.

در خط بعد $V$ کاراکتر از بین یکی ͬاز کاراکترهای Tبرای مثلث، S برای مربع، P برای پنج ضلعی، H برای شش ضلعی و C برای دایره، که با یک فاصله از هم جدا شده‌اند می‌آید که کاراکتر $i$ام، شکل گره $i$ام را مشخص می‌کند (0 ≥ $i$).

پس از آن، $E$ خط به صورت ‍‍i j می‌آید. که نشان می‌دهد یالی میان گره $i$ام و گره $j$ام وجود دارد. نمونه ورودی متناظر با شکل در ادامه آمده است.

خروجی🔗

به ازای هر تست، یک خط خروجی می‌آید که شامل $V$ عدد بین ١ تا ٩ است که با فاصله از هم جدا شده اند و عدد $i$ام، مقدار منتسب به گره $i$ام را نشان می‌دهد.

مثال🔗

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

1
9 8
C P H S S H H T C
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8

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

9 1 7 6 8 3 5 2 4

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

حالا که امتحان های میان ترم فرزاد تمام شده است و زمان بیشتری دارد، او به فکر کار افتاده است. پس از جستجوهای فراوان نهایتاً در شرکت دانیال اینا کاری به او داده شد. کار او به این صورت است که به او چند عدد صحیح می دهند که میزان سود یا ضرر شرکت در روزهای متوالی است. (واحد اعداد میلیون تومان است.) او باید بگوید بیشترین سود شرکت چقدر بوده است. مثلاً در روز اول به او این عددها را دادند: $1,2,-5,4,-3,2$.

واضح است که بیشترین سود شرکت در چهارمین روز بوده است، که برابر ۴ میلیون تومان است. چون مجموع اعضای هر زیر آرایه دیگری از این آرایه داده شده، مقداری کوچک تر از ۴ دارد. دقت کنید که اگر همه اعداد، منفی (ضرر) بودند، میزان سود برابر ۰ است. برنامه‌ای بنویسید که فرزاد به وسیله آن بدون محاسبات ذهنی، کار خود را انجام دهد.

ورودی🔗

در خط اول ورودی تعداد روزهایی که قرار است سود و ضرر و در ادامه آرایه‌ی سود و ضررها در این روزها گرفته می‌شود.

$1 \le n \le 100$

خروجی🔗

در خروجی شما باید میزان بیشترین سود را بیان کنید. به ورودی و خروجی نمونه دقت کنید.

مثال🔗

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

12
7 -1 -2 1 5 -11 9 1 4 -1 3 -10

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

16

توضیح خروجی: بیشترین سود شرکت در روزهای ۷ تا ۱۱ است که مجموع اعداد شماره ۷ تا ۱۱ برابر ‍۱۶ است.

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

5
-5 -2 -9 -1 -3

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

0

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

در کشوری رییس جمهور به این نحو انتخاب می‌شود:

اگر n نفر کاندید شده باشند $(2 \leq n)$، ابتدا طی مراسمی با قرعه کشی به هر کاندیدی یک عدد از ۱ تا n تعلق می‌گیرد. کاندیدها به ترتیب شماره‌هایشان، دور میزی می‌نشینند و یکی در میان با شروع از شماره‌ی ۲ حذف می‌شوند.

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

ورودی🔗

در تنها خط ورودی عدد $n$ آمده است. $2 \leq n \leq 100$

خروجی🔗

در تنها خط خروجی شماره‌ی کاندیدا‌ پیروز را چاپ کنید.

مثال🔗

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

12

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

9

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

16

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

1

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

از آن‌جایی که دترمینان یک ماتریس بسیار مفید و کاربردیست!

برنامه‌ای بنویسید که ابتدا $n$ و سپس درایه‌های یک ماتریس $n \times n$ را بگیرد. و با کمک تابع بازگشتی دترمینان ماتریس را محاسبه و با دقت دو رقم اعشار چاپ کند.

ورودی🔗

در خط اول ورودی عدد $n$ آمده است. در $n$ خط بعد در هر خط $n$ عدد گویا آمده که درایه‌های ماتریس را مشخص می‌کنند.( هر درایه‌ی ماتریس عددی گویاست که قدرمطلق آن از ۱۰۰ کمتر است.) $1 \leq n \leq 30$

خروجی🔗

در خروجی دترمینان ماتریس داده شده را تا ۲ رقم اعشار چاپ کنید.

مثال🔗

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

3
1.0 0.0 0.0
2.0 3.0 4.0
5.0 6.0 7.0

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

-3.00

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

2
1.1 2.2
3.3 4.4

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

-2.42

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

سرانجام هری‌پاتر توانست طلسم شکست دادن دشمن بزرگ خود مالفوی را ابداع کند! هری یک جفت دستبند قدرت دایره‌ای ساخته که روی مچ دست‌های راست و چپش بسته می‌شود. او روی هر دستبند دنباله‌ای از حروف جادویی نوشته است که هر حرف فعال قدرت او را تقریبا به اندازه یک بید کتک‌زن افزایش می‌دهد! با این حال یک مشکل وجود دارد. دستبندها فقط زمانی کار می‌کنند که زیردنباله حروف فعال شده روی هر دو دستبند یکسان باشد. برای مثال در شکل زیر یک جفت دستبند داده شده که حروف دو رشته $ababdcbcc$ و $aabdccccbd$ به عنوان حروف جادویی روی آنها قرار گرفته است که یک فعال‌سازی بهینه از این حروف به هری قدرتی به اندازه ۱۴ بید کتک‌زن می‌دهد.

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

ورودی🔗

فایل ورودی حداکثر شامل ۱۰۰ نمونه ورودی است. (حداکثر شامل ۵ نمونه بزرگ) هر نمونه یک خط شامل یک جفت رشته که با فاصله جدا شده اند و مربوط به همان دنباله حروف روی دستبندهای قدرت چپ و راست هری است (به ترتیب) می باشد و هر رشته تنها از حروف کوچک تشکیل خواهد شد. طول هر رشته ورودی بین $1$ تا $100$ کاراکتر است به جز در نمونه های بزرگ که طول هر رشته ورودی بین $1$ تا $1500$ کاراکتر می باشد.

خروجی🔗

حداکثر قدرتی که هری با فعال کردن حروف روی دستبندها می تواند برسد (بر حسب واحد بید کتک‌زن) را چاپ کنید.

مثال🔗

ورودی نمونه🔗

ababdcbcc aabdccccbd
harrypotter plorppothaa
potterharry plorppothaa

خروجی نمونه🔗

14
12
12

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

در یک صبح زیبای تابستانی اتفاق وحشتناکی در پردازنده مرکزی افتاد، یک ویروس آب زیرکاه به نام مگابایت به طریقی به حافظه خواهرش به نام هگزادسیمال (که کمتر از او آب زیرکاه نبود) دسترسی پیدا کرد. او برای به دست آوردن کنترل کامل بر خواهرش $n$ عدد مختلف طبیعی از ۱ تا $n$ را $load$ کرد .

ولی نقشه اش با شکست مواجه شد. علتش ساده بود: هگزادسیمال هر اطلاعاتی را درک نمی کرد، بجز اعدادی که در مبنای ۲ نوشته شده اند. یعنی اگر عددی در مبنای ۱۰ شامل رقمی به جز ۰ و ۱ باشد، در حافظه قرار نمی گیرد. اکنون مگابایت می‌خواهد بداند که چه تعداد از عددها به طور موفقیت آمیز $load$ شده‌اند .

ورودی🔗

در یک خط عدد $n$ به شما داده می‌شود.

$1 \leq n \leq 10^{9}$

خروجی🔗

در یک خط پاسخ مسئله را چاپ کنید.

مثال🔗

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

10

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

2

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

پس از این که TA سخت گیر، کوییز طاقت فرسایی از دانشجوها گرفت، دانشجوها با یکدیگر دست به یکی کردند تا از او انتقام بگیرند.

بدین منظور بازی ای ترتیب دادند و از TA خواستند که با آن ها بازی کند. در صورت باختن TA باید ۱۰ نمره به همه اضافه و در صورت بردن او ۱۰ نمره از همه کم می شود.

در این بازی دانشجویان یک جدول $3 \times n$ به همراه تعداد نامحدودی دومینو (موزاییک هایی که هر کدام دو خانه از جدول را می‌پوشانند.) به TA می دهند و TA باید تعداد روش هایی که می تواند به وسیله ی این دومینو ها، جدول را بپوشاند به دانشجوها تحویل دهد. در صورت درست بودن جواب، TA برنده و در غیر این صورت TA بازنده می‌شود.

یکی از دانشجوهای زرنگ(!) برنامه ای نوشته است که این تعداد روش ها را محاسبه می کند و آن را به TA داده است. ولی برای این که TA ببازد، در آخر دو برابر جواب اصلی را در خروجی چاپ می کند.

این برنامه را بازنویسی کنید.

ورودی🔗

در یک خط عدد $n$ به شما داده می‌شود.

$1\le n \le 25$

خروجی🔗

در یک خط پاسخ مسئله را چاپ کنید.

مثال🔗

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

4

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

22

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

10

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

1142

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

مبین خیلی عیدی دوست دارد! در یک مهمانی عمویش به او جدولی داد و گفت « هر چقدر EYDI در این جدول پیدا کنی به همان تعداد سکه به تو عیدی می‌دهم».

در هر خانه‌ی جدول یکی از حروف E, Y, D, I نوشته شده است. روش بازی به صورت زیر است:

• مبین در ابتدا در خانه شامل حرف E است.

• خانه‌ای شامل حرف Y پیدا می‌کند که مجاور با خانه‌ی قبلی باشد.

• خانه‌ای شامل حرف D پیدا می‌کند که مجاور با خانه‌ی قبلی باشد.

• خانه‌ای شامل حرف I پیدا می‌کند که مجاور با خانه‌ی قبلی باشد.

• یک سکه به دست می‌آورد!

• خانه‌ای شامل حرف E پیدا می‌کند که مجاور با خانه‌ی قبلی باشد. سپس به گام دوم برمی‌گردد.

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

ورودی🔗

در خط اول ورودی دو عدد nو m می‌آیند که به ترتیب تعداد سطرها و تعداد ستون‌های جدول هستند. n خط بعدی هر کدام شامل m حرف است، به این صورت که حرف jام از iامین خط ($1 \leq j \leq m$ و $1 \leq i \leq n$) حرفی است که در خانه‌ی (i,j) از جدول قرار دارد.

$1 \le n, m \le 600$

خروجی🔗

اگر مبین نمی‌تواند سکه‌ای به دست بیاورد عبارت !Poor Mobin را چاپ کنید. اگر مبین می‌تواند نامتناهی سکه به دست بیاورد عبارت !Poor Uncle را چاپ نمایید. در غیر این صورت حداکثر تعداد سکه‌هایی را بنویسید که مبین می‌تواند به دست بیاورد.

مثال🔗

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

1 2
EY

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

Poor Mobin!

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

2 2
DI
YE

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

Poor Uncle!

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

5 5
EYDIE
EYDIY
EYDID
EEDII
IIDYE

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

4

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

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

او گفت که می‌تواند تعدادی ستاره به Quera بدهد که دیگر نیازی به برگزاری مسابقه نباشد و Quera نیز طبعاً از این پیشنهاد بسیار استقبال کرد!

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

شما باید برنامه‌ای بنویسید که با ورودی گرفتن این عکس‌ها، ستاره‌های داخل آن‌ را بیابد!

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

برنامه‌ی شما باید پس از دریافت عکس (توصیف دقیق فرمت تست‌ها را می‌توانید در بخش "ورودی" بیابید) تعداد ستاره‌هایی که پیدا کرده‌است را چاپ کند و سپس مختصات حداقل یک نقطه از هریک از این ستارگان را در خروجی بنویسد. سپس سیستم تعداد ستاره‌هایی که برنامه‌ی شما یافته‌ را بررسی می‌کند. اگر کمتر از ۷۵٪ تعدادی که برنامه‌ی شما ادعا کرده‌است ستاره شامل نقاط خروجی شما وجود داشت، برنامه‌ی شما نمره‌ی آن تست را دریافت نمی‌کند.

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

در این مثال تنها ۵ ستاره وجود دارد که شما باید آن‌ها را بیابید.

یا برای مثال، در عکس زیر (که بازهم بخشی از یکی از عکس‌های تست‌ها است) ۱۲ ستاره وجود دارد که شما باید آن‌ها را بیابید:

(ورودی مثال این دو عکس و یک خروجی معتبرشان در نمونه‌های سوال آمده‌اند.)

دقت کنید که لازم نیست تمام ستارگان با شرایط گفته‌شده را بیابید؛ شما کافیست به تعداد $expected$ ستاره با این شرایط پیدا کنید و می‌توانید تا $\frac 4 3$ تعداد کل ستارگان با شرایط گفته شده نقطه خروجی دهید. تضمین می‌شود بیش از $\lceil \frac 5 4 \rceil$ مقدار $expected$ در هر تست، ستاره با شرایط گفته شده یافت شود.

جهت تشخیص درست ستاره‌ها، تلاش کنید نقطه‌ای که در ستاره‌ی معرفی شده ارائه می‌دهید در گوشه‌های آن نباشد. (بعنوان مثال، می‌توانید مرکز ثقل شکل ستاره یافت‌شده را خروجی دهید!)

ورودی🔗

در سطر اول ورودی، سه عدد $h$ و $w$ و $expected$ آمده‌است که به ترتیب نمایانگر مقدار ارتفاع و عرض عکس ورودی و تعداد ستاره‌هایی که باید یافت شوند هستند.

$150 \le w, h \le 800$

سپس در $h$ سطر بعدی، هر سطر رنگ $w$ نقطه‌ از تصویر توصیف شده‌است. توصیف هر نقطه بصورت $(r,\ g,\ b)$ می‌باشد که نمایانگر رنگ این نقطه در صورت نمایش بصورت RGB است. توصیف‌ نقاط با فاصله (space) از هم جدا شده‌اند.

تضمین می‌شود در هریک از تست‌های داده شده، حداکثر ۵۰ ستاره با شرایط گفته شده وجود دارد.

به ورودی‌های نمونه دقت کنید!

خروجی🔗

در سطر اول خروجی یک عدد $k$ چاپ کنید که نمایانگر تعداد ستاره‌هایی است که در عکس یافت شده‌اند. سپس در هریک از $k$ سطر بعدی، مختصات یکی از نقاط یکی از ستاره‌های یافت شده را خروجی دهید. هر مختصات باید بصورت $(h', w')$ باشد که یعنی این نقطه در سطر $h'$ توصیف عکس در ورودی سوال، نقطه‌ی $w'$امی بوده‌است که توصیف شده‌است.

مثال🔗

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

ورودی نمونه‌را می‌توانید در اینجا ببینید.

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

5
13 23
78 139
25 60
67 61
103 130

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

ورودی نمونه‌را می‌توانید در اینجا ببینید.

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

12
83 160
22 147
88 137
175 229
15 290
144 172
136 119
147 179
47 98
111 97
163 284
154 278