کلید چراغ

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

چراغی داریم که با تغییر وضعیت یک کلید، از روشن به خاموش و بالعکس تغییر می‌کند. وضعیت روشنایی این چراغ را در $n$ ثانیه متوالی داریم و می‌دانیم در ثانیه $i$ ام از این $n$ ثانیه چراغ روشن بوده یا خاموش. حال وظیفه شما این است که بگویید این چراغ در مجموع چند بار تغییر وضعیت داده است.

ورودی🔗

در خط اول ورودی به شما عدد $n$ داده می‌شود.

در $n$ خط بعدی، در هر خط به شما یک عدد داده می‌شود که اگر عدد داده‌شده در $i$ امین خط برابر با $1$ بود یعنی چراغ در ثانیه $i$ ام از این $n$ ثانیه روشن و اگر برابر با $0$ بود یعنی چراغ در آن ثانیه خاموش بوده‌ است. $1 \le n \le 1\ 000$

خروجی🔗

خروجی شامل یک عدد است که بیانگر تعداد دفعاتی است که کلید تغییر وضعیت می‌دهد.

مثال🔗

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

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

توضیح نمونه: در این نمونه چراغ یک بار در ثانیه ۳ و یک بار در ثانیه ۴ تغییر وضعیت می‌دهد.

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دیواری داریم که به شکل یک مستطیل $n \times m$ است. هر خانه از این دیوار یا آجری است یا شیشه‌ای. اگر آجری باشد،‌ قسمتی از بدنه‌ دیوار و اگر شیشه‌ای باشد، قسمتی از پنجره است. پنجره موجودی کاملا شیشه‌ای است که در بین آجرها قرار دارد. یک پنجره را استاندارد می‌گوییم اگر به شکل یک مستطیل باشد. همچنین می‌گوییم دو خانه شیشه‌ای در یک پنجره قرار دارند، اگر و تنها اگر، از یکی از آن‌ها بتوان با تعدادی حرکت به خانه دیگر رسید به‌طوری که در هر حرکت به یک خانه شیشه‌ای که با خانه فعلی ضلع مشترک دارد، برویم. در ورودی یک دیوار به شما داده می‌شود که تضمین می‌شود محیط آن کاملا از آجر تشکیل شده است. حال شما باید تشخیص دهید که تمامی پنجره‌های دیوار استاندارد هستند یا خیر. # ورودی در خط اول ورودی به شما دو عدد $n$ و $m$ داده می‌شوند که نشان‌دهنده ابعاد دیوار هستند. در $i$امین خط از $n$ خط بعدی، یک رشته به طول $m$ متشکل از `+` و `*` آمده است که $j$امین عنصر آن، نشان‌دهنده نوع خانه واقع در تقاطع سطر $i$ام و ستون $j$ام می‌باشد. اگر این عنصر `+` باشد، نشان‌دهنده وجود پنجره و در غیر این صورت نشان‌دهنده وجود آجر است. $$2 \le n, m \le 50$$ # خروجی اگر در دیوار داده شده، پنجره‌ای غیر استاندارد وجود دارد، چاپ کنید `bad wall`. در غیر این صورت عبارت `good wall` را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 2 3 *** *** ``` ## خروجی نمونه ۱ ``` good wall ``` **توضیح نمونه:** در این نمونه هیچ پنجره‌ای نداریم، بنابراین دیوار یک دیوار خوب است. ## ورودی نمونه ۲ ``` 6 5 ***** *+*+* ***+* *++** *++** ***** ``` ## خروجی نمونه ۲ ``` good wall ``` **توضیح نمونه**: در این نمونه سه پنجره داریم که هر سه آن‌ها مستطیلی هستند. ## ورودی نمونه ۳ ``` 4 4 **** *+** *++* **** ``` ## خروجی نمونه ۳ ``` bad wall ``` **توضیح نمونه:** در این نمونه تنها یک پنجره وجود دارد که به شکل مستطیل نیست.

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

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

