+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر همه است؛ حتی به فکر افراد معتاد. برای همین او از همه‌ی معتاد‌های سراسر کشور دعوت کرده که به پیش او بروند تا فکری به حالشان بکند. اولین معتاد امروز به پیش آقای خوش‌قلب رفت. آقای خوش‌قلب ابتدا باید "سطح اعتیاد" این فرد را معین کند. برای این کار، از شخص معتاد یک تست گرفته شد. آقای خوش‌قلب تعداد خیلی زیادی جسم روی میز گذاشت و به معتاد گفت که اجسام یکسان را بشمرد و روی کاغذی بنویسد از هر جسم چندتا روی میز موجود است. آقای خوش‌قلب سطح اعتیاد افراد را بصورت عددی طبیعی مشخص می‌کند و می‌دانیم که یک معتاد با سطح اعتیاد $k$، هر جسم روی میز را $k$بار می‌بیند. (پس به ازای هر جسم موجود عددی که روی کاغذ می‌نویسد $k$ برابر تعداد واقعی است.) حال آقای خوش‌قلب به خانه‌ی خود رفته و حین دیدن بازی‌های پرهیجان المپیک، می‌خواهد که سطح اعتیاد معتاد را بدست آورد. اما ناگهان متوجه می‌شود که یادش نمی‌آید چه تعداد از هر جسم روی میز بوده! با شتاب به سوی کیف خود رفته و برگه‌ی نوشته‌های معتاد را بیرون می آورد. او با تمام خوش‌قلبی خود، می‌خواهد بفهمد که حداقل چند جسم روی میز بوده است تا کمترین مقدار هزینه به مسئول چیدمان اجسام روی میز بدهد! (کمی خسیس هم هست) حال خوش‌قلب به سراغ شما آمده و با دادن اعداد نوشته‌شده روی کاغذ معتاد به شما، از شما می‌خواهد که بگویید کمترین مقدار ممکن برای تعداد اجسام روی میز چه قدر میتوانسته باشد. # ورودی در سطر ورودی یک عدد $n$ آمده است که نمایانگر تعداد اعداد روی کاغذ معتاد است. (که برابر تعداد اجسام مختلف روی میز است.) سپس در سطر دوم ورودی $n$ عدد آمده است که با فاصله از هم جدا شده‌اند و نمایانگر اعداد نوشته شده روی کاغذ هستند. $$ 1 \le n \le 1\ 000\ 000 $$ اعداد روی کاغذ کوچکتر مساوی $1\ 000\ 000\ 000$ هستند. # خروجی خروجی باید شامل یک عدد باشد که برابر کمترین تعداد اجسام ممکن روی میز است. # مثال ## ورودی نمونه ۱ ``` 3 5 5 10 ``` ## خروجی نمونه ۱ ``` 4 ``` اگر سطح اعتیاد معتاد برابر ۵ باشد، می‌توان گفت روی میز ۴ جسم بوده‌ است که ۲ تای آن یک شکل بودند. ## ورودی نمونه ۲ ``` 3 1 2 3 ``` ## خروجی نمونه ۲ ``` 6 ``` چون معتاد از یکی از اجسام تنها یک دانه دیده، سطح اعتیاد او تنها می‌تواند ۱ باشد پس همه‌ی اجسام گفته‌شده توسط معتاد روی میز موجود هستند؛ سه نوع جسم و از نوع اول یک دانه، از نوع دوم ۲ تا و از نوع سوم، ۳ تا.

