اعداد فیثاغورثی

اعداد فیثاغورثی:🔗

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

مثال:

خروجی	ورودی
YES	5 4 3
NO	8 7 10

ماکزیمم

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

مثال🔗

ورودی نمونه

4
1 5 6 2

خروجی نمونه

فرزام از بچگی به گل و گیاه علاقه داشت و به همین سبب حالا که بزرگ شده است، در باغچه حیات خود گلدان‌های متعدد و زیادی دارد. او سال ها پیش که می‌خواست گل‌های خود را در این گلدان‌ها بکارد، در هر یک از گلدان‌ها مقدار مشخصی خاک ریخت اما اکنون پس از گذشت چند سال، مقدار خاک مورد نیاز این گل‌ها تغییر کرده است. باتوجه به متفاوت بودن گل‌های گلدان‌های مختلف، مقدار خاک مورد نیاز آن‌ها هم متفاوت است. برخی از گل‌ها در طی این چند سال نیازشان به خاک افزایش یافته‌اند، اما برخی نیز ممکن است نیاز آن‌ها کاهش یافته باشد. فرض کنید، گلدان‌ها با شماره‌های ۱ تا $N$ که $1 \leq N \leq 100$ به ترتیب در یک سطر قرار گرفته باشند و مقدار اولیه خاک هر گلدان را به ترتیب $A_i$ می‌نامیم. هم چینن مقدار خاک جدید مورد نیاز هر گلدان را به ترتیب $B_i$ می‌نامیم. فرض کنید خاک موجود در گلدان‌ها در طی این چند سال تغییری نکرده باشد و همه $A_i$ و $B_i$ها در بازه صفر تا ۱۰ باشند. می‌دانیم به هر یک از سه طریق زیر می‌توان مقدار خاک یک گلدان را تغییر داد. + می‌تواند ۱ واحد خاک بخرد و آن را در هریک ار گلدان‌ها که بخواهد بریزد. هزینه این عمل به طور ثابت برابر $X$ است. + می‌تواند ۱ واحد از خاک یک گلدان دلخواه را با هزینه ثابت $Y$ از گلدان مورد نظر برداشته و دور بریزد. + می‌تواند یک واحد خاک را از گلدان $i$ به گلدان $j$ منتقل کند. هزینه این عمل برابر $Z \times |i-j|$ خواهد بود. می‌خواهیم خاک هر گلدان مقدار مورد نیاز جدید شود. حداقل هزینه مورد نیاز برای انجام این کار با توجه به مقادیر ورودی چقدر است؟ ## ورودی در خط اول ورودی ۴ عدد $N, X, Y, Z$ می‌آیندکه با یک فاصله از هم جدا شده‌اند. $$1 \leq X,Y,Z \leq 1000$$ در خط‌های $2, ..., N+1$ در هر خط دو عدد می‌آید به طوری که در خط $i+1$ام، به ترتیب دو عدد $A_i$ و $B_i$ می‌آیند که با یک فاصله از هم جدا شده‌اند. ## خروجی در تنها سطر خروجی حداقل هزینه‌ای که با آن می‌توان به حالت مورد نظر رسید را چاپ کنید. ## مثال ورودی نمونه ``` 4 10 200 1 1 4 2 3 3 2 4 0 ``` خروجی نمونه ``` 210 ```

خاک برداری

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

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

فرض کنید، گلدان‌ها با شماره‌های ۱ تا $N$ که $1 \leq N \leq 100$ به ترتیب در یک سطر قرار گرفته باشند و مقدار اولیه خاک هر گلدان را به ترتیب $A_i$ می‌نامیم. هم چینن مقدار خاک جدید مورد نیاز هر گلدان را به ترتیب $B_i$ می‌نامیم. فرض کنید خاک موجود در گلدان‌ها در طی این چند سال تغییری نکرده باشد و همه $A_i$ و $B_i$ ها در بازه صفر تا ۱۰ باشند.

می‌دانیم به هر یک از سه طریق زیر می‌توان مقدار خاک یک گلدان را تغییر داد.

