المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۱:سوال ۲

سوال ۲

در یک دوره مسابقه، $n$‌تیم با شماره‌های ۱ تا $n$‌ شرکت دارند و به صورت دوره‌ای هر تیم با تمامی تیم‌ها مسابقه می‌دهد. هر مسابقه یک برنده و یک بازنده دارد. نتایج مسابقات در یک ماتریس $n\times n$ بدین ترتیب ثبت شده است که در درایه‌ی $(i,j)$ شماره‌ی تیم برنده ($i$ یا $j$) قرار دارد. عناصر روی قطر اصلی ماتریس نتایج صفر در نظر گرفته می‌شود.

یک دنباله $a_1,a_2,…,a_n$ از شماره تیم‌ها را «دنباله‌ی برنده» می‌گوییم اگر به ازای $i=1,…,n-1$، تیم $a_i$ از تیم $a_{i+1}$ برده باشد. (دقت کنید که $a_i \in \{1,2,…,n\}$ و اگر $i \ne j$‌ آن‌گاه $a_i \ne a_j$.)

الگوریتمی بنویسید که تعداد تیم‌ها $(n\leq 20)$ و ماتریس نتایج را بگیرد و یک دنباله‌ی برنده پیدا کرده، در یک آرایه‌ی $n$ تایی قرار دهد.


ابزار صفحه