+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- مبنای ۱۶، یکی از مبناهای عددی است که برای نمایش اعداد در آن از ارقام (به ترتیب) ، $0123456789ABCDEF$ استفاده می‌کنند ، برای مثال عدد ۴۷ در مبنای ۱۶ به فرم $2F$ نشان داده می‌شود . یک عدد در مبنای ۱۶ به شما داده می‌شود، این عدد را بعلاوه یک کرده و عدد حاصل را مجددا در مبنای ۱۶ چاپ کنید. # ورودی سطر اول ورودی شامل یک عدد نامنفی در مبنای ۱۶ می باشد. تضمین می‌شود که در ابتدای عدد رقم صفر نداریم (مگر خود عدد صفر) و تضمین می شود که طول عدد داده شده حداکثر ۱۰۰ می‌باشد . # خروجی در تنها خط خروجی عدد به دست آمده را در مبنای ۱۶ چاپ کنید. دقت کنید که عدد شما نباید دارای صفر در ابتدایش باشد. # مثال ## ورودی نمونه ``` 2F ``` ## خروجی نمونه ``` 30 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- سه ظرف داریم که در ابتدا به ترتیب در آن‌ها $a$ ,$b$ ,$c$ لیتر آب داریم. در هرگام می توانیم دو ظرف انتخاب کرده و مقداری آب (می تواند این مقدار اعشاری هم باشد) از یک ظرف به ظرف دیگر منتقل کنیم. هدف برابر کردن مقدار آب در هر سه ظرف است، کمینه تعداد حرکات لازم را در خروجی چاپ کنید. # ورودی سه عدد طبیعی $$1 \le a , b , c \le 10^{15}$$ به شما داده میشود که بیانگر مقدار آب در سه ظرف است. # خروجی در تنها خط خروجی کمینه تعداد گام های لازم برای برابر کردن مقدار آب در هر سه ظرف را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 10 10 10 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 1 1000 20 ``` ## خروجی نمونه ۲ ``` 2 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- یک درخت $n$ راسی به شما داده می شود. مجموعه $P$ (که می‌تواند تهی باشد) از رئوس درخت را **اکبرجوجه** مینامیم، اگر برای هر دو عضو متمایز $u$ و $v$ در $P$، هیچ یک از $u$ یا $v$ جد دیگری نباشد. می گوییم راس $u$ **جد** راس $v$ است اگر در مسیر $v$ به **راس ۱**، راس $u$ وجود داشته باشد. هدف پیدا کردن باقی‌مانده تعداد زیرمجموعه‌های اکبرجوجه از رئوس درخت بر $10^{9} + 7$ می‌باشد، این عدد را در خروجی چاپ کنید. # ورودی در خط اول ورودی عدد $n$ که به شما داده می‌شود که بیانگر تعداد رئوس گراف است. سپس در $n-1$ خط ، و در خط $i$ ام، دو عدد $u_{i}$ و $v_{i}$ می‌آید که به معنی یالی بین این دو راس است. تضمین می‌شود گراف ورودی درخت است. $$1 \le n \le 100\ 000$$$$1 \le u_{i} , v_{i} \le n$$ # خروجی در تنها خط خروجی باقی‌مانده تعداد زیرمجموعه‌های اکبرجوجه درخت را بر $10^{9} + 7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 1 2 2 3 3 4 ``` ## خروجی نمونه ۱ ``` 5 ``` شرح ورودی و خروجی نمونه شماره یک : مجموعه موردنظر حداکثر می‌تواند شامل یک راس باشد که خود چهار حالت دارد و یک حالت هم مجموعه تهی است، پس پاسخ برابر پنج است. ## ورودی نمونه ۲ ``` 4 1 2 1 3 1 4 ``` ## خروجی نمونه ۲ ``` 9 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم $\frac {a_i} {b_i}$ نوشته شده است. درخت به این شکل ساخته میشود: 1. $a_{1}$ = $b_{1}$ = $1$ 2. $a_{2i}$ = ($a_{i}$ + $b_{i}$ ) , $b_{2i}$ = $b_{i}$ (بچه سمت چپ) 3. $a_{2i+1}$ = $a_{i}$ , $b_{2i+1}$ = ($a_{i}$ + $b_{i}$ ) (بچه سمت راست) فاصله دو راس در درخت را تعداد یال های تنهای مسیر بینشان تعریف می کنیم. به شما $Q$ درخواست که هر کدام شامل کسری به فرم $\frac {p_i} {q_i}$ داده میشود. برای هر عدد موجود در درخواست ها، اگر تنها یک راس در درخت وجود داشت که کسرش برابر کسر ورودی داده شده بود، فاصله راس آن کسر تا راس ۱ را در خروجی چاپ کنید و در غیر این صورت $-1$ خروجی دهید. # ورودی در خط اول $Q$ و در $Q$ خط بعدی$p_{i}$ و $q_{i}$ به شما داده شده. $$1 \le Q \le 100\ 000$$ $$1 \le p_{i},q_{i} \le 10^{18}$$ # خروجی در خط $i$ام اگر کسری معادل عدده $\frac {p_i} {q_i}$ بود و فقط این کسر معادل این عدد بود فاصله‌ی آن را از راس ۱ خروجی دهید در غیر این صورت $-1$ خروجی دهید. # مثال ## ورودی‌ نمونه ``` 2 1 1 1 2 ``` ## خروجی‌ نمونه ``` 0 1 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- **دنباله ولایی**، یک دنباله به طول $n$ از اعداد حسابی به صورت $a_{0},a_{1},....,a_{n-1}$ است که $a_{i}$ برابر تعداد تکرارهای عدد $i$ در دنباله‌ی $a$ است. برای مثال دنباله $2,0,2,0$ این خاصیت را دارد زیرا تعداد ۰ های دنباله برابر با ۲، تعداد ۱ های دنباله برابر با ۰، تعداد ۲ های دنباله برابر با ۲ و تعداد ۳ های دنباله برابر با ۰ است. عدد $n$ به شما داده شده، دنباله‌های ولایی به طول $n$ را چاپ کنید. # ورودی در تنها خط از ورودی عدد $n$ داده شده. $$1 \le n \le 1\ 000$$ # خروجی در اولین خط از خروجی تعداد دنباله های ولایی به طول $n$ را چاپ کنید. سپس در خطوط بعدی، در هر خط یک دنباله ولایی را چاپ کنید. دنباله ها باید به ترتیب کتابخانه ای خروجی داده شوند. یک دنباله از دنباله‌ی دیگر در ترتیب کتابخانه‌ای زودتر می‌آید اگر در محل چپ‌ترین محل تفاوت دو دنباله، دنباله‌ی اول عدد کوچکتری داشته باشد. # مثال ## ورودی نمونه ``` 1 ``` ## خروجی نمونه ``` 0 ```