دنباله تورج‌پسند

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

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

آقا تورج دنباله $a_1, a_2, .... , a_k$ از اعداد حسابی را دنباله‌ای خوب می‌داند اگر شرایط زیر برقرار باشد :‌

$0 \le a_1 \le d$ $2\le i \le k ,\ \ \mid a_i - a_{i - 1} \mid \le d$

آقا تورج مقادیر $d$ و $k$ را برای توک معین کرده است، اکنون توک باید باقی‌مانده تعداد دنباله‌های خوب را بر $10^9 + 7$ بیابد تا بتواند به خواستگاری پوپک برود.

ورودی🔗

در تنها خط ورودی به ترتیب دو عدد $k$ و $d$ آمده است. $0 \le d \le 2\ 000$ $1 \le k \le 100$

خروجی🔗

در تنها خط خروجی باقی مانده تعداد دنباله‌های خوب بر $10 ^ 9 + 7$ را چاپ کنید.

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

2 2

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

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

1 10

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پس از حل سوال قبلی،‌ توک خیلی خوشحال شده است. او می‌خواهد قرار خواستگاری را با آقا تورج هماهنگ کند که ناگهان غافلگیر می‌شود. پشت تلفن، آقا تورج به توک می‌گوید که پوپک خواستگار دیگری به نام صمد دارد ... آقا تورج برای اینکه بتواند داماد لایقش را انتخاب کند، یک مساله به توک و صمد گفته است که هرکس این مساله را زودتر حل کند، می‌تواند با پوپک ازدواج کند. آقا تورج فرمانده ارتش است. در راستای انجام پروژه‌ای محرمانه نیاز شده است که $n$ پایگاه ارتش با تعدادی تونل دوطرفه یه یکدیگر متصل شوند، ارتش می‌تواند بین هر دو پایگاه دلخواه $i$ و $j$ تونلی بسازد که طول آن عددی بین $1$ تا $10^9$ (شامل هر دو) باشد. ارتش می‌خواهد که این تونل‌ها را به شکلی بین برخی از پایگاه‌ها بسازد که در نهایت طول کوتاه‌ترین مسیر از پایگاه $i$ به پایگاه $j$ برابر با $A_{i, j}$ باشد. آقا تورج می‌خواهد ببیند که آیا می‌توان تونل‌هایی ساخت که شرایط بالا برقرار باشد یا نه. اگر می‌توان به شکلی تونل‌ها را بین پایگاه‌ها ساخت که شرایط برقرار باشد، کمینه تعداد تونل‌های مورد نیاز چقدر است؟ توک و صمد پس از شنیدن مساله هر دو دست به کار می‌شوند ... اما ای دل غافل که این صمد است که خیلی زود پاسخ را به آقا تورج می‌گوید و توک از رسیدن به مرادش باز می‌ماند. توک که دیگر عصبانی شده است و افکار پلیدی در سر دارد می‌خواهد ببیند که جوابی که صمد به آقا تورج داده است چه بوده است. برای این‌کار از شما کمک می‌گیرد ... # ورودی در خط اول ورودی عدد $n$ ، تعداد پایگاه‌های ارتش آمده است. سپس در $n$ سطر بعدی ماتریس $A$ می‌آید. در هر سطر $n$ عدد می‌آید که عدد $j$ ام در سطر $i+1$ ام ورودی ، طول کوتاه‌ترین مسیر از پایگاه $i$ به $j$ را مشخص می‌کند، تضمین می‌شود که $A_{i, i} = 0$ است. $$1 \le n \le 500$$ $$i \neq j : 1 \le A_{i, j} \le 10^9$$ $$ i = j : A_{i, j} = 0 $$ # خروجی چناچه نمی‌توان تعدادی تونل دوطرفه با طول‌های دلخواه ساخت که طول کوتاه‌ترین مسیر از پایگاه $i$ به پایگاه $j$ برابر با $A_{i, j}$ باشد، در یک خط فقط عدد `-1` را چاپ کنید . در غیراین‌صورت کمترین تعداد تونل مورد نیاز که باید بین پایگاه‌ها ساخته شود را چاپ کنید. ## ورودی نمونه ۱ ``` 2 0 4 4 0 ``` ## خروجی نمونه ۱ ``` 1 ``` کافی است یه تونل با طول $4$ (زمان گذشتن از آن $4$ است) ، بین پایگاه‌های $1$ و $2$ بسازیم. ## ورودی نمونه ۲ ``` 1 0 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 2 0 10 56 0 ``` ## خروجی نمونه ۳ ``` -1 ``` نمی‌توان تعدادی تونل ساخت که طول کوتاه‌ترین مسیر از پایگاه $1$ به $2$ با طول کوتاه‌ترین مسیر از پایگاه $2$ به $1$ برابر نباشد (تونل‌ها همگی دوطرفه‌اند) ## ورودی نمونه ۴ ``` 3 0 4 8 4 0 4 8 4 0 ``` ## خروجی نمونه ۴ ``` 2 ```

