برنده والیبال


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

تیم والیبال «کدکاپ» (CodeCup) و تیم والیبال «کوئرا» (Quera) باهم tt دَست والیبال بازی کرده‌اند. می‌دانیم در دست iiام، nn امتیاز بین دو تیم رد و بدل شده. هر امتیاز به دقیقاً یکی از دو تیم کدکاپ یا کوئرا رسیده. هر تیمی که زودتر به امتیاز ۲۵ برسد برنده آن دست است.

توضیح تصویر

داور این بازی، حرف اول تیم گیرنده‌ی هر امتیاز را به ترتیب در یک رشته‌ی nn کاراکتری نوشته است. یعنی اگر امتیاز iiام را تیم کدکاپ گرفته باشد، کاراکتر iiام برابر C و اگر امتیاز iiام را تیم کوئرا گرفته باشد، کاراکتر iiام برابر Q است.

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

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

ورودی🔗

در سطر اول ورودی، عدد صحیح tt آمده که تعداد ست‌ها را نشان می‌دهد. 1t1001 \leq t \leq 100

در سطر اول هر ست، عدد صحیح nn آمده که تعداد امتیازهای رد و بدل شده را نشان می‌دهد. 25n4925 \leq n \leq 49

در سطر دوم هر ست، یک رشته از nn کاراکتر است که کاراکتر iiام برابر C است اگر امتیاز را تیم کدکاپ گرفته باشد و Q است اگر امتیاز را تیم کوئرا گرفته باشد.

تضمین می‌شود ورودی درست است و دقیقاً یکی از تیم‌ها در هر ست، برنده شده.

خروجی🔗

در tt سطر برنده‌ی هر ست را به ترتیب چاپ کنید. اگر برنده تیم کدکاپ بود رشته‌ی CodeCup و اگر برنده تیم کوئرا بود Quera را چاپ کنید.

توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.

مثال🔗

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

2
44
QQQQCCCQQQQQCCQQQQCQCCCCCCQQQQCCCQQQQQCCCCQQ
25
CCCCCCCCCCCCCCCCCCCCCCCCC
Plain text

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

Quera
CodeCup
Plain text
جدول امتیازات دست اول
ردیف 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

بازگشت ابدی


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

توضیح تصویر

دنباله‌ی {fn}\{f_n\} برای همه‌ی اعداد طبیعی مثل nn ساخته می‌شود. ابتدا مقدار f1=2f_1 = 2 درنظر بگیرید. برای nnهای بزرگ‌تر از ۱، مقدار fnf_n به این صورت بدست می‌آید:

اگر nn عددی زوج باشد: fn=fn12×fn12f_n = \lfloor\frac{f_{n-1}}{2}\rfloor \times \lceil\frac{f_{n-1}}{2}\rceil

اگر nn عددی فرد باشد: fn=fn14 f_n = f_{n-1} - 4

منظور از x\lfloor x \rfloor (بخوانید کَفِ xx) بزرگ‌ترین عدد صحیح، کوچک‌تر یا مساوی xx است. برای مثال 3.2=3\lfloor 3.2 \rfloor = 3، 1.3=2\lfloor -1.3 \rfloor = -2 و 2=2\lfloor 2 \rfloor = 2.

منظور از x\lceil x \rceil (بخوانید سَقفِ xx) کوچک‌ترین عدد صحیح، بزرگ‌تر یا مساوی xx است. برای مثال 3.2=4\lceil 3.2 \rceil = 4، 1.3=1\lceil -1.3 \rceil = -1 و 2=2\lceil 2 \rceil = 2.

حال از شما tt سوال پرسیده می‌شود. در هر سوال یک عدد طبیعی مثل nn داده می‌شود و از شما مقدار fnf_n را می‌خواهند.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت tt آمده که تعداد سوالات را نشان می‌دهد.

1t1000001 \leq t \leq 100\,000

در tt سطر بعدی، در هر سطر، یک عدد صحیح و مثبت مثل nn داده می‌شود.

1n1091 \leq n \leq 10^9

خروجی🔗

در tt سطر مختلف پاسخ سوالات را به ترتیب چاپ کنید.

مثال‌ها🔗

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

5
1
7
2
1403
8
Plain text

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

2
-3
1
-3
2
Plain text

f1=2f_1 = 2

f2=f12×f12=22×22=1×1=1f_2 = \lfloor\frac{f_1}{2}\rfloor \times \lceil\frac{f_1}{2}\rceil = \lfloor\frac{2}{2}\rfloor \times \lceil\frac{2}{2}\rceil = 1 \times 1 = 1

