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

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

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

مینو حداکثر چند رونوشت از آگهی می‌تواند تولید کند؟

ورودی🔗

در خط اوّل ورودی رشته‌ی $S$ شامل a, b, c, ..., z, 1, 2, ..., 9 و «فاصله» آمده‌است.

در خط دوّم ورودی متن آگهی شامل a, b, c, ..., z, 1, 2, ..., 9 و «فاصله» آمده‌است.

هر دو رشته‌ی ورودی شامل حداقل ‌‌‌$1$ و حداکثر $10^5$ کاراکتر هستند.

دقّت کنید که فاصله «» هم یک کاراکتر در نظر گرفته می‌شود.

خروجی🔗

در تنها خط خروجی حداکثر تعداد آگهی‌ها را چاپ کنید.

مثال🔗

ورودی نمونه🔗

abracadabra 2018 codeknock
ab cd

خروجی نمونه🔗

2

*توضیح نمونه: * چون رشته‌ی $S$ شامل دو فاصله می‌باشد، واضح است که حداکثر تعداد آگهی‌ها از ۲ بیشتر نیست. و ۲ آگهی هم قابل تولید است.

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

پگاه خود را به عنوان هم‌سفر مینو معرفی کرد.

حال آن‌ها می‌خواهند با قطار گشتِ محشر را آغاز کنند. قطار آن‌ها $n$ واگن دارد که به ازای هر $1 \leq i \leq n$ دقیقا یکی از واگن‌ها $i$ کوپه دارد.

کوپه‌های قطار به ترتیب از چپ به راست با $1$ تا $\frac{n \times (n+1)}{2}$ شماره‌گذاری شده‌اند.

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

می‌دانیم واگن‌ها به ترتیبی بهم متصل شده‌اند که تعداد واگن‌هایی که عدد آن‌ها فرد است، بیشینه می‌باشد. چینش واگن‌های این قطار چگونه است؟

ورودی🔗

تنها ورودی عدد $n$ تعداد واگن‌های قطار است.

$1 \leq n \leq 100\ 000$

خروجی🔗

در خروجی $n$ عدد چاپ کنید که تعداد کوپه‌های هر واگن از چپ به راست است. اگر چند چینشِ خوب برای واگن‌ها وجود داشت یکی از آن‌ها را به دل‌خواه خروجی دهید.

مثال🔗

ورودی نمونه🔗

5

خروجی نمونه🔗

2 1 3 4 5

توضیح نمونه: عدد واگن‌ها در چینش ۵ ۴ ۳ ۱ ۲ به ترتیب ۱۱ ۷ ۴ ۳ ۱ است و بین همه‌ی چینش‌های مختلف ‌‌‌‌$n$ واگن بیشینه‌ی تعداد واگن‌هایی که عدد آن‌ها فرد است‌ ‌۴ می‌باشد.

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

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

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

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

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

ورودی🔗

در خط اوّل ورودی $n$ تعداد اعضای قبیله آمده‌است.

در ‌$n$ خط بعد در هر خط دو عدد $x_i$ و $y_i$ آمده که نشان‌دهنده‌ی مختصات نفر $i$اُم است.

تضمین می‌شود همه‌ی اعداد ورودی صحیح هستند و هیچ دو فردی از قبیله به یک نقطه فرستاده نمی‌شوند. هم‌چنین هیچ فردی به مبدأ فرستاده نمی‌شود.

$1 \leq n \leq 1\ 000\ 000$ $-1\ 000 \leq x_i, y_i \leq 1\ 000$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

3
1 1
2 2
-1 -1

خروجی نمونه🔗

2

توضیح نمونه: گلوله‌ی فردی که در $2, 2$ ایستاده است به فردی که در ‌‌$1, 1$ ایستاده برخورد می‌کند.

گلوله‌ی فردی که در $1, 1$ ایستاده است به فردی که در $-1, -1$ ایستاده برخورد می‌کند.

گلوله‌ی فردی که در ‌‌‌ $-1, -1$ ایستاده‌ است به فردی که در ‌$1, 1$ ایستاده برخورد می‌کند.

پس در نهایت ‌‌۲ نفر مورد اصابت گلوله قرار گرفته و کشته می‌شوند.

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

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

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

سوال مینو از این قرار است:

تعداد $n$ چندضلعی در صفحه‌ی مختصات قرار داده‌ شده‌است. خواسته‌ی مینو از افراد پیدا کردن کوچک‌ترین دایره‌کوچیکه‌ی ممکن برای این چندضلعی‌ها بعد از انجام حداکثر ‌‌$k$ تا عملیات کلّه‌شکنی است.

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