دیواری داریم که به شکل یک مستطیل $n \times m$ است. هر خانه از این دیوار یا آجری است یا شیشه‌ای. اگر آجری باشد،‌ قسمتی از بدنه‌ دیوار و اگر شیشه‌ای باشد، قسمتی از پنجره است.

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

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

ورودی🔗

در خط اول ورودی به شما دو عدد $n$ و $m$ داده می‌شوند که نشان‌دهنده ابعاد دیوار هستند.

در $i$ امین خط از $n$ خط بعدی، یک رشته به طول $m$ متشکل از + و * آمده است که $j$ امین عنصر آن، نشان‌دهنده نوع خانه واقع در تقاطع سطر $i$ ام و ستون $j$ ام می‌باشد. اگر این عنصر + باشد، نشان‌دهنده وجود پنجره و در غیر این صورت نشان‌دهنده وجود آجر است. $2 \le n, m \le 50$

خروجی🔗

اگر در دیوار داده شده، پنجره‌ای غیر استاندارد وجود دارد، چاپ کنید bad wall. در غیر این صورت عبارت good wall را خروجی دهید.

مثال🔗

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

2 3
***
***

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

good wall

توضیح نمونه: در این نمونه هیچ پنجره‌ای نداریم، بنابراین دیوار یک دیوار خوب است.

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

6 5
*****
*+*+*
***+*
*++**
*++**
*****

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

good wall

توضیح نمونه: در این نمونه سه پنجره داریم که هر سه آن‌ها مستطیلی هستند.

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

4 4
****
*+**
*++*
****

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

bad wall

توضیح نمونه: در این نمونه تنها یک پنجره وجود دارد که به شکل مستطیل نیست.

کوچکِ بزرگ

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

تابع $F(x)$ را تعریف می‌کنیم کوچکترین عدد طبیعی که دقیقا $x$ تا مقسوم‌علیه داشته باشد. برای مثال $F(3)$ برابر با ۴ و $F(6)$ برابر با ۱۲ است.

حال یک عدد $n$ به شما داده می‌شود و شما باید مقداری را خروجی دهید که در میان تمام اعداد طبیعی کمتر مساوی $n$ ، بیشترین مقدار خروجی را در تابع $F$ داشته باشد. در صورتی که چند عدد مختلف ویژگی مورد نظر را داشتند، بزرگترین آن‌ها را خروجی دهید.

به عنوان مثال می‌دانیم که $F(6) = 12$ ، زیرا تعداد مقسوم‌علیه‌های اعداد ۱ تا ۱۲ به ترتیب برابر است با ۱، ۲، ۲، ۳، ۲، ۴، ۲، ۴، ۳، ۴، ۲، ۶. بنابراین عدد ۱۲ کوچکترین عددی است که دقیقا ۶ مقسوم‌علیه دارد.

ورودی🔗

در تنها خط ورودی به شما عدد $n$ داده می‌شود. $1 \le n \le 100\ 000$

خروجی🔗

در تنها خط خروجی عدد مورد نظر مسئله را چاپ کنید.

مثال🔗

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

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

توضیح نمونه: در این نمونه به ترتیب از ۱ تا ۳ خروجی $F$ برابر با ۱ و ۲ و ۴ هست. بنابراین عددی که بیشترین مقدار $F$ را دارد ۳ است.

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

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

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

مسیر عجیب

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

یک گراف کامل $n$ راسی $G$ به شما داده می‌شود که $m$ تا از راس‌های آن، به صورت دلخواه با اعداد $1$ تا $m$ شماره‌گذاری شده‌اند و $n - m$ راس دیگر گراف، با یکدیگر یکسان هستند و همگی آن‌ها شماره $0$ دارند.

همچنین $e$ یال از گراف $G$ حذف شده‌ است به طوری که شماره راس دو سر هر کدام از این یال‌ها بین $1$ و $m$ می‌باشد.

شما باید تعداد مسیر‌های به طول $n - 1$ در گراف $n$ راسی $G$ (در واقع تعداد مسیرهای هامیلتونی) را خروجی دهید.