f3=f24=14=3f_3 = f_2 - 4 = 1 - 4 = -3

f4=f32×f32=32×32=2×1=2f_4 = \lfloor\frac{f_3}{2}\rfloor \times \lceil\frac{f_3}{2}\rceil = \lfloor\frac{-3}{2}\rfloor \times \lceil\frac{-3}{2}\rceil = -2 \times -1 = 2

f5=f44=24=2f_5 = f_4 - 4 = 2 - 4 = -2

f6=f52×f52=22×22=1×1=1f_6 = \lfloor\frac{f_5}{2}\rfloor \times \lceil\frac{f_5}{2}\rceil = \lfloor\frac{-2}{2}\rfloor \times \lceil\frac{-2}{2}\rceil = -1 \times -1 = 1

f7=f64=14=3f_7 = f_6 - 4 = 1 - 4 = -3

f8=f72×f72=32×32=2×1=2f_8 = \lfloor\frac{f_7}{2}\rfloor \times \lceil\frac{f_7}{2}\rceil = \lfloor\frac{-3}{2}\rfloor \times \lceil\frac{-3}{2}\rceil = -2 \times -1 = 2

عدالت شکلاتی


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

یک کیک مکعب مستطیلی a×b×ca \times b \times c موازی محورهای مختصات داریم. در واقع این کیک تمام نقاط (x,y,z)(x, y, z) است که 0xa0 \leq x \leq a، 0yb0 \leq y \leq b و 0zc0 \leq z \leq c باشد.

داخل این کیک nn قطعه شکلات قرار دارد. هر قطعه شکلات یک مکعب مستطیل موازی محورها است. می‌دانیم که هیچ دو قطعه شکلاتی با هم اشتراک ندارند. هر قطعه شکلات را با شش عدد x1,y1,z1,x2,y2,z2x_1, y_1, z_1, x_2, y_2, z_2\,\,\, نشان می‌دهیم و یعنی تمام نقاط (x,y,z)(x, y, z) که x1xx2x_1 \leq x \leq x_2، y1yy2y_1 \leq y \leq y_2 و z1zz2z_1 \leq z \leq z_2 از کیک شکلاتی هستند. بقیه فضای کیک را خمیر تشکیل داده است.

توضیح تصویر

خانم کاپ‌کیک می‌خواهد این کیک را بین mm نفر تقسیم کند. او می‌خواهد کیک را m1m - 1 برش از بالا (موازی صفحه‌ی yzyz) بزند به طوری که mm قطعه بدست آمده حجم یکسانی شکلات داشته باشند.

از شما می‌خواهیم مختصات این برش‌ها را پیدا کنید.

ورودی🔗

در سطر اول ورودی دو عدد صحیح nn و mm آمده که به ترتیب تعداد قطعات شکلات و تعداد نفرات را نشان می‌دهد.

1n100001 \leq n \leq 10\,000 2m100002 \leq m \leq 10\,000

در سطر دوم ورودی سه عدد صحیح aa، bb و cc آمده که ابعاد کیک را نشان می‌دهد. 1a,b,c1001 \leq a, b, c \leq 100

در nn سطر بعدی، در هر سطر شش عدد صحیح x1,y1,z1,x2,y2,z2x_1, y_1, z_1, x_2, y_2, z_2\,\,\, داده می‌شود که مختصات قطعه شکلاتی را نشان می‌دهد.

0x1<x2a,0y1<y2b,0z1<z2c0 \leq x_1 \lt x_2 \leq a, \quad 0 \leq y_1 \lt y_2 \leq b, \quad 0 \leq z_1 \lt z_2 \leq c

تضمین می‌شود که هیچ دو قطعه شکلاتی با هم اشتراک ندارند.

خروجی🔗

خروجی m1m - 1 خط دارد و در خط iiام عدد اعشاری XiX_i که نشان دهنده‌ی برشی است که باید بزنیم. شما باید برش‌ها را به ترتیب چاپ کنید یعنی:

0<X1<X2<<Xm1<a0 \lt X_1 \lt X_2 \lt \dots \lt X_{m-1} \lt a

زمانی پاسخ شما پذیرفته می‌شود که اختلاف حجم شکلاتی که به هر کس می‌رسد با مقدار دقیق آن حداکثر ۰.۰۰۱ باشد.

مثال🔗

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

2 3
3 4 5
0 0 0 1 1 1
2 2 2 3 4 5
Plain text

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

