Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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

یک دنباله a1,a2,,an از شماره تیم‌ها را «دنباله‌ی برنده» می‌گوییم اگر به ازای i=1,,n1، تیم ai از تیم ai+1 برده باشد. (دقت کنید که ai{1,2,,n} و اگر ij‌ آن‌گاه aiaj.)

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


ابزار صفحه