دو مسیر در گراف متفاوت درنظر گرفته می‌شوند اگر دنباله‌های راسی آن‌ها متفاوت باشند، برای مثال دو مسیر $1\ 0\ 2\ 3$ و $1\ 0\ 2\ 3$ با یکدیگر یکسان و دو مسیر $0\ 2\ 1\ 0$ و $0\ 1\ 2\ 0$ با یکدیگر متفاوت هستند.

از آنجایی که جواب ممکن است بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ چاپ کنید.

ورودی🔗

در خط اول ورودی به ترتیب سه عدد $n$ و $m$ و $e$ داده می‌شود.

در $e$ خط بعدی ورودی, در هر خط دو عدد $u$ و $v$ به شما داده می‌شود که بیانگر این است که یال بین دو راسی که با $u$ و $v$ شماره‌گذاری شده‌اند حذف شده‌است.

تضمین می‌شود که هر یال حداکثر یک‌بار حذف می‌شود. $1 \le n \le 10^{18}$ $1 \le m \le 16$ $m \le n$ $0 \le e \le \frac{m(m - 1)}{2}$ $1 \le u, v \le m$

خروجی🔗

در تنها خط خروجی، یک عدد خروجی دهید که بیانگر تعداد مسیرهای به طول $n - 1$ در گراف $G$ به باقیمانده $10^9 + 7$ می‌باشد.

مثال🔗

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

4 3 2
1 2
1 3

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

مسیرهای هامیلتونی متفاوت عبارت‌اند از 1 0 3 2 و 1 0 2 3 و 2 3 0 1 و 3 2 0 1.

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

3 3 1
2 3

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

مسیرهای هامیلتونی متفاوت عبارت‌اند از 2 1 3 و 3 1 2.

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- جدولی $n \times m$ داریم که برخی از خانه‌های آن مسدود شده‌اند. می‌دانیم که سطرهای این جدول از بالا به پایین با ۱ تا $n$ و ستون‌های این جدول از چپ به راست با ۱ تا $m$ شماره‌گذاری شده‌اند. حال فرض کنید مربعی بر روی این جدول داریم و می‌خواهیم آن را به مکان دیگری از جدول انتقال دهیم. برای این کار در هر حرکت می‌توانیم مربع را یک واحد به سمت چپ یا راست یا بالا یا پایین انتقال دهیم، به‌طوری که از جدول خارج نشود و هیچ خانه مسدودی وارد آن نشود. مربع $A$ را از مربع $B$ دسترس‌پذیر می‌گوییم اگر بتوانیم با تعدادی حرکت بر روی $A$، آن را به $B$ برسانیم. حال در ورودی $q$ پرسش آمده است. در هر پرسش دو خانه **متفاوت** از جدول برای شما مشخص شده‌اند و شما باید بزرگترین $k$ را خروجی دهید که مربع $k \times k$ با گوشه پایین چپ خانه اول، از مربع $k \times k$ با گوشه پایین چپ خانه دوم، دسترس‌پذیر باشد و همچنین هیچ‌کدام از دو مربع مورد‌نظر دارای خانه مسدود نباشند. دقت کنید که $k$ ممکن است صفر نیز باشد. # ورودی در خط اول ورودی به شما سه عدد $n$ و $m$ و $q$ داده می‌شود. در $i$امین خط از $n$ خط بعدی، یک رشته به طول $m$ متشکل از `.` و‍ `*` آمده است که $j$امین عنصر آن، نشان‌دهنده مسدود بودن یا نبودن خانه واقع در تقاطع سطر $i$ام و ستون $j$ام می‌باشد. اگر این عنصر `*` باشد، نشان‌دهنده مسدود بودن خانه مورد‌نظر و در غیر این صورت نشان‌دهنده خالی بودن آن می‌شود. در $i$امین خط از $q$ خط بعدی، چهار عدد $x$ و $y$ و $x_2$ و $y_2$ آمده‌ است که به ترتیب نشان‌دهنده شماره سطر خانه اول، شماره ستون خانه اول، شماره سطر خانه دوم و شماره ستون خانه دوم می‌باشد. تضمین می‌شود هیچ یک از دو خانه داده شده، مسدود نمی‌باشد. $$1 \le n, m \le 2\ 000$$ $$1 \le q \le 1\ 000\ 000$$ $$1 \le x, x_2 \le n$$ $$1 \le y, y_2 \le m$$ # خروجی در خط $i$ام خروجی، پاسخ پرسش $i$ام را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 4 3 .... .... .... .... 2 3 3 2 1 1 1 2 4 1 4 2 ``` ## خروجی نمونه ۱ ``` 2 1 3 ``` ## ورودی نمونه ۲ ``` 6 7 3 ....... ..****. *...... ***...* .*..... *.*.*.* 3 2 4 5 5 4 4 5 6 2 1 1 ``` ## خروجی نمونه ۲ ``` 1 2 0 ```