صمد و توک

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

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

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

آقا تورج فرمانده ارتش است. در راستای انجام پروژه‌ای محرمانه نیاز شده است که $n$ پایگاه ارتش با تعدادی تونل دوطرفه یه یکدیگر متصل شوند، ارتش می‌تواند بین هر دو پایگاه دلخواه $i$ و $j$ تونلی بسازد که طول آن عددی بین $1$ تا $10^9$ (شامل هر دو) باشد.

ارتش می‌خواهد که این تونل‌ها را به شکلی بین برخی از پایگاه‌ها بسازد که در نهایت طول کوتاه‌ترین مسیر از پایگاه $i$ به پایگاه $j$ برابر با $A_{i, j}$ باشد.

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

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

ورودی🔗

در خط اول ورودی عدد $n$ ، تعداد پایگاه‌های ارتش آمده است.

سپس در $n$ سطر بعدی ماتریس $A$ می‌آید.

در هر سطر $n$ عدد می‌آید که عدد $j$ ام در سطر $i+1$ ام ورودی ، طول کوتاه‌ترین مسیر از پایگاه $i$ به $j$ را مشخص می‌کند، تضمین می‌شود که $A_{i, i} = 0$ است.

$1 \le n \le 500$ $i \neq j : 1 \le A_{i, j} \le 10^9$ $i = j : A_{i, j} = 0$

خروجی🔗

چناچه نمی‌توان تعدادی تونل دوطرفه با طول‌های دلخواه ساخت که طول کوتاه‌ترین مسیر از پایگاه $i$ به پایگاه $j$ برابر با $A_{i, j}$ باشد، در یک خط فقط عدد -1 را چاپ کنید .

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

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

2
0 4
4 0

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

کافی است یه تونل با طول $4$ (زمان گذشتن از آن $4$ است) ، بین پایگاه‌های $1$ و $2$ بسازیم.

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

1
0

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

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

2
0 10
56 0

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

-1

نمی‌توان تعدادی تونل ساخت که طول کوتاه‌ترین مسیر از پایگاه $1$ به $2$ با طول کوتاه‌ترین مسیر از پایگاه $2$ به $1$ برابر نباشد (تونل‌ها همگی دوطرفه‌اند)

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

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

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همان‌طور که در سوال قبل گفته شد پدر پوپک - همان آقا تورج - فرمانده ارتش است و توک پس از اینکه به پوپک نمی‌رسد، تصمیم می‌گیرد وارد ارتش شود و از آقا تورج انتقام بگیرد. برای این کار، توک یک بمب در اتاق آقا تورج کار می‌گذارد. آقا تورج وقتی متوجه بمب می‌شود که دیگر خیلی دیر شده و برای نجات دفترش می‌خواهد رمز بمب را حدس بزند. برای خنثی کردن بمب او باید $n$ تا عدد $$a_1,a_2,...,a_{n-1},a_{n}$$را انتخاب کند به طوری که هر کدام عددی بین $0$ تا $2^{31}-1$ (شامل هر دو) هستند. او $q$ ثانیه برای فکر کردن دارد. در هر ثانیه این حدس را می‌زند که $xor$ دو عدد $a_i$ و $a_j$ برابر $k$ است. شما باید بعد از هر حدس به تورج بگویید که به چند طریق مختلف می‌تواند رمز را بزند (آرایه $a$ را انتخاب کند) که تمام حدس‌هایی که تا الان زده شده، در آرایه $a$ صدق کند (توجه کنید که ممکن است تعداد این حالات $0$ باشد یعنی حالتی نباشد که با حدس‌ها هم‌‌خوانی داشته باشد). باقیمانده جواب را بر $10^9+7$ چاپ کنید. اگر با عملگر $xor$ آشنایی ندارید [اینجا](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) را ببینید. # ورودی در خط اول ورودی دو عدد $n$ و $q$ داده شده است. سپس در $q$ سطر بعدی در هر سطر یک حدس آقا تورج آمده است که به شکل سه عدد $i, j, k$ است. $$1 \le q \le 300\ 000$$ $$2 \le n \le 300\ 000$$ $$1 \le i,j \le n , i\neq j$$ $$0 \le k \le 2^{31}-1$$ # خروجی به ازای هر حدس در $q$ سطر باقیمانده جواب مساله بر $10^9+7$ را چاپ کنید. ## ورودی نمونه ۱ ``` 3 2 1 2 100 2 3 71 ``` ## خروجی نمونه ۱ ``` 145586002 147483634 ```

انتقام توک

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

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

برای این کار، توک یک بمب در اتاق آقا تورج کار می‌گذارد.

آقا تورج وقتی متوجه بمب می‌شود که دیگر خیلی دیر شده و برای نجات دفترش می‌خواهد رمز بمب را حدس بزند. برای خنثی کردن بمب او باید $n$ تا عدد $a_1,a_2,...,a_{n-1},a_{n}$ را انتخاب کند به طوری که هر کدام عددی بین $0$ تا $2^{31}-1$ (شامل هر دو) هستند.

او $q$ ثانیه برای فکر کردن دارد. در هر ثانیه این حدس را می‌زند که $xor$ دو عدد $a_i$ و $a_j$ برابر $k$ است. شما باید بعد از هر حدس به تورج بگویید که به چند طریق مختلف می‌تواند رمز را بزند (آرایه $a$ را انتخاب کند) که تمام حدس‌هایی که تا الان زده شده، در آرایه $a$ صدق کند (توجه کنید که ممکن است تعداد این حالات $0$ باشد یعنی حالتی نباشد که با حدس‌ها هم‌‌خوانی داشته باشد). باقیمانده جواب را بر $10^9+7$ چاپ کنید.

اگر با عملگر $xor$ آشنایی ندارید اینجا را ببینید.

ورودی🔗

در خط اول ورودی دو عدد $n$ و $q$ داده شده است.

سپس در $q$ سطر بعدی در هر سطر یک حدس آقا تورج آمده است که به شکل سه عدد $i, j, k$ است.

$1 \le q \le 300\ 000$ $2 \le n \le 300\ 000$ $1 \le i,j \le n , i\neq j$ $0 \le k \le 2^{31}-1$

خروجی🔗

به ازای هر حدس در $q$ سطر باقیمانده جواب مساله بر $10^9+7$ را چاپ کنید.

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

3 2
1 2 100
2 3 71

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

145586002
147483634

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از ترکیدن بمب، آقا تورج با اینکه خودش را از بمب دور می‌کند به شدت آسیب می‌بیند و به کما می‌رود ... توک به جای او فرماندهی رو به دست گرفته است و در یکی از حمله‌ها در حال توضیح دادن نقشه حمله به سربازان، یکی از سربازها می گوید که او هم نقشه‌ای برای حمله دارد. یک نقشه برای حمله، چیدن $n$ سرباز در یک جدول $n \times n$ است به طوری که در هر سطر و در هر ستون دقیقا یک سرباز وجود داشته باشد. ضعف یک نقشه بزرگترین $k$ ای است که در نقشه یک مربع $k \times k$ وجود داشته باشد به طوری که هیچ سربازی در آن مربع نباشد. نقشه توک به صورتی است که ضعف آن کم‌ترین ضعف بین تمام نقشه‌ها را دارد (توجه کنید که ما نقشه توک را نداریم.) اگر نقشه‌ای که سرباز توک به او پیشنهاد می‌کند میزان ضعفش بیشتر از نقشه توک باشد، توک او را به سیاه‌چاله می‌اندازد! در ورودی به شما نقشه سرباز داده شده است. ابتدا بگویید ضعف این نقشه چقدر است. سپس بگویید آیا سرباز در سیاه‌چاله می افتد یا خیر. ( آیا نقشه‌ای وجود دارد که ضعفش کمتر از نقشه پیشنهادی سرباز باشد؟ ) نقشه حمله سرباز به شکل یک جای‌گشت با نام $P$ داده می‌شود که $P_i$ شماره سطری است که سرباز ستون $i$ ام در نقشه پیشنهادی در آن قرار گرفته است. # ورودی در خط اول ورودی عدد $n$ آمده است . سپس در $n$ خط بعدی جای‌گشت $P$ آمده است که یعنی در نقشه پیشنهادی، سرباز ستون $i$ ام، در سطر $P_i$ قرار گرفته است. $$1 \le n \le 100\ 000$$ $$1 \le P_i \le n $$ # خروجی در خط اول ضعف نقشه پیشنهادی سرباز را چاپ کنید. سپس در خط دوم، چنانچه سرباز به سیاه‌چاله می‌افتاد `YES` و در غیراین‌صورت `NO` چاپ کنید. ## ورودی نمونه ۱ ``` 4 1 2 3 4 ``` ## خروجی نمونه ۱ ``` 2 YES ``` ## ورودی نمونه ۲ ``` 2 1 2 ``` ## خروجی نمونه ۲ ``` 1 NO ```

نقشه حمله

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

بعد از ترکیدن بمب، آقا تورج با اینکه خودش را از بمب دور می‌کند به شدت آسیب می‌بیند و به کما می‌رود ...

توک به جای او فرماندهی رو به دست گرفته است و در یکی از حمله‌ها در حال توضیح دادن نقشه حمله به سربازان، یکی از سربازها می گوید که او هم نقشه‌ای برای حمله دارد. یک نقشه برای حمله، چیدن $n$ سرباز در یک جدول $n \times n$ است به طوری که در هر سطر و در هر ستون دقیقا یک سرباز وجود داشته باشد.

ضعف یک نقشه بزرگترین $k$ ای است که در نقشه یک مربع $k \times k$ وجود داشته باشد به طوری که هیچ سربازی در آن مربع نباشد.

نقشه توک به صورتی است که ضعف آن کم‌ترین ضعف بین تمام نقشه‌ها را دارد (توجه کنید که ما نقشه توک را نداریم.) اگر نقشه‌ای که سرباز توک به او پیشنهاد می‌کند میزان ضعفش بیشتر از نقشه توک باشد، توک او را به سیاه‌چاله می‌اندازد!

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

نقشه حمله سرباز به شکل یک جای‌گشت با نام $P$ داده می‌شود که $P_i$ شماره سطری است که سرباز ستون $i$ ام در نقشه پیشنهادی در آن قرار گرفته است.

ورودی🔗

در خط اول ورودی عدد $n$ آمده است . سپس در $n$ خط بعدی جای‌گشت $P$ آمده است که یعنی در نقشه پیشنهادی، سرباز ستون $i$ ام، در سطر $P_i$ قرار گرفته است.

$1 \le n \le 100\ 000$ $1 \le P_i \le n$

خروجی🔗

در خط اول ضعف نقشه پیشنهادی سرباز را چاپ کنید.

سپس در خط دوم، چنانچه سرباز به سیاه‌چاله می‌افتاد YES و در غیراین‌صورت NO چاپ کنید.

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

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

2
YES

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

2
1
2

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

1
NO

فرار از زندان

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

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

ورودی🔗

در خط اول ورودی دو عدد $n$ و $m$ ، تعداد راس ها و تعداد یال‌های گراف داده شده است.

سپس در $m$ سطر بعدی، دو عدد $u$ و $v$ می آید که نشان دهنده این است که این دو راس در گراف به یکدیگر یال دارند.

$1 \le n,m \le 40$ $1 \le m \le {{n}\choose {2}}$

خروجی🔗

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

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

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

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