تیم والیبال «کدکاپ» (CodeCup) و تیم والیبال «کوئرا» (Quera) باهم دَست والیبال بازی کردهاند. میدانیم در دست ام، امتیاز بین دو تیم رد و بدل شده. هر امتیاز به دقیقاً یکی از دو تیم کدکاپ یا کوئرا رسیده. هر تیمی که زودتر به امتیاز ۲۵ برسد برنده آن دست است.
داور این بازی، حرف اول تیم گیرندهی هر امتیاز را به ترتیب در یک رشتهی کاراکتری نوشته است. یعنی اگر امتیاز ام را تیم کدکاپ گرفته باشد، کاراکتر ام برابر C
و اگر امتیاز ام را تیم کوئرا گرفته باشد، کاراکتر ام برابر Q
است.
میدانیم همهی دستها به درستی داوری شده و به محض برنده شدن یک تیم، آن دست به پایان رسیده. اما این داور فراموش کرده نام تیم برنده را بنویسد. از شما میخواهیم با بررسی کردن این رشتهها، تیم برندهی هر دست را مشخص کنید.
برای بهتر متوجه شدن خواستهی سوال، مثال پایین را مطالعه کنید.
در سطر اول ورودی، عدد صحیح آمده که تعداد ستها را نشان میدهد.
در سطر اول هر ست، عدد صحیح آمده که تعداد امتیازهای رد و بدل شده را نشان میدهد.
در سطر دوم هر ست، یک رشته از کاراکتر است که کاراکتر ام برابر C
است اگر امتیاز را تیم کدکاپ گرفته باشد و Q
است اگر امتیاز را تیم کوئرا گرفته باشد.
تضمین میشود ورودی درست است و دقیقاً یکی از تیمها در هر ست، برنده شده.
در سطر برندهی هر ست را به ترتیب چاپ کنید. اگر برنده تیم کدکاپ بود رشتهی CodeCup
و اگر برنده تیم کوئرا بود Quera
را چاپ کنید.
توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.
ردیف | Quera | CodeCup |
---|---|---|
1 | 1 | 0 |
2 | 2 | 0 |
3 | 3 | 0 |
4 | 4 | 0 |
5 | 4 | 1 |
6 | 4 | 2 |
7 | 4 | 3 |
8 | 5 | 3 |
9 | 6 | 3 |
10 | 7 | 3 |
11 | 8 | 3 |
12 | 9 | 3 |
13 | 9 | 4 |
14 | 9 | 5 |
15 | 10 | 5 |
16 | 11 | 5 |
17 | 12 | 5 |
18 | 13 | 5 |
19 | 13 | 6 |
20 | 14 | 6 |
21 | 14 | 7 |
22 | 14 | 8 |
23 | 14 | 9 |
24 | 14 | 10 |
25 | 14 | 11 |
26 | 14 | 12 |
27 | 15 | 12 |
28 | 16 | 12 |
29 | 17 | 12 |
30 | 18 | 12 |
31 | 18 | 13 |
32 | 18 | 14 |
33 | 18 | 15 |
34 | 19 | 15 |
35 | 20 | 15 |
36 | 21 | 15 |
37 | 22 | 15 |
38 | 23 | 15 |
39 | 23 | 16 |
40 | 23 | 17 |
41 | 23 | 18 |
42 | 23 | 19 |
43 | 24 | 19 |
44 | 25 | 19 |
ردیف | Quera | CodeCup |
---|---|---|
1 | 0 | 1 |
2 | 0 | 2 |
3 | 0 | 3 |
4 | 0 | 4 |
5 | 0 | 5 |
6 | 0 | 6 |
7 | 0 | 7 |
8 | 0 | 8 |
9 | 0 | 9 |
10 | 0 | 10 |
11 | 0 | 11 |
12 | 0 | 12 |
13 | 0 | 13 |
14 | 0 | 14 |
15 | 0 | 15 |
16 | 0 | 16 |
17 | 0 | 17 |
18 | 0 | 18 |
19 | 0 | 19 |
20 | 0 | 20 |
21 | 0 | 21 |
22 | 0 | 22 |
23 | 0 | 23 |
24 | 0 | 24 |
25 | 0 | 25 |
دنبالهی برای همهی اعداد طبیعی مثل ساخته میشود. ابتدا مقدار درنظر بگیرید. برای های بزرگتر از ۱، مقدار به این صورت بدست میآید:
اگر عددی زوج باشد:
اگر عددی فرد باشد:
منظور از (بخوانید کَفِ ) بزرگترین عدد صحیح، کوچکتر یا مساوی است. برای مثال ، و .
منظور از (بخوانید سَقفِ ) کوچکترین عدد صحیح، بزرگتر یا مساوی است. برای مثال ، و .
حال از شما سوال پرسیده میشود. در هر سوال یک عدد طبیعی مثل داده میشود و از شما مقدار را میخواهند.
در سطر اول ورودی، عدد صحیح و مثبت آمده که تعداد سوالات را نشان میدهد.
در سطر بعدی، در هر سطر، یک عدد صحیح و مثبت مثل داده میشود.
در سطر مختلف پاسخ سوالات را به ترتیب چاپ کنید.
یک کیک مکعب مستطیلی موازی محورهای مختصات داریم. در واقع این کیک تمام نقاط است که ، و باشد.
داخل این کیک قطعه شکلات قرار دارد. هر قطعه شکلات یک مکعب مستطیل موازی محورها است. میدانیم که هیچ دو قطعه شکلاتی با هم اشتراک ندارند. هر قطعه شکلات را با شش عدد نشان میدهیم و یعنی تمام نقاط که ، و از کیک شکلاتی هستند. بقیه فضای کیک را خمیر تشکیل داده است.
خانم کاپکیک میخواهد این کیک را بین نفر تقسیم کند. او میخواهد کیک را برش از بالا (موازی صفحهی ) بزند به طوری که قطعه بدست آمده حجم یکسانی شکلات داشته باشند.
از شما میخواهیم مختصات این برشها را پیدا کنید.
در سطر اول ورودی دو عدد صحیح و آمده که به ترتیب تعداد قطعات شکلات و تعداد نفرات را نشان میدهد.
در سطر دوم ورودی سه عدد صحیح ، و آمده که ابعاد کیک را نشان میدهد.
در سطر بعدی، در هر سطر شش عدد صحیح داده میشود که مختصات قطعه شکلاتی را نشان میدهد.
تضمین میشود که هیچ دو قطعه شکلاتی با هم اشتراک ندارند.
خروجی خط دارد و در خط ام عدد اعشاری که نشان دهندهی برشی است که باید بزنیم. شما باید برشها را به ترتیب چاپ کنید یعنی:
زمانی پاسخ شما پذیرفته میشود که اختلاف حجم شکلاتی که به هر کس میرسد با مقدار دقیق آن حداکثر ۰.۰۰۱ باشد.
در کشور کدکاپ شهر وجود دارد. شهرهای کدکاپ با اعداد تا شمارهگذاری شدهاند. بین شهرهای کدکاپ تعدادی جاده قرار دارد. میدانیم هر جاده دو طرفه است و دقیقاً دو شهر مختلف را به هم متصل میکند. در واقع نقشه کشور کدکاپ، بهصورت یک گراف ساده است.
به سه شهر مختلف مثل ، و یک مثلث میگوییم، هرگاه بین ، و یک جاده وجود داشته باشد.
نقشهی کشور کدکاپ گم شده اما تعداد شهرهای آن یعنی را میدانیم. همچنین برای جفت از شهرها مثل و میدانیم شهر و شهر باهم در حداقل یک مثلث آمدهاند. یعنی شهر دیگری مثل وجود دارد که این سهشهر باهم یک مثلث تشکیل میدهند. توجه کنید که مقدار را نداریم.
همچنین برای جفت از شهرها مثل و میدانیم در هیچ مثلثی نیامدهاند. یعنی هیچ شهری مثل وجود ندارد که با آنها تشکیل مثلث بدهد.
حال از شما میخواهیم باتوجه به این اطلاعات بررسی کنید نقشهی قابل قبولی برای کشور کدکاپ وجود دارد یا نه. همچنین در صورت وجود چنین کشوری، یک مثال از آن را ارائه کنید.
در سطر اول ورودی، عدد صحیح آمده که تعداد تستها را نشان میدهد.
در سطر اول هر تست سه عدد ، و آمده است که به ترتیب تعداد شهرهای کدکاپ قدیم، تعداد جفت شهرهایی که در حداقل یک مثلث آمدهاند و تعداد جفت شهرهایی که در هیچ مثلثی نیامدهاند.
در سطر بعدی، در هر سطر دو شهر و آمده که جفت اول در حداقل یک مثلث آمدهاند و جفت آخر در هیچ مثلثی نیامدهاند.
تضمین میشود که هر جفت شهر حداکثر یکبار بیاید. همچنین مجموع برای همهی تستها حداکثر ۱۰۰۰ باشد.
با عبارت YES
و NO
بگویید چنین گرافی وجود دارد یا نه. اگر جواب YES
بود یک نقشه با شرایط گفته شده چاپ کنید.
برای چاپ کردن نقشه، در سطر بعد از YES
عدد را چاپ کنید که تعداد جادههای موجود را نشان میدهد. سپس در سطر بعدی در هر سطر دو عدد صحیح مثل و با یک فاصله از هم چاپ کنید که وجود یک جاده بین و را نشان میدهد.
توجه کنید باید هر جاده را حداکثر یکبار چاپ کنید و هیچ جادهای ابتدا و انتهای یکسانی نداشته باشند. اگر چند جواب برای مسئله وجود دارد، یکی را به دلخواه چاپ کنید.
تصویر زیر، نمای کوه کدکاپ است. میدانیم ارتفاع این کوه از هر دو طرف تا قله همواره صعودی است. توجه کنید ممکن است در بازهای ارتفاع ثابت بماند اما هیچوقت در مسیر قله، ارتفاع کاهش نمییابد.
زمینشناسان نقطه در کوه کدکاپ را انتخاب کرده و ارتفاع کوه را در آن نقاط را اندازه گیری کردهاند. ارتفاع این نقاط را به ترتیب از چپ به راست با مشخص میکنیم. با این حال اندازهگیری زمینشناسان خطا دارد و ارتفاع واقعی کوه در این نقطه برابر با اعداد اندازهگیری شده نیست. ارتفاع واقعی کوه را در این نقطه با نشان میدهیم.
بنابراین با توجه به ویژگی کوه کدکاپ میدانیم دنبالهی در ابتدا صعودی و سپس نزولی است. یعنی عدد صحیحی مثل که وجود دارد به طوری که تشکیل یک دنبالهی صعودی و دنبالهی تشکیل یک دنبالهی نزولی بدهد.
به یک دنباله مثل صعودی میگوییم هرگاه باشد. به یک دنباله مثل نزولی میگوییم هرگاه باشد.
میگوییم خطای اندازهگیری است اگر هر کدام از ها حداکثر واحد با اختلاف داشته باشد. ()
به شما دنبالهی داده میشود. از شما میخواهیم کمینه خطای ممکن برای این دادهها را حساب کنید. یعنی کوچکترین ی صحیحی را پیدا کنید که دنبالهای مثل وجود داشته باشد که هر عضوش با حداکثر واحد اختلاف داشته باشد و در ابتدا صعود و سپس نزولی باشد.
در سطر اول ورودی، عدد صحیح آمده که تعداد تستها را نشان میدهد.
در سطر اول هر تست، عدد صحیح و مثبت آمده که تعداد اعداد آرایه را نشان میدهد.
در سطر دوم هر تست، عدد با فاصله از هم آمده است. توجه کنید که با وجود این که عددی است، ممکن است هر عددی شامل اعداد منفی یا بزرگتر از باشد.
تضمین میشود مجموع ها برای همهی تستها حداکثر ۲۰۰،۰۰۰ باشد.
در سطر کمینه خطای ممکن برای هر تست را به ترتیب چاپ کنید.
سر چنگک آقا و خانم پیت کند شده و آنها میخواهند سر آن را تعویض کند.
برای تعویض سر چنگک، آقا و خانم پیت به سراغ یک درخت راسی میروند. برای ساخت سر یک چنگک آنها باید یالهای یک زیرگراف یالی خاص را از درخت حذف کنند. این زیرگراف خاص از مسیر یالی تشکیل شده است که راس اولشان با هم مشترک است. این گراف برای حالت در شکل نمایش داده شده است.
آقا و خانم پیت با استفاده از این درخت حداکثر چند سر چنگک میتوانند بسازند؟ توجه کنید که آقا و خانم پیت راسهای درخت را هیچگاه حذف نمیکنند. آنها تنها یک زیرگراف مشابه شکل پیدا میکنند و یالهای آن را از درخت حذف میکنند. بنابراین دو چنگک میتوانند در راس با هم اشتراک داشته باشند.
در سطر اول ورودی، ابتدا عدد طبیعی و سپس داده میشود.
در سطر دوم ورودی، عدد داده میشود. که عدد نشان دهندهی این است که راس به راس در درخت متصل است. تضمین میشود گراف حاصل یک درخت است.
در تنها سطر خروجی، یک عدد صحیح که نشان دهندهی حداکثر تعداد چنگکهایی است که آقا و خانم پیت میتوانند با استفاده از درخت بسازند را چاپ کنید.
یالهایی که آقا و خانم پیت برای ساخت سر چنگک اولشان باید حذف کنند با رنگ قرمز مشخص شده است.
یالهایی که آقاو خانم پیت برای سر چنگک اول حذف میکنند با رنگ قرمز و یالهای که برای سر چنگک دوم حذف میکنند با رنگ آبی مشخص شدهاست.
یالهایی که آقا و خانم پیت برای سر چنگک اول حذف میکنند با رنگ قرمز و یالهایی که برای سر چنگک دوم حذف میکنند با رنگ آبی مشخص شدهاست.
یالهایی که آقا و خانم پیت برای ساخت سر چنگکشان استفاده میکنند با رنگ قرمز مشخص شده است.