2.222222222217
2.611111111103
Plain text

مثلث گمشده


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

در کشور کدکاپ nn شهر وجود دارد. شهرهای کدکاپ با اعداد 11 تا nn شماره‌گذاری شده‌اند. بین شهرهای کدکاپ تعدادی جاده قرار دارد. می‌دانیم هر جاده دو طرفه است و دقیقاً دو شهر مختلف را به هم متصل می‌کند. در واقع نقشه کشور کدکاپ، به‌صورت یک گراف ساده است.

به سه شهر مختلف مثل uu، vv و ww یک مثلث می‌گوییم، هرگاه بین uvuv، vwvw و uwuw یک جاده وجود داشته باشد.

توضیح تصویر

نقشه‌ی کشور کدکاپ گم شده اما تعداد شهرهای آن یعنی nn را می‌دانیم. همچنین برای mm جفت از شهرها مثل aia_i و bib_i می‌دانیم شهر aia_i و شهر bib_i باهم در حداقل یک مثلث آمده‌اند. یعنی شهر دیگری مثل cic_i وجود دارد که این سه‌شهر باهم یک مثلث تشکیل می‌دهند. توجه کنید که مقدار cic_i را نداریم.

همچنین برای kk جفت از شهر‌ها مثل aia_i و bib_i می‌دانیم در هیچ مثلثی نیامده‌اند. یعنی هیچ شهری مثل cic_i وجود ندارد که با آن‌ها تشکیل مثلث بدهد.

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

ورودی🔗

در سطر اول ورودی، عدد صحیح tt آمده که تعداد تست‌ها را نشان می‌دهد.

1t10001 \leq t \leq 1000

در سطر اول هر تست سه عدد nn، mm و kk آمده است که به ترتیب تعداد شهرهای کدکاپ قدیم، تعداد جفت شهرهایی که در حداقل یک مثلث آمده‌اند و تعداد جفت شهرهایی که در هیچ مثلثی نیامده‌اند.

1n1000,0m+kn(n1)21 \leq n \leq 1000, \quad 0 \leq m + k \leq \frac{n(n - 1)}{2}

در m+km+k سطر بعدی، در هر سطر دو شهر uu و vv آمده که mm جفت اول در حداقل یک مثلث آمده‌اند و kk جفت آخر در هیچ مثلثی نیامده‌اند.

1uvn1 \leq u \neq v \leq n

تضمین می‌شود که هر جفت شهر حداکثر یکبار بیاید. همچنین مجموع nn برای همه‌ی تست‌ها حداکثر ۱۰۰۰ باشد.

خروجی🔗

با عبارت YES و NO بگویید چنین گرافی وجود دارد یا نه. اگر جواب YES بود یک نقشه با شرایط گفته شده چاپ کنید.

برای چاپ کردن نقشه، در سطر بعد از YES عدد ee را چاپ کنید که تعداد جاده‌های موجود را نشان می‌دهد. سپس در ee سطر بعدی در هر سطر دو عدد صحیح مثل uu و vv با یک فاصله از هم چاپ کنید که وجود یک جاده بین uu و vv را نشان می‌دهد.

توجه کنید باید هر جاده را حداکثر یکبار چاپ کنید و هیچ جاده‌ای ابتدا و انتهای یکسانی نداشته باشند. اگر چند جواب برای مسئله وجود دارد، یکی را به دلخواه چاپ کنید.

مثال‌ها🔗

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

4
3 0 0
3 1 0
2 1
3 2 0
1 2
3 1
3 1 2
2 1
3 1
2 3
Plain text

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

YES
2
2 1
1 3
YES
3
1 2
3 1
3 2
YES
3
1 2
1 3
2 3
NO
Plain text

اندازه‌گیری کوه


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

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

زمین‌شناسان nn نقطه در کوه کدکاپ را انتخاب کرده و ارتفاع کوه را در آن نقاط را اندازه گیری کرده‌اند. ارتفاع این نقاط را به ترتیب از چپ به راست با h1,h2,,hnh_1, h_2, \dots, h_n\, مشخص می‌کنیم. با این حال اندازه‌گیری زمین‌شناسان خطا دارد و ارتفاع واقعی کوه در این nn نقطه برابر با اعداد اندازه‌گیری شده نیست. ارتفاع واقعی کوه را در این nn نقطه با H1,H2,,HnH_1, H_2, \dots, H_n\, نشان می‌دهیم.

توضیح تصویر