می‌تواند ۱ واحد خاک بخرد و آن را در هریک ار گلدان‌ها که بخواهد بریزد. هزینه این عمل به طور ثابت برابر $X$ است.
می‌تواند ۱ واحد از خاک یک گلدان دلخواه را با هزینه ثابت $Y$ از گلدان مورد نظر برداشته و دور بریزد.
می‌تواند یک واحد خاک را از گلدان $i$ به گلدان $j$ منتقل کند. هزینه این عمل برابر $Z \times |i-j|$ خواهد بود.

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

ورودی🔗

در خط اول ورودی ۴ عدد $N, X, Y, Z$ می‌آیندکه با یک فاصله از هم جدا شده‌اند.

$1 \leq X,Y,Z \leq 1000$

در خط‌های $2, ..., N+1$ در هر خط دو عدد می‌آید به طوری که در خط $i+1$ ام، به ترتیب دو عدد $A_i$ و $B_i$ می‌آیند که با یک فاصله از هم جدا شده‌اند.

خروجی🔗

در تنها سطر خروجی حداقل هزینه‌ای که با آن می‌توان به حالت مورد نظر رسید را چاپ کنید.

مثال🔗

ورودی نمونه

خروجی نمونه

جمع اول‌ها

جمع اول‌ها:🔗

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

مثال:🔗

ورودی نمونه 1

خروجی نمونه 1

31 + 3 = 34
29 + 5 = 34
23 + 11 = 34
17 + 17 = 34

ورودی نمونه 2

خروجی نمونه 2

not found

حل معادله درجه دوم