+ محدودیت ز مان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای مهندس می‌خواهد یک گراف «مهندسی‌ساز» بسازد. به یک گراف وزن‌دار مهندسی‌ساز می‌گوییم اگر بتوان طوری وزن تعدادی از یال‌هایش را مقدار مثبتی زیاد کرد که هیچ‌کدام از `MSF`های گراف سابق در گراف جدید `MSF` نباشند. آقای مهندس در حال ساختن گرافش است و در هر مرحله یک یال جدید به آن اضافه می‌کند. شما باید در هر مرحله به او بگویید گرافش مهندسی‌ساز است یا نه. به یک زیرگراف از گرافمان، جنگل فراگیر می‌گوییم اگر دور نداشته باشد و بین هر دو راسی که در درون یک مؤلفه قرار دارند، با یال‌های این زیرگراف مسیر وجود داشته باشد. به زیرجنگلی که جمع وزن‌ یال‌هایش کمینه باشد، `Minimum Spanning Forest` یا `MSF` می‌گوییم. ## ورودی در خط اول ورودی دو عدد $n$ و $m$ آمده‌اند که $n$ تعداد راس‌های گراف و $m$ تعداد یال‌های آن را نشان می‌دهد. در $m$ خط بعد در هر خط سه عدد $u_i$ و $v_i$ و $w_i$ آمده‌است که اضافه شدن یالی به وزن $w_i$ بین دو راس $u_i$ و $v_i$ را نشان می‌دهد. دقت کنید که یال‌ها ممکن است چندگانه باشند. + $1 \le n, m \le 10^5$ + $1 \le u_i, v_i \le n$ + $1 \le w_i \le 10^9$ ## خروجی در تنها خط خروجی یک رشته به طول $m$ از `0` و `1` چاپ کنید که `1` بودن حرف $i$ام آن به معنی مهندسی‌ساز بودن گراف بعد از اضافه کردن یال $i$ام است. ## مثال ورودی نمونه ``` 6 7 1 2 2 1 3 2 3 2 2 5 6 1 3 5 1 1 4 1 1 5 1 ``` خروجی نمونه ``` 0000001 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- کریم یک کودک ۵ ساله است و در گردهمایی مهدکودکی‌ها شرکت می‌کند. کریم و $n - 1$ نفر از هم مهدی‌هایش دور یک میز دایره‌ای شکل جهت صرف دوغ گرد هم آمده‌اند. آن‌ها را با شروع از کریم و بصورت ساعتگرد، با اعداد 1 تا $n$ شماره‌گذاری می‌کنیم. بین برخی از این کودکان رابطه‌ی دوطرفه‌ی دوستی برقرار است. پس از انتظارهای بسیار، یک عدد پارچ دوغ به کنار میز آورده می‌شود. همه‌ی این $n$ نفر می‌خواهند از این دوغ بنوشند. روند دوغ‌رسانی در این قبیل گردهمایی‌ها به این صورت است که پارچ دوغ ابتدا به یکی از افراد دور میز داده می‌شود. هرکسی که پارچ به دستش میرسد پس از نوشیدن مقداری از آن، پارچ دوغ را به یکی از دوستانش **که هنوز دوغ نخورده است** می‌دهد تا وقتی که همه از آن بنوشند. دقت کنید که بخاطر سن کم، هیچ کس پارچ دوغ را به کسی که با او دوست نیست نمی‌دهد. به دلیل بزرگ بودن میز و کوچک بودن کودکان، هرکس برای رساندن دوغ به نفر بعدی به روی میز میرود و هنگام راه رفتن روی مسیر بین جایگاه نشستن خود و نفر بعدی، خطی از دوغ روی میز باقی می‌گذارد. روی هیچ نقطه‌ای از مسیری که یک کودک به سمت کودک بعدی طی می‌کند نباید از قبل دوغی ریخته شده باشد؛ چون کودک هنگام حمل دوغ لیز خورده و خاطره‌ی بدی از گردهمایی بجا خواهد ماند. حال با دانستن روابط دوستی بین این کودکان، بگویید که این ها به چه ترتیبی می‌توانند دوغ بخورند که به همه دوغ برسد و هیچکس هنگام حمل دوغ زمین نخورد. (یا بگویید که امکان ندارد.) # ورودی خط اول ورودی شامل عدد $n$ است. در خط دوم ورودی عدد $m$ که بیانگر تعداد رابطه های دوستی بین کودکان است. هریک از $m$ خط بعدی یک جفت عدد $u, v$ آمده که یعنی کودک شماره $u$ و کودک شماره $v$ با هم دوست هستند. $$3 \le n \le 1000$$ $$0 \le m \le \frac{n \times (n-1)}2$$ # خروجی اگر امکان ندارد که به همه با شرایط گفته شده دوغ برسد، تنها خط خروجی باید شامل عدد $-1$ باشد. در غیر این صورت خروجی برنامه باید ترتیبی صحیح از دوغ خوردن افراد باشد که در $n$ خط آمده است. در صورت وجود چند ترتیب درست، یکی را به دلخواه خروجی دهید. # ورودی نمونه ۱ ``` 7 9 1 4 5 1 1 7 5 6 2 3 3 4 2 6 4 6 6 7 ``` # خروجی نمونه ۱ ``` 2 3 4 1 7 6 5 ``` # ورودی نمونه ۲ ``` 4 3 1 2 2 4 1 3 ``` # خروجی نمونه ۲ ``` -1 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول پرست است، جهت صرفه‌جویی در تعداد حروف پیامک‌هایش به فشرده‌سازی رشته‌ها روی آورده. روش عمو برای فشرده‌سازی به این صورت است: که او در ابتدا جایگشتی از اعداد ۱, ۲, ..., $k$ انتخاب میکند. سپس رشته‌ی خود را به دسته های پشت سر هم $k$ حرفی تقسیم میکند (طول رشته باید به $k$ بخش‌پذیر باشد) و روی هر دسته از حروف، جایگشت خود را اعمال میکند. سپس رشته‌ی بدست آمده را بوسیله‌ی روش RLE که در ادامه توضیح داده خواهد شد، فشرده میکند. اعمال جایگشت $p$ روی یک دسته از $k$ حرف یعنی حرف $p_1$م را در جایگاه اول قرار داده، حرف $p_2$م را در جایگاه دوم و... برای مثال اعمال جایگشت {۲ ,۴ ,۱ ,۳} روی رشته‌ی $abcd$ آن را تبدیل به $cadb$ میکند. اعمال این جایگشت با دسته دسته کردن روی رشته‌ی $abcdefgh$، رشته‌ی $cadbgehf$ را نتیجه میدهد. رشته‌ی جایگشت داده شده توسط RLE (یا run-length encoding) فشرده میشود. جهت جلوگیری از محاسبات پیچیده، طول رشته‌ی فشرده‌شده را برابر تعداد گروه حرف‌های برابر پشت سر هم درنظر میگیریم. برای مثال طول رشته‌ی $aabcaa$ پس از فشرده‌شدن توسط RLE را ۴ در نظر میگیریم. (یک گروه ۲ حرفی a، یک گروه تک حرفی b، یک گروه تک حرفی c و یک گروه ۲ حرفی a) عمو میخواهد پیامکی را با روش گفته شده فشرده کرده و بفرستد. واضح است که طول رشته‌ی نهایی به جایگشت انتخاب‌شده مربوط است. شما با داشتن متن پیامک عمو، جایگشتی انتخاب کنید که پس از فشرده‌سازی بوسیله‌ی آن طول پیامک کمینه شود و این طول کمینه را خروجی دهید. # ورودی سطر اول تنها شامل عدد $k$ است. در سطر بعدی پیامک عمو بصورت یک رشته از حروف کوچک انگلیسی به طول حداکثر ۵۰۰۰۰ آمده است. $$2 \le k \le 16$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین طول ممکن برای پیامک عمو است. # ورودی نمونه ``` 4 abcabcabcabc ``` # خروجی نمونه ``` 7 ``` در این مثال با انتخاب جایگشت {۲ ,۳ ,۴ ,۱} نتیجه‌ی بهینه بدست می‌آید.