مینو برای چند ضلعی شماره‌ی $i$ نقطه‌ی $p_i$ را در نظرگرفته و عملیات کلّه‌شکنی را به این صورت تعریف می‌کند:

1. انتخاب یکی از چندضلعی‌ها
2. نصف کردن فاصله‌ی رئوس چندضلعی تا نقطه‌ای که برای آن چندضلعی در نظر گرفته است.

به غول‌پیکرها برای حل سؤال مینو کمک کنید.

ورودی🔗

خط اوّل ورودی شامل دو عدد $n$ و $k$ است که با فاصله از هم جدا شده‌اند.

پس از آن $n$ چندضلعی به صورت زیر ورودی داده می‌شود:

1. ابتدا تعداد رئوس چندضلعی $m_i$ داده می‌شود.
2. سپس $x_{p_i}$ و $y_{p_i}$ مختصات نقطه‌ای که مینو برای آن چندضلعی درنظر گرفته داده‌می‌شود.
3. بعد از آن $m_i$ خط داده می‌شود که هر خط شامل $x_{i, j}$ و $y_{i, j}$ مختصات رأس ‌$j$اُم چندضلعی است.

تضمین می‌شود تمام اعداد ورودی صحیح هستند.

توجه کنید که منظور از چندضلعی با یک رأس، یک رأسِ تنها و منظور از چند ضلعی با دو رأس، دو رأس که با یک ضلع به‌هم متصل شده‌اند است. $1\leq n, k \leq 100\ 000$ $1\leq m_i \leq 20$ $-10^9 \leq x_{p_i}, y_{p_i} \leq 10^9$ $-10^9 \leq x_{i, j}, y_{i, j} \leq 10^9$ $\Sigma_{i=1}^{n} m_i \leq 100\ 000$

خروجی🔗

در خروجی تنها یک عدد، شعاع کوچکترین دایره‌کوچیکه‌ی ممکن بعد از انجام حداکثر $k$ تا عملیات کلّه‌شکنی، را با دقیقاً ۶ رقم اعشار چاپ کنید.

مثال🔗

ورودی نمونه🔗

2 2
2
2 0
3 0
1 0
2
-2 0
-1 0
-3 0

خروجی نمونه🔗

2.500000

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

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

از این رو سراغ شجره‌نامه‌ی افراد قبیله می‌رود. شجره‌نامه یک درخت $n$ رأسی است که از رأس شماره‌ی ۱ ریشه‌دار شده و هر رأس آن یکی از افراد قبیله است.

در این قبیله مقدار بدبختی هر غول‌پیکر با یک عدد نشان داده می‌شود.

هم‌چنین افراد این قبیله به علّت اعتقاد راسخی که به «فرزند بیشتر، زندگیِ شادتر» دارند؛ اعتبار هر فرد را برابر تعداد نوادگان آن فرد در شجره‌نامه قرار می دهند.

پگاه می‌خواهد مأموران مخصوص خود را به گونه‌ای انتخاب کند که مجموع بدبختی آن‌ها از $k$ بیشتر نباشد و هیچ مأموری از نوادگان مأمور دیگری نباشد.

مجموع اعتبار مأموران ویژه‌ی پگاه حداکثر چقدر می‌تواند باشد؟

ورودی🔗

در خط اوّل دو عدد $n$ تعداد افراد قبیله و $k$ داده می‌شود که با یک فاصله از هم جدا شده‌اند.

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

در خط آخر ورودی ‌$n$ عدد داده می‌شود که عدد $i$اُم میزان بدبختی غول‌پیکر $i$اُم را نشان می‌دهد. مقدار بدبختی هر فرد عددی طبیعی بین ۱ تا $10^9$ است. $1\leq n \leq 1\ 000$ $1 \leq k \leq 100$ $1 \leq u, v \leq n$

خروجی🔗

در خروجی یک عدد که حداکثر مجموع اعتبار مأموران مخصوص پگاه است را چاپ کنید.

مثال🔗

ورودی نمونه🔗

5 5
1 2
1 3
3 4
3 5
6 2 5 1 3

خروجی نمونه🔗

2

توضیح نمونه: اگر پگاه فقط غول‌پیکر شماره ۳ را انتخاب کند، مجموع اعتبار مأموران بیشینه و برابر ۲ خواهد بود.

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

همانطور که می‌دانید در قبیله‌ی غول‌پیکرها هر فرد یک عدد بدبختی و یک عدد اعتبار دارد. عدد بدبختی غول‌پیکر شماره $i$ را با $b_i$ و عدد اعتبار او را با $a_i$ نشان می‌دهیم.