تابعی بنویسید که با گرفتن ضرایب a,b,c,n به ترتیب، معادله‌ی درجه دو $ax^2 + bx + c = 0$ را حل کند. در این تابع n برابر 0 یا 1 است که در صورت وجود دو حواب متمایز برای معادله، اگر $n = 0$ باشد، جواب کوچکتر و اگر $n = 1$ باشد، جواب بزرگتر را خروجی بدهد و درصورت یکتابودن جواب، $n =0 ,\, n=1$ تفاوتی ندارد؛ سپس به کمک تابع برنامه ای بنویسید که با گرفتن a,b,c,n از کاربر جواب معادله را چاپ کند و در صورت موهومی بودن جواب Complex number را نمایش دهد. خروجی‌ها تا 2 رقم اعشار چاپ شود. برای به‌توان رساندن باید از تابع (pow(i,n استفاده کنید. برای این کار لازم است در ابتدای برنامه، math.h را include کنید.

مثال🔗

ورودی نمونه ۱

2 2 -4 0

خروجی نمونه ۱

-2.00

ورودی نمونه ۲

0 2 -1 1

خروجی نمونه ۲

0.50

ورودی نمونه ۳

0.2 0 0.35 0

خروجی نمونه ۳

Complex number

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کیانوش متقاضی عضویت در سازمان OC است. در روز دوم مصاحبه، سازمان خلاقیت او را مورد بررسی قرار داده است. روز دوم مسابقه کیانوش به یک مزرعه برده میشود. این مزرعه از بالا به شکل جدولی با $n$ سطر و $n$ ستون قابل رویت است که روی برخی از خانه‌های این جدول تعدادی بسته‌ی کاه قرار گرفته است. کیانوش باید با جابجاکردن این بسته‌های کاه بین خانه‌های جدول، شکلی خلاقانه روی زمین طراحی کند. کیانوش تصمیم گرفت که طوری بسته‌ها را جابجا کند که آن‌ها به شکل زیرمستطیلی با ابعاد دلخواه از جدول قرار بگیرند. روی هر خانه‌ی آن زیرمستطیل باید دقیقاً یک بسته کاه قرارگیرد و همچنین روی خانه‌‌های خارج از این مستطیل باید بسته‌ی کاهی نباشد. کیانوش میتواند در یک حرکت یک بسته‌ی کاه را از روی یک خانه‌ی جدول برداشته و روی خانه‌ی دیگری از آن بگذارد. او قصد دارد از این مستطیل بعنوان پس‌زمینه استفاده کند و با چوب و سنگ‌هایی که پیدا میکند علامت حق تکثیر (یا copyright) را روی آن حک کند. حال با ورودی گرفتن $n$ و موقعیت بسته‌های کاه، بگویید کیانوش حداقل چند حرکت لازم دارد تا به شکل دلخواهش برسد. تضمین میشود که در ورودی داده شده، کیانوش میتواند شکل دلخواهش را طراحی کند. # ورودی سطر اول ورودی شامل دو عدد $n$ و $m$ است که نمایانگر طول مزرعه و تعداد بسته‌های کاه است. سپس در هریک از $m$ سطر بعدی دو عدد آمده است که به ترتیب بیانگر شماره سطر و ستون یک بسته‌ی کاه است. سطر‌های جدول را از بالا به پایین و ستون‌‌های آن را از چپ به راست با اعداد ۱ تا $n$ شماره گذاری میکنیم. توجه داشته باشید که ممکن است دو بسته‌ی کاه در یک خانه از جدول باشند. $$1 \le n \le 100$$ $$1 \le m \le n^2$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر حداقل تعداد جابجایی‌های لازم در شکل داده‌شده است. # ورودی نمونه ۱ ``` 3 2 2 2 2 2 ``` # خروجی نمونه ۱ ``` 1 ``` # ورودی نمونه ۲ ``` 4 6 1 1 1 2 1 3 2 1 4 3 4 4 ``` # خروجی نمونه ۲ ``` 2 ``` در این مثال کافیست دو بسته‌ی کاه انتهایی را به ستون‌های دوم و سوم از سطر دوم انتقال دهیم بطوری که بسته‌های کاه مستطیلی با ۲ سطر و ۳ ستون در جدول تشکیل دهند.

علامت حق تکثیر

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

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

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

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

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

ورودی🔗

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

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

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

$1 \le n \le 100$ $1 \le m \le n^2$

خروجی🔗

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

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

3 2
2 2
2 2

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

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

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

در این مثال کافیست دو بسته‌ی کاه انتهایی را به ستون‌های دوم و سوم از سطر دوم انتقال دهیم بطوری که بسته‌های کاه مستطیلی با ۲ سطر و ۳ ستون در جدول تشکیل دهند.

اعداد هگزا دسیمال

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

ورودی🔗

ورودی تنها شامل عدد n است.

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

خروجی🔗

خروجی تنها عددی است که پاسخ مسئله باشد!

مثال:🔗

خروجی	ورودی
2	10

کامل بودن یا نبودن

کامل بودن یا نبودن:🔗

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

مثال:

خروجی	ورودی
NO	27
YES	6

سازمان اطلاعات کشور ایکو، برای جمع‌آوری اطلاعات، $n$ جاسوس به کشور بیکو فرستاده است. این جاسوس‌ها با اعداد 1 تا $n$ شماره‌گذاری شده‌اند و برای ارتباط با یکدیگر از تلفن‌های همراه مخصوصی استفاده می‌کنند. به دلیل مسائل امنیتی، برقراری ارتباط تنها بین $n-1$ جفت از جاسوس‌ها مجاز است. هم‌چنین می‌دانیم گرافی که رأس‌های آن جاسوس‌ها باشند و یال‌های آن، جفت جاسوس‌هایی باشند که می‌توانند با یکدیگر ارتباط تلفنی برقرار کنند، یک درخت است. در این ارتباط‌ ها، هر جاسوس یک کد دارد که در برقراری ارتباط با دیگر جاسوس‌ها از آن استفاده می کند. (دقت کنید که کد جاسوس $i$ ($1 \leq i \leq n$) می‌تواند $i$ نباشد.) کد جاسوس‌ها یک عدد طبیعی از 1 تا $n$ است و هم‌چنین کد هر دو جاسوسی متفاوت است. به خاطر دلایل نامعلوم، سازمان اطلاعات برای هر جفت جاسوس $(i,j)$ که می‌توانند باهم ارتباط برقرار کنند، مشخص کرده است که کد کدام یک از دو جاسوس باید کوچکتر باشد. برنامه‌ای بنویسید که با گرفتن ارتباط‌های مجاز بین جاسوس‌ها و این‌که در هر ارتباط مجاز، کد کدام یک از آن‌ها باید کمتر باشد، تعداد روش‌های اختصاص‌دهی کد به جاسوس‌ها را محاسبه‌کند. با توجه به این‌که این عدد ممکن است بزرگ باشد، برنامه‌ی شما باید باقی‌مانده این عدد بر $10^9 + 7$ را به عنوان جواب در نظربگیرد. ## ورودی سطر اول ورودی شامل عدد طبیعی، $n$، تعداد جاسوس‌ها است. در هر یک از $n-1$ سطر بعدی به ترتیب دو عدد $u$ و $v$ آمده است که به معنای این است که جاسوس $u$ و $v$ می‌توانند باهم ارتباط تلفنی برقرار کنند و هم‌چنین کد جاسوس $u$ باید کمتر از کد جاسوس $v$ باشد. ## خروجی در تنها سطر خروجی، باقی‌مانده‌ی تعداد روش‌های کدگذاری جاسوس‌ها بر $10^9 + 7$ را چاپ کنید. ## محدودیت‌ها + $1 \leq n \leq 3000$ + $u \ne v , 1 \leq u,v \leq n$ ## مثال ورودی نمونه ۱ ``` 3 1 2 2 3 ``` خروجی نمونه ۱ ``` 1 ``` ورودی نمونه ۲ ``` 4 1 4 2 4 3 4 ``` خروجی نمونه ۲ ``` 6 ```

جاسوس‌ها

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

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

برنامه‌ای بنویسید که با گرفتن ارتباط‌های مجاز بین جاسوس‌ها و این‌که در هر ارتباط مجاز، کد کدام یک از آن‌ها باید کمتر باشد، تعداد روش‌های اختصاص‌دهی کد به جاسوس‌ها را محاسبه‌کند. با توجه به این‌که این عدد ممکن است بزرگ باشد، برنامه‌ی شما باید باقی‌مانده این عدد بر $10^9 + 7$ را به عنوان جواب در نظربگیرد.

ورودی🔗

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

در هر یک از $n-1$ سطر بعدی به ترتیب دو عدد $u$ و $v$ آمده است که به معنای این است که جاسوس $u$ و $v$ می‌توانند باهم ارتباط تلفنی برقرار کنند و هم‌چنین کد جاسوس $u$ باید کمتر از کد جاسوس $v$ باشد.

خروجی🔗

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

محدودیت‌ها🔗

$1 \leq n \leq 3000$
$u \ne v , 1 \leq u,v \leq n$

مثال🔗

ورودی نمونه ۱

3
1 2
2 3

خروجی نمونه ۱

ورودی نمونه ۲

خروجی نمونه ۲

فاکتوریل

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

مثال🔗

ورودی نمونه

خروجی نمونه

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

تقاطع‌های حیاتی

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

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

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

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

ورودی🔗

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

سپس در $i$ مین سطر از هریک از $m$ سطر بعدی، دو عدد $u_i$ و $v_i$ آمده است که یعنی خیابانی از تقاطع شماره $u_i$ به سمت تقاطع شماره $v_i$ وجود دارد. میتوانید فرض کنید بین هردو تقاطع حداکثر یک خیابان در یک جهت وجود دارد.

$1 \le n \le 5000$

$n - 1 \le m \le 2 \times 10^5$

خروجی🔗

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

ورودی نمونه🔗

خروجی نمونه🔗

2
1 2

در این مثال با انسداد تقاطع شماره ۱ از شهرداری به هیچیک از دیگر تقاطع‌ها نمیتوان رفت. درصورت انسداد تقاطع ۲ هم نمیتوان به تقاطع ۳ رسید.

توان دو

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

مثال🔗

ورودی نمونه ۱

خروجی نمونه ۱

ورودی نمونه ۲

خروجی نمونه ۲

دترمینان ماتریس‌ها

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

برنامه‌ای بنویسید که ابتدا $n$ و سپس درایه‌های یک ماتریس $n \times n$ را بگیرد $(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

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کیانوش متقاضی عضویت در سازمان OC است. در روز اول مصاحبه، سازمان پشتکار او را مورد بررسی قرار داده است. سوال‌های روز اول مصاحبه‌ی کیانوش، اینچنین بودند: عبارتی شامل دو عدد بزرگ و یک عملیات به شما میدهند. اگر عملیات جمع بود، باید مجموع آن دو عدد را خروجی دهید و اگر عملیات ضرب بود، باید ضرب آن دو را خروجی دهید... کیانوش با شنیدن این جملات، بدون فرض اضافه‌ای با عزمی راسخ شروع به پاسخ دادن به سوالات کرد و وقت بسیاری روی آن گذاشت؛ غافل از اینکه در ادامه‌ی صورت سوال آمده است که اعداد داده شده حتماُ توانی از ۱۰ هستند. (میتوان آن ها را بصورت $10^x$ نوشت که $x$ یک عدد صحیح نامنفی است.) کیانوش پس از این مصاحبه درخواست کرده است که به شما بگوییم برنامه‌ای بنویسید که با ورودی گرفتن اعداد و عملگر، پاسخ مسئله را خروجی دهد. # ورودی ورودی شامل سه خط میشود. در خط اول و سوم ورودی هریک شامل یک عدد هستند. تضمین میشود هریک از این اعداد را میتوان بصورت $10^x$ نوشت که $x$ عددی صحیح بین ۰ تا ۱۰۰ است. خط دوم ورودی شامل یک کاراکتر است. اگر آن کاراکتر + بود شما باید مجموع اعداد داده شده را خروجی دهید و اگر * بود باید ضرب آن ها را خروجی دهید. # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر پاسخ عملیات داده‌شده است. # ورودی نمونه ۱ ``` 10 + 100 ``` # خروجی نمونه ۱ ``` 110 ``` # ورودی نمونه ۲ ``` 10000 * 10 ``` # خروجی نمونه ۲ ``` 100000 ```

جمع بزرگان

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

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

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

عبارتی شامل دو عدد بزرگ و یک عملیات به شما میدهند. اگر عملیات جمع بود، باید مجموع آن دو عدد را خروجی دهید و اگر عملیات ضرب بود، باید ضرب آن دو را خروجی دهید...

کیانوش با شنیدن این جملات، بدون فرض اضافه‌ای با عزمی راسخ شروع به پاسخ دادن به سوالات کرد و وقت بسیاری روی آن گذاشت؛ غافل از اینکه در ادامه‌ی صورت سوال آمده است که اعداد داده شده حتماُ توانی از ۱۰ هستند. (میتوان آن ها را بصورت $10^x$ نوشت که $x$ یک عدد صحیح نامنفی است.)

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

ورودی🔗

ورودی شامل سه خط میشود. در خط اول و سوم ورودی هریک شامل یک عدد هستند. تضمین میشود هریک از این اعداد را میتوان بصورت $10^x$ نوشت که $x$ عددی صحیح بین ۰ تا ۱۰۰ است.

خط دوم ورودی شامل یک کاراکتر است. اگر آن کاراکتر + بود شما باید مجموع اعداد داده شده را خروجی دهید و اگر * بود باید ضرب آن ها را خروجی دهید.

خروجی🔗

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

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

10
+
100

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

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

10000
*
10

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

چاپ مربع

برنامه‌ای بنویسید که عدد n را از ورودی دریافت کرده و سپس یک مربع توخالی به طول و عرض n با ستاره چاپ کند.

مثال🔗

ورودی نمونه

خروجی نمونه

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

ژله‌ی ایرانی

افراسیاب $n$ ژله‌ که به شکل مکعب‌های $1 \times 1 \times1$ هستند با شماره‌های ۱ تا $n$ خریده است. ژله $i$ ام دارای وزن $W_i$ کیلوگرم است. می‌دانیم یک ژله قابلیت تحمل وزن تا حداکثر $C_i$ کیلوگرم را دارد. می‌خواهیم برای دسر، تعدادی از این ژله‌ها را روی یکدیگر بچینیم. از آن‌جا که در ایران باستان هرچه ژله بلندتر بود ارزش بیشتری داشت، افراسیاب قصد دارد با قرار دادن تعدادی ژله بر روی هم بلندترین ژله‌ي ممکن را بسازد. برنامه‌ای بنویسید که با دریافت وزن و قدرت تحمل ژله‌ها، طول بلندترین برج ژله‌ای را به دست آورد.

ورودی🔗

در خط اول ورودی عدد $n$ و س‍پس در $n$ خط بعد، درهر خط ابتدا عدد $W_i$ و سپس $C_i$ داده می‌شود.

خروجی🔗

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

محدودیت‌ها🔗

$0 \leq W_i, C_i \leq 10^9 , \, n \leq 10^9$

مثال🔗

ورودی نمونه ۱

خروجی نمونه ۱

ورودی نمونه ۲

2
10 5
9 4

خروجی نمونه ۲

لکنت

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

کریم یک کودک ۵ ساله است که در گفتن برخی حروف انگلیسی مشکل دارد.

برای مثال او گاهی از اوقات به جای حرف K، حرف T را تلفظ میکند. اما او هیچ‌گاه به جای حرف T، حرف K را تلفظ نمی‌کند.

همینطور او گاهاَ حرف G را به اشتباه D تلفظ می‌کند. و R را بعضی اوقات L تلفظ می‌کند و بعضی اوقات F. البته پیش می‌آید که این حروف را درست تلفظ کند.

مادر کریم همیشه نسبت به گفته‌ی او شوق وافری نشان می‌دهد؛ از این رو کلمه‌ای که کریم گفته را به شما میگوید و شما باید تعداد کلمه‌های ممکن که کریم با مدنظر داشتن آن‌ها چنین کلمه‌ای را می‌گوید را به او بگویید. (مستقل از بامعنا بودن یا نبودن این کلمات)

به مثال و توضیح آن توجه کنید.

ورودی🔗

تنها خط ورودی شامل یک رشته به طول حداکثر ۲۰ حرف از حروف بزرگ انگلیسی است.

خروجی🔗

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

ورودی نمونه🔗

FILIPEK

خروجی نمونه🔗

کریم ممکن است کلمات FILIPEK، RILIPEK، RIRIPEK یا FIRIPEK را مد نظر داشته باشد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول پرست است، جهت صرفه‌جویی در تعداد حروف پیامک‌هایش به فشرده‌سازی رشته‌ها روی آورده. روش عمو برای فشرده‌سازی به این صورت است: که او در ابتدا جایگشتی از اعداد ۱, ۲, ..., $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

خروجی نمونه🔗

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

خانواده بلک یکی از اصیل ترین خانواده‌ها میان خانواده‌های جادوگری است و همه اعضای آن به شجره‌نامه خانواده خود بسیار اهمیت می‌دهند. شجره‌نامه این خانواده به شکل یک درخت است و ریشه آن بزرگترین فرد خانواده بلک است. در این خانواده سنت‌های زیادی وجود دارد. مثلن گاهی یکی از اعضای خانواده تصمیم میگیرد جایزه‌ای برای بچه‌هایش بگیرد. نحوه جایزه دادن به این صورت است که فرد جایزه‌دهنده در آن روز جایزه را پیش خودش نگه‌میدارد و فردایش آن جایزه را به یکی از فرزندانش (در صورت وجود) می‌دهد. در صورتی که آن شخص، فرزندی نداشته باشد جایزه پیش خودش می‌ماند. وگرنه فرزندش همین کار را تکرار می‌کند. یعنی جایزه را یک روز پیش خود نگه می‌دارد و فردایش آن را به یکی از فرزندانش می‌دهد. این کار آنقدر تکرار می‌شود تا جایزه به یکی از بلک‌های جوان برسد. (منظور عضوی از خانوادهاست که هنوز فرزندی ندارد یعنی یکی از برگ‌های درخت شجره‌نامه) با گرفتن زمان جایزه فرستادن‌ها و شخص‌فرستنده جایزه به سوالاتی شبیه سوال زیر پاسخ دهید: + یک عضو جوان خانواده بلک تا یک روز مشخص حداکثر چند جایزه گرفته است؟ ## ورودی در خط اول ورودی دو عدد `n` و `q` آمده اند که `n` تعداد اعضای خانواده بلک و `q` تعداد استفسارات (`query`ها) را نشان می‌دهد. در خط بعد `n-1` عدد $p_2$ jh $p_n$ آمده است که شجره نامه خانواده بلک را مشخص می‌کند. فرض کنید اعضای خانواده به ترتیب سن با اعداد 1 تا `n` شماره‌گذاری شده‌اند. عدد $p_i$ شماره پدر(یا مادر) عضو شماره `i` را نشان‌ می‌دهد. رأس شماره 1 اولین عضو خانواده بلک است. در هر یک از `q` خط بعد در هر خط یک استفسار آمده است. در اول هر خط یک کاراکتر آمده است که نوع استفسار را مشخص می‌کند. کاراکتر `$` نشان دهنده‌ جایزه دادن و `?` نشان دهنده پرسش است. + در حالت `$`، در ادامه دو عدد `v` و `t` آمده است که نشان می‌دهد عضو شماره `v`ام خانواده در روز `t` تصمیم می‌گیرد جایزه بخرد! دقت کنید که یک نفر ممکن است جوان باشد و برای خودش جایزه بگیرد. + در حالت `?`، در ادامه دو عدد `v` و `t` آمده است که نشان می‌دهد عضو شماره `v`آم خانواده از ابتدا تا روز `t` (شامل خود این روز) حداکثر چند جایزه گرفته است؟ تضمین می‌شود که این عضو یک بلک جوان است(فرزندی ندارد). + استفسارات به ترتیب نانزولی برحسب زمان در ورودی ظاهر شده‌اند. + $2 \leq n \leq 2 \times 10^5$ + $ 1 \leq p_i \leq i−1 , 2 \leq i \leq n $ + $ 1 \leq q \leq 2 \times 105 $ + $ 1 \leq v \leq n $ + $ 1 \leq t \leq 109$ ## خروجی در خروجی به ازای هر پرسش، جواب آن را در یک خط چاپ کنید. ## مثال ورودی نمونه ``` 5 8 1 2 2 1 $ 2 1 ? 3 3 $ 1 4 $ 2 4 ? 3 4 ? 3 5 ? 3 6 ? 5 6 ``` خروجی نمونه ``` 1 1 2 3 1 ``` (24امین دوره المپیاد کامپیوتر- آزمون سوم - 1393/06/06)

خانواده بلک

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

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

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

ورودی🔗

در خط اول ورودی دو عدد n و q آمده اند که n تعداد اعضای خانواده بلک و q تعداد استفسارات (queryها) را نشان می‌دهد. در خط بعد n-1 عدد $p_2$ jh $p_n$ آمده است که شجره نامه خانواده بلک را مشخص می‌کند. فرض کنید اعضای خانواده به ترتیب سن با اعداد 1 تا n شماره‌گذاری شده‌اند. عدد $p_i$ شماره پدر(یا مادر) عضو شماره i را نشان‌ می‌دهد. رأس شماره 1 اولین عضو خانواده بلک است.

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

در حالت $، در ادامه دو عدد v و t آمده است که نشان می‌دهد عضو شماره vام خانواده در روز t تصمیم می‌گیرد جایزه بخرد! دقت کنید که یک نفر ممکن است جوان باشد و برای خودش جایزه بگیرد.
در حالت ?، در ادامه دو عدد v و t آمده است که نشان می‌دهد عضو شماره vآم خانواده از ابتدا تا روز t (شامل خود این روز) حداکثر چند جایزه گرفته است؟ تضمین می‌شود که این عضو یک بلک جوان است(فرزندی ندارد).
استفسارات به ترتیب نانزولی برحسب زمان در ورودی ظاهر شده‌اند.
$2 \leq n \leq 2 \times 10^5$
$ 1 \leq p_i \leq i−1 , 2 \leq i \leq n $
$1 \leq q \leq 2 \times 105$
$1 \leq v \leq n$
$1 \leq t \leq 109$

خروجی🔗

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

مثال🔗

ورودی نمونه

خروجی نمونه

(24امین دوره المپیاد کامپیوتر- آزمون سوم - 1393/06/06)

-«راه بهشت از برنامه‌ی تو میگذره!» جمله‌ی بالا آخرین حرفی بود که یک فرد گمشده در جهنم به زبان آورد! جاده‌ی اصلی یک شهر در انتها به دو جاده تقسیم می‌شود. جاده‌ی اول رو به بهشت است و جاده‌ی دوم رو به جهنم! هیچ کدام از این جاده‌ها راه برگشتی ندارند. اینک شمایید و مردم این شهر و انتخاب جاده! متأسفانه انتخاب جاده چندان آسان نیست و هیچ تابلویی وجود ندارد و شما مجبورید در انتخاب جاده به حرف مردم آن شهر اعتماد کنید. این مردم به دو گروه تقسیم می شوند. گروهی همیشه راست می‌گویند و گروهی همیشه دروغ! و تنها اطلاعات دیگری که داریم، این است که تعداد افراد راست‌گوی شهر از تعداد دروغ‌گویان بیشتر است. شما فکر می‌کنید و فکر می‌کنید و ناگهان ایده به ذهن شما می‌رسد! کافی است که از هرکس بخواهید اطلاعاتش را درباره‌ی دروغ‌گو یا راست‌گو بودن دیگران به شما بگوید و با استفاده از تناقضات آن‌ها، افراد راست‌گو و دروغ‌گو را تشخیص دهید. حال «راه بهشت از برنامه‌ای که می‌نویسید، میگذرد!» ## مثال در ابتدا تعداد نفرات شهر از سوی کاربر وارد می‌شود. فرض کنید که در این شهر سه نفر وجود دارند. از هریک از آن‌ها که می‌خواهیم که اطلاعاتشان را درباره‌ی تمامی نفرات شهر بدهند. آن‌ها نیز به ترتیب شروع به دادن اطلاعات می‌کنند و جدول زیر به دست می‌آید: ``` 3 L L L D D T ``` این جدول به این معناست که نفر اول ادعا می‌کند دو نفر دیگر دروغ می‌گویند، نفر دوم ادعا می‌کند نفر اول دروغ می‌گوید ولی درباره‌ی نفر سوم نظری ندارد. همچنین نفر سوم درباره‌ی نفر اول نظری ندارد ولی ادعا می‌کند که نفر دوم راست می‌گوید. حال بر اساس ورودی بالا می‌توان حقیقت را تشخیص داد. فرض کنید که نفر اول راست‌گو باشد. در این صورت طبق ادعای او، دو نفر دیگر دروغ‌گو هستند و این با اطلاعات تطبیق دارد؛ زیر اگر نفر دوم دروغ‌گو باشد ادعا می‌کند که نفر اول دروغ‌گو است و اگر نفر سوم دروغ‌گو باشد، از آنجا که می‌داند نفر دوم دروغ‌گو است، به دروغ او را راست‌گو معرفی خواهد کرد! بنابراین طبق اطلاعات این حالت ممکن است ولی توجه کنید که تعداد راست‌گویان شهر از تعداد دروغ‌گویان بیشتر است و بنابراین این حالت امکان‌پذیر نخواهد بود. از طرفی فرض کنید که نفر اول دروغ‌گو باشد. از آن‌جا که خودش دروغ‌گو است و دو نفر دیگر را دروغ‌گو معرفی کرده است، دو نفر دیگر باید راستگو باشند! این حالت نیز با اطلاعات تطبیق دارد؛ زیرا اگر نفر دوم راست‌گو باشد، نفر اول را دروغ‌گو معرفی می‌کند و نفر سوم نیز نفر دوم را راست‌گو معرفی می‌کند. بنابراین حالت دروغ گو، راست‌گو، راست‌گو با اطلاعات تطبیق دارد و حالات دیگر با توجه به نحوه‌ی ورودی امکان‌پذیر نیست: ``` L T T ``` ورودی نمونه ``` 4 D D D T L D L D L D T D ``` خروجی نمونه ``` T T L T ```

راه بهشت در شهر دروغ‌گویان

-«راه بهشت از برنامه‌ی تو میگذره!»

جمله‌ی بالا آخرین حرفی بود که یک فرد گمشده در جهنم به زبان آورد!

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

شما فکر می‌کنید و فکر می‌کنید و ناگهان ایده به ذهن شما می‌رسد! کافی است که از هرکس بخواهید اطلاعاتش را درباره‌ی دروغ‌گو یا راست‌گو بودن دیگران به شما بگوید و با استفاده از تناقضات آن‌ها، افراد راست‌گو و دروغ‌گو را تشخیص دهید. حال «راه بهشت از برنامه‌ای که می‌نویسید، میگذرد!»

مثال🔗

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

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

3
L L
L D
D T

این جدول به این معناست که نفر اول ادعا می‌کند دو نفر دیگر دروغ می‌گویند، نفر دوم ادعا می‌کند نفر اول دروغ می‌گوید ولی درباره‌ی نفر سوم نظری ندارد. همچنین نفر سوم درباره‌ی نفر اول نظری ندارد ولی ادعا می‌کند که نفر دوم راست می‌گوید.

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

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

بنابراین حالت دروغ گو، راست‌گو، راست‌گو با اطلاعات تطبیق دارد و حالات دیگر با توجه به نحوه‌ی ورودی امکان‌پذیر نیست:

L T T

ورودی نمونه

4
D D D
T L D
L D L
D T D

خروجی نمونه

T T L T