+ محدودیت ز مان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شرکت «بساز و بنداز» به تازگی پروژه‌ی رنگ‌آمیزی دیوار‌ بزرگ شهر را انجام داده‌است و آقای مهندس در حال جمع‌آوری داده‌های این پروژه است تا عملکرد شرکت خود را در این پروژه بسنجد. اگر دیوار بزرگ شهر را به صورت $n$ قسمت مساوی پشت‌سرهم در نظر بگیریم، یک داده به صورت $t\ l\ r\ c$ به این معنی است که در زمان $t$، رنگ قسمت‌های $l$-ام تا $r$-ام دیوار با رنگ $c$، رنگ‌آمیزی می‌شود. در حین جمع‌آوری داده‌ها سوال‌هایی به این شکل برای آقای مهندس پیش می‌آید: «دیوار $i$-ام در زمان $t$ به چه رنگی بوده است؟» دقت کنید که آقای مهندس داده‌ها را بر حسب زمان‌شان جمع‌آوری نمی‌کند. یعنی امکان دارد داده‌ها بر حسب زمان مرتب نباشند و آقای مهندس سوال‌ها را با توجه به داده‌هایی که تا قبل از پیش‌آمدن این سوال جمع‌آوری کرده، پاسخ می‌دهد. حال شما باید برنامه‌ای بنویسید که با گرفتن داده‌های مربوط به رنگ‌آمیزی و سوال‌های آقای مهندس، پاسخ سوال‌های آقای مهندس را در خروجی چاپ کند. رنگ همه‌ی قسمت‌های دیوار در ابتدای کار $0$ است. بنابراین اگر با داده‌های جمع‌آوری شده رنگ خانه‌ی سوال پرسیده‌شده معلوم نشود، پاسخ سوال $0$ است. ## ورودی در سطر اول ورودی دو عدد طبیعی $n$، تعداد قسمت‌های دیوار، و $q$، تعداد داده‌ها و پرسش‌ها، آمده است. در هر کدام از $q$ سطر بعدی، یا یک داده در مورد رنگ‌آمیزی دیوار و یا یک پرسش آمده است. + داده رنگ‌آمیزی: «`t l r c ~`»: دیوار $l$-ام تا $r$-ام دیوار در زمان $t$ به رنگ $c$، رنگ‌آمیزی می‌شود. + پرسش:‌ «`t x ?`»: دیوار $x$-ام در زمان $t$ با استفاده از اطلاعات کنونی، به چه رنگی است؟ تمامی زمان‌هایی که در ورودی آمده است متمایزند. + $2\le n,q \le 10^5$ + $1\le l\le r\le n$ + تمامی اعداد ورودی بین 1 تا $10^{9}$ هستند. ## خروجی سطر $i$-ام خروجی پاسخ پرسش $i$-ام آقای مهندس است. ## مثال ورودی نمونه ``` 4 6 ? 2 1 ~ 1 1 3 1 ? 3 1 ~ 5 2 4 2 ? 4 2 ? 6 2 ``` خروجی نمونه ``` 0 1 1 2 ```