گذراندن مربع

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

جدولی $n \times m$ داریم که برخی از خانه‌های آن مسدود شده‌اند. می‌دانیم که سطرهای این جدول از بالا به پایین با ۱ تا $n$ و ستون‌های این جدول از چپ به راست با ۱ تا $m$ شماره‌گذاری شده‌اند.

حال فرض کنید مربعی بر روی این جدول داریم و می‌خواهیم آن را به مکان دیگری از جدول انتقال دهیم. برای این کار در هر حرکت می‌توانیم مربع را یک واحد به سمت چپ یا راست یا بالا یا پایین انتقال دهیم، به‌طوری که از جدول خارج نشود و هیچ خانه مسدودی وارد آن نشود. مربع $A$ را از مربع $B$ دسترس‌پذیر می‌گوییم اگر بتوانیم با تعدادی حرکت بر روی $A$ ، آن را به $B$ برسانیم.

حال در ورودی $q$ پرسش آمده است. در هر پرسش دو خانه متفاوت از جدول برای شما مشخص شده‌اند و شما باید بزرگترین $k$ را خروجی دهید که مربع $k \times k$ با گوشه پایین چپ خانه اول، از مربع $k \times k$ با گوشه پایین چپ خانه دوم، دسترس‌پذیر باشد و همچنین هیچ‌کدام از دو مربع مورد‌نظر دارای خانه مسدود نباشند. دقت کنید که $k$ ممکن است صفر نیز باشد.

ورودی🔗

در خط اول ورودی به شما سه عدد $n$ و $m$ و $q$ داده می‌شود.

در $i$ امین خط از $n$ خط بعدی، یک رشته به طول $m$ متشکل از . و‍ * آمده است که $j$ امین عنصر آن، نشان‌دهنده مسدود بودن یا نبودن خانه واقع در تقاطع سطر $i$ ام و ستون $j$ ام می‌باشد. اگر این عنصر * باشد، نشان‌دهنده مسدود بودن خانه مورد‌نظر و در غیر این صورت نشان‌دهنده خالی بودن آن می‌شود.

در $i$ امین خط از $q$ خط بعدی، چهار عدد $x$ و $y$ و $x_2$ و $y_2$ آمده‌ است که به ترتیب نشان‌دهنده شماره سطر خانه اول، شماره ستون خانه اول، شماره سطر خانه دوم و شماره ستون خانه دوم می‌باشد. تضمین می‌شود هیچ یک از دو خانه داده شده، مسدود نمی‌باشد. $1 \le n, m \le 2\ 000$ $1 \le q \le 1\ 000\ 000$ $1 \le x, x_2 \le n$ $1 \le y, y_2 \le m$

خروجی🔗

در خط $i$ ام خروجی، پاسخ پرسش $i$ ام را چاپ کنید.

مثال🔗

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

4 4 3
....
....
....
....
2 3 3 2
1 1 1 2
4 1 4 2

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

2
1
3

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