بنابراین با توجه به ویژگی کوه کدکاپ می‌دانیم دنباله‌ی HH در ابتدا صعودی و سپس نزولی است. یعنی عدد صحیحی مثل ii که 1in1 \leq i \leq n وجود دارد به طوری که H1,H2,,HiH_1, H_2, \dots, H_i\, تشکیل یک دنباله‌ی صعودی و دنباله‌ی Hi+1,Hi+2,,HnH_{i+1}, H_{i+2}, \dots, H_n\, تشکیل یک دنباله‌ی نزولی بدهد.

به یک دنباله مثل a1,a2,,ana_1, a_2, \dots, a_n\, صعودی می‌گوییم هرگاه a1a2ana_1 \leq a_2 \leq \dots \leq a_n\, باشد. به یک دنباله مثل a1,a2,,ana_1, a_2, \dots, a_n\, نزولی می‌گوییم هرگاه a1a2ana_1 \geq a_2 \geq \dots \geq a_n\, باشد.

می‌گوییم خطای اندازه‌گیری kk است اگر هر کدام از hih_iها حداکثر kk واحد با HiH_i اختلاف داشته باشد. (hiHik|h_i-H_i|\leq k\,)

به شما دنباله‌ی h1,h2,,hnh_1, h_2, \dots, h_n\, داده می‌شود. از شما می‌خواهیم کمینه خطای ممکن برای این داده‌ها را حساب کنید. یعنی کوچک‌ترین kkی صحیحی را پیدا کنید که دنباله‌ای مثل HH وجود داشته باشد که هر عضوش با hh حداکثر kk واحد اختلاف داشته باشد و در ابتدا صعود و سپس نزولی باشد.

ورودی🔗

در سطر اول ورودی، عدد صحیح tt آمده که تعداد تست‌ها را نشان می‌دهد. 1t2000001 \leq t \leq 200\,000

در سطر اول هر تست، عدد صحیح و مثبت nn آمده که تعداد اعداد آرایه را نشان می‌دهد. 1n2000001 \leq n \leq 200\,000

در سطر دوم هر تست، nn عدد h1,h2,,hnh_1, h_2, \dots, h_n\, با فاصله از هم آمده است. 1hi1091 \leq h_i \leq 10^9 توجه کنید که با وجود این که hih_i عددی است، HiH_i ممکن است هر عددی شامل اعداد منفی یا بزرگ‌تر از 10910^9 باشد.

تضمین می‌شود مجموع nnها برای همه‌ی تست‌ها حداکثر ۲۰۰،۰۰۰ باشد.

خروجی🔗

در tt سطر کمینه خطای ممکن برای هر تست را به ترتیب چاپ کنید.

مثال🔗

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

2
5
10 20 30 20 10
7
1 4 1 3 2 1 3
Plain text

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

0
1
Plain text

چنگک


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

سر چنگک آقا و خانم پیت کند شده و آن‌ها می‌خواهند سر آن را تعویض کند.

آقا و خانم پیت و چنگکشان

برای تعویض سر چنگک، آقا و خانم پیت به سراغ یک درخت nn راسی می‌روند. برای ساخت سر یک چنگک آن‌ها باید یال‌های یک زیرگراف 3x3x یالی خاص را از درخت حذف کنند. این زیرگراف خاص از 33 مسیر xx یالی تشکیل شده‌ است که راس اولشان با هم مشترک است. این گراف برای حالت x=2x=2 در شکل نمایش داده شده است.

توضیح تصویر

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

ورودی🔗

در سطر اول ورودی، ابتدا عدد طبیعی nn و سپس xx داده می‌شود. 1n3000001\leq n \leq 300\,000 1x1000001\leq x \leq 100\,000

در سطر دوم ورودی، n1n-1 عدد a2,a3,a4,,...,ana_2, a_3, a_4, ,..., a_n داده می‌شود. که عدد aia_i نشان دهنده‌ی این است که راس ii به راس aia_i در درخت متصل است. 1ain1\leq a_i \leq n تضمین می‌شود گراف حاصل یک درخت است.

خروجی🔗

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

مثال‌ها🔗

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

5 1
1 1 3 3 
Plain text

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

1
Plain text

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

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

7 1
1 1 3 3 2 2 
Plain text

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

2
Plain text

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

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

8 1
1 1 1 1 1 1 1 
Plain text

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

2
Plain text

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

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

12 2
1 2 3 4 4 5 6 1 1 9 10 
Plain text

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

1
Plain text

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