فاصله‌ی عاطفی دو غول‌پیکر ‌$i$ و $j$ برابر است با: $f(i, j) = |a_i - a_j| + |b_i - b_j|$

سه غول‌پیکر $i$ و $j$ و $l$ تشکیل یک اکیپ می‌دهند اگر مجموع فواصل عاطفی دو به دوی آن‌ها از $k$ بیشتر نباشد. به عبارتی: $f(i, j) + f(i, l) + f(j, l) \leq k$

مینو از وقتی که به هوش و ذکاوت سرشار افراد قبیله پی برده‌است؛ می‌خواهد تعداد اکیپ‌های قبیله را بداند. به او کمک کنید.

ورودی🔗

در خط اوّل ورودی عدد $n$ تعداد اعضای قبیله و $k$ آمده‌اند که با یک فاصله از هم جدا شده‌اند.

در $n$خط بعد در هر خط دو عدد $a_i$ و $b_i$ آمده‌است.

$1 \leq n \leq 2\ 000$ $1 \leq k \leq 4 \times 10^9$ $0 \leq a_i, b_i \leq 10^9$

خروجی🔗

در خروجی یک عدد که تعداد اکیپ‌های غول‌پیکرهاست را چاپ کنید.

مثال🔗

ورودی نمونه🔗

5 10
4 2
5 3
1 1
3 1
2 4

خروجی نمونه🔗

5

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

غول‌پیکرها به همراه مینو و پگاه بعد از یک سفر سخت و طولانی بالأخره به شهرجادویی رسیدند. سُس بیژن، شکلات پارمیدا، روغن لادن، شیرین‌عسلِ جذّاب و همه‌ی خوراکی‌های دیگر از آن‌ها استقبال کردند. ولی بلافاصله بعد از اتمام پذیرایی، ساکنین شهرجادویی مشکلی که به تازگی برای آن‌ها پیش آمده را با پگاه و مینو مطرح کردند تا شاید بتوانند آن را حل کنند.

شهر جادویی شامل $n$ شهرستان است که بعضی آن‌ها با یک جاده به‌هم متصل شده‌اند. می‌دانیم بین هر دو شهرستان دقیقاً یک مسیر وجود دارد. (هر مسیر از تعدادی جاده تشکیل شده است.) به علاوه، هر شهرستان در شهرجادویی تعدادی درخت آلبالو دارد.

ساکنان شهر جادویی $q$ مشکل دارند، که در مشکل $i$اُم می خواهند بدانند اگر مسیر شهرستان ‌$u_i$ و $v_i$ را با شروع از $u_i$ و $k_i$ تا $k_i$ تا طی کنند تاجایی که دیگر نتوانند به مسیر خود ادامه دهند در مجموع چندتا درخت آلبالو می‌بینند. (اگر از همه‌ی شهرستان‌های مسیر بین ‌$u_i$ و $v_i$ عبور کنیم؛ مسیر را یکی‌یکی طی کرده‌ایم.)

همچنین میدانیم اگر $ans_i$ پاسخ مشکل $i$اُم باشد: $k_1 = x_1$ $k_i = ans_{i-1}\oplus x_i \ \ \ \ \ i > 1$ به مینو و پگاه کمک کنید تا خودشان را به ساکنان شهرجادویی ثابت کنند.

ورودی🔗

در خط اوّل ورودی دو عدد $n$ و $q$ داده می‌شود. $1 \leq n, q \leq 100\ 000$ در خط بعد $n$ عدد آمده که عدد $i$اُم $t_i$ (تعداد درخت‌های آلبالوی شهرستان$i$) است. $1 \leq t_i \leq 1\ 000\ 000\ 000$

پس از آن در $n-1$ خط جاده‌های شهر جادویی داده می‌شوند. هر خط شامل دو عدد $u$ و $v$ است که شهرستان‌های دو سر جاده را مشخص می‌کنند. $1 \leq u,v \leq n$ سپس در $q$ خط بعد در هر خط سه عدد $u_i$ و $v_i$ و $x_i$ می‌آید که معرف مشکل ‌‌‌$i$اُم هستند. $1 \leq u_i, v_i \leq n$ $1 \leq x_i \leq 10^{15}$

خروجی🔗

خروجی شامل $q$ خط است که خط $i$اُم آن برابر $ans_i$ می‌باشد.

مثال🔗

ورودی نمونه🔗

4 5
1 2 3 4
1 2
2 3
1 4
1 4 1
1 4 1
1 2 2
1 3 4
1 4 3

خروجی نمونه🔗

5
1
1
1
1