6 7 3
.......
..****.
*......
***...*
.*.....
*.*.*.*
3 2 4 5
5 4 4 5
6 2 1 1

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

1
2
0

+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به شما یک گراف همبند $n$ راسی با $n - 1$ یال داده می‌شود. شما باید $q$ عملیات را روی این گراف انجام دهید. هرکدام از این عملیات‌ها به یکی از دو صورت می‌باشد: - `1 v` - `2 u v` عملیات اول به این صورت است که باید راس $v$ را از گراف باقیمانده حذف کنید. عملیات دوم نیز به این صورت است که باید یال بین دو راس $u$ و $v$ را از گراف باقیمانده حذف کنید. همچنین پس از اعمال هر عملیات باید مجموع فواصل هر دو راسی که درون یک مولفه هستند را خروجی دهید. # ورودی در خط اول ورودی به شما دو عدد $n$ و $q$ داده می‌شود که به ترتیب بیانگر تعداد راس‌های گراف و تعداد عملیات‌ها می‌باشند. در $n - 1$ خط بعدی، در هر خط دو عدد $u$ و $v$ داده می‌شود که بیانگر این است که بین راس‌های $u$ و $v$ یک یال وجود دارد. در $q$ خط بعدی، در هر خط به شما یک عملیات داده می‌شود که یا از نوع اول می‌باشد یا از نوع دوم می‌باشد. تضمین می‌شود گراف ورودی همبند است و همچنین در هنگام عملیات های نوع اول و دوم، به ترتیب راس و یال مورد نظر در گراف موجود است. $$ 1 \le n \le 500\ 000$$ $$ 1 \le q \le 2n - 1 $$ $$ 1 \le u, v \le n $$ $$ u \neq v $$ # خروجی خروجی شامل $q$ خط است که خط $i$ام برابر با مجموع فواصل هر دوراسی که درون یک مولفه هستند، پس از اعمال عملیات $i$ام می‌باشد. # مثال ## ورودی نمونه ۱ ``` 4 1 1 2 2 3 3 4 2 1 2 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 5 2 1 2 2 3 3 4 3 5 2 2 3 1 3 ``` ## خروجی نمونه ۲ ``` 5 1 ```

فاصله درختی

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

به شما یک گراف همبند $n$ راسی با $n - 1$ یال داده می‌شود. شما باید $q$ عملیات را روی این گراف انجام دهید.

هرکدام از این عملیات‌ها به یکی از دو صورت می‌باشد:

1 v
2 u v

عملیات اول به این صورت است که باید راس $v$ را از گراف باقیمانده حذف کنید. عملیات دوم نیز به این صورت است که باید یال بین دو راس $u$ و $v$ را از گراف باقیمانده حذف کنید. همچنین پس از اعمال هر عملیات باید مجموع فواصل هر دو راسی که درون یک مولفه هستند را خروجی دهید.

ورودی🔗

در خط اول ورودی به شما دو عدد $n$ و $q$ داده می‌شود که به ترتیب بیانگر تعداد راس‌های گراف و تعداد عملیات‌ها می‌باشند.

در $n - 1$ خط بعدی، در هر خط دو عدد $u$ و $v$ داده می‌شود که بیانگر این است که بین راس‌های $u$ و $v$ یک یال وجود دارد.

در $q$ خط بعدی، در هر خط به شما یک عملیات داده می‌شود که یا از نوع اول می‌باشد یا از نوع دوم می‌باشد.

تضمین می‌شود گراف ورودی همبند است و همچنین در هنگام عملیات های نوع اول و دوم، به ترتیب راس و یال مورد نظر در گراف موجود است. $1 \le n \le 500\ 000$ $1 \le q \le 2n - 1$ $1 \le u, v \le n$ $u \neq v$

خروجی🔗

خروجی شامل $q$ خط است که خط $i$ ام برابر با مجموع فواصل هر دوراسی که درون یک مولفه هستند، پس از اعمال عملیات $i$ ام می‌باشد.

مثال🔗

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

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

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

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

5
1