+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پوپک از خواب بیدار می‌شود... به یاد می‌آورد که خوابی دیده است اما جزییات این خواب در خاطرش نیست... پوپک می‌داند که او در خوابش دو کیسه تیله داشته است که در هر کیسه حداقل یک تیله بوده است. پوپک می‌داند که تعداد تیله‌های کیسه اول مقسوم‌علیهی از عدد $a$ بوده و تعداد تیله‌های کیسه دوم مقسوم علیهی از عدد $b$ بوده است. همچنین پوپک به یاد دارد که دو کیسه‌اش خیلی سنگین نبودند و در مجموع حداکثر $x$ تیله در دو کیسه قرار داشته است. در همین هنگام پوپک، توک را می‌بیند و ماجرا را برای او تعریف می‌کند. توک نیز خیلی سریع تعداد خواب‌های متفاوتی که ممکن است پوپک دیده باشد را می‌شمارد و این تعداد را به او می‌گوید... در همین هنگام توک یه دل نه صد دل عاشق پوپک می‌شود ... # ورودی در تنها خط ورودی به ترتیب سه عدد $a$ و $b$ و $x$ آمده است. $$1 \le a, b\le 1\ 000$$ $$2 \le x \le 1\ 000$$ # خروجی در تنها خط خروجی تعداد خواب‌های متفاوتی که ممکن است پوپک دیده باشد را چاپ کنید. ## ورودی نمونه ۱ ``` 2 2 2 ``` ## خروجی نمونه ۱ ``` 1 ``` تنها حالت ممکن این است که در هر دو کیسه دقیقا $1$ تیله قرار گرفته باشد. ## ورودی نمونه ۲ ``` 7 7 14 ``` ## خروجی نمونه ۲ ``` 4 ``` چهار حالت مختلف برای تعداد تیله‌های در کیسه $(1, 1)$ و $(1, 7)$ و $(7, 1)$ و $(7 , 7)$ هستند.

خواب پوپک

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

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

پوپک می‌داند که او در خوابش دو کیسه تیله داشته است که در هر کیسه حداقل یک تیله بوده است. پوپک می‌داند که تعداد تیله‌های کیسه اول مقسوم‌علیهی از عدد $a$ بوده و تعداد تیله‌های کیسه دوم مقسوم علیهی از عدد $b$ بوده است. همچنین پوپک به یاد دارد که دو کیسه‌اش خیلی سنگین نبودند و در مجموع حداکثر $x$ تیله در دو کیسه قرار داشته است.

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

در همین هنگام توک یه دل نه صد دل عاشق پوپک می‌شود ...

ورودی🔗

در تنها خط ورودی به ترتیب سه عدد $a$ و $b$ و $x$ آمده است.

$1 \le a, b\le 1\ 000$ $2 \le x \le 1\ 000$

خروجی🔗

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

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

2 2 2

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

تنها حالت ممکن این است که در هر دو کیسه دقیقا $1$ تیله قرار گرفته باشد.

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

7 7 14

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

چهار حالت مختلف برای تعداد تیله‌های در کیسه $(1, 1)$ و $(1, 7)$ و $(7, 1)$ و $(7 , 7)$ هستند.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- توک به مناسبت ولنتاین میخواهد هدیه زیبایی به پوپک بدهد ... از آنجایی که توک پول زیادی ندارد، به زحمت توانسته است که یک رشته باینری بخرد. توک می‌داند که رشته باینری خیلی جذاب نیست بنابراین تصمیم گرفته است تغییری در آن ایجاد کند. او می تواند رشته‌اش را به $a$ رشته با طول برابر افراز کند (که بالطبع طول این رشته‌ها $\frac{n} a$ خواهد بود) و در نهایت $and$ بیتی این $a$ رشته را به عنوان کادو به پوپک بدهد. هر چه عدد متناظر با رشته باینری‌ای که توک به پوپک می دهد بیشتر باشد، پوپک شادتر می شود. بهترین رشته‌ای که توک به پوپک باید هدیه بدهد (یعنی رشته‌ای که عدد متناظر با آن بیشینه است) را بدون صفر در پشت رشته (`leading zeroes`) چاپ کنید . برای مثال اگر رشته توک $110101$ باشد، توک با انتخاب $a=3$ ، آن را به سه رشته $11, 01, 01$ تقسیم می‌کند که $and$ بیتی این رشته برابر $01$ است پس رشته‌ای که توک به پوپک در این حالت هدیه می‌دهد $1$ است. به شکل مشابه اگر توک $a=2$ را انتخاب کند آنگاه رشته‌اش را به دو رشته $110, 101$ تقسیم می‌کند و رشته‌ای که کادو می‌دهد $100$ خواهد بود در حالی که با انتخاب $a=1$ ، رشته‌ای که توک به پوپک هدیه می‌دهد $110101$ می‌شود، پس چون عدد مربوط به این‌ رشته از بقیه رشته‌ها بیشتر است توک باید این رشته را به پوپک کادو بدهد! (می‌توانید بقیه‌ حالات را نیز بررسی کنید، که به جواب کوچکتری نسبت به این رشته منتهی می‌شوند) چنانچه عدد متناظر با رشته‌ای که توک کادو می ‌دهد $0$ باشد، در خروجی $0$ چاپ کنید. اگر با عملگر $and$ آشنایی ندارید [اینجا](https://en.wikipedia.org/wiki/Bitwise_operation#AND) را ببینید. # ورودی در تنها خط ورودی رشته باینری که توک خریده است، آمده است. اگر طول رشته توک را با $n$ نشان دهیم $$1 \le n \le 100\ 000$$ # خروجی در تنها خط خروجی رشته‌ای که توک به پوپک هدیه می‌دهد را چاپ کنید. ## ورودی نمونه ۱ ``` 011 ``` ## خروجی نمونه ۱ ``` 11 ``` ## ورودی نمونه ۲ ``` 110101 ``` ## خروجی نمونه ۲ ``` 110101 ``` این تست نمونه در صورت سوالات توضیح داده شده است . ## ورودی نمونه ۳ ``` 0000 ``` ## خروجی نمونه ۳ ``` 0 ```

کادوی پوپک‌پسند

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

توک به مناسبت ولنتاین میخواهد هدیه زیبایی به پوپک بدهد ...

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

او می تواند رشته‌اش را به $a$ رشته با طول برابر افراز کند (که بالطبع طول این رشته‌ها $\frac{n} a$ خواهد بود) و در نهایت $and$ بیتی این $a$ رشته را به عنوان کادو به پوپک بدهد.

هر چه عدد متناظر با رشته باینری‌ای که توک به پوپک می دهد بیشتر باشد، پوپک شادتر می شود. بهترین رشته‌ای که توک به پوپک باید هدیه بدهد (یعنی رشته‌ای که عدد متناظر با آن بیشینه است) را بدون صفر در پشت رشته (leading zeroes) چاپ کنید .

برای مثال اگر رشته توک $110101$ باشد، توک با انتخاب $a=3$ ، آن را به سه رشته $11, 01, 01$ تقسیم می‌کند که $and$ بیتی این رشته برابر $01$ است پس رشته‌ای که توک به پوپک در این حالت هدیه می‌دهد $1$ است. به شکل مشابه اگر توک $a=2$ را انتخاب کند آنگاه رشته‌اش را به دو رشته $110, 101$ تقسیم می‌کند و رشته‌ای که کادو می‌دهد $100$ خواهد بود در حالی که با انتخاب $a=1$ ، رشته‌ای که توک به پوپک هدیه می‌دهد $110101$ می‌شود، پس چون عدد مربوط به این‌ رشته از بقیه رشته‌ها بیشتر است توک باید این رشته را به پوپک کادو بدهد! (می‌توانید بقیه‌ حالات را نیز بررسی کنید، که به جواب کوچکتری نسبت به این رشته منتهی می‌شوند)

چنانچه عدد متناظر با رشته‌ای که توک کادو می ‌دهد $0$ باشد، در خروجی $0$ چاپ کنید.

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

ورودی🔗

در تنها خط ورودی رشته باینری که توک خریده است، آمده است.

اگر طول رشته توک را با $n$ نشان دهیم $1 \le n \le 100\ 000$

خروجی🔗

در تنها خط خروجی رشته‌ای که توک به پوپک هدیه می‌دهد را چاپ کنید.

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

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

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

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

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

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

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

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

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

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

آقا تورج دنباله $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