+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهتاب تصمیم گرفته کارهای مدرسه‌اش را انجام دهد و در هکاتون دیوار شرکت کند. تمرین ریاضی مدرسه‌ی او برای مهتاب که برنامه‌نویس نیست کار چندان ساده‌ای نیست. در دفتر مشق مهتاب، عدد طبیعی $n$ نوشته شده و از او خواسته‌اند که اعداد فرد کوچک‌تر از $n$ را در دفترش بنویسد و سپس جمع این اعداد را حساب کند. معلم مهتاب، هیچ‌وقت اعداد نوشته شده را نگاه نمی‌کند و فقط حاصل جمع نهایی را بررسی می‌کند. مهتاب از شما کمک می‌خواهد که این عدد را پیدا کنید. # ورودی در تنها سطر ورودی، عدد صحیح و مثبت $n$ داده می‌شود. $$2 \leq n \leq 100$$ # خروجی در تنها سطر خروجی، یک عدد صحیح برابر عدد نهایی که باید مهتاب بنویسد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 10 ``` ## خروجی نمونه ۱ ``` 25 ``` ## ورودی نمونه ۲ ``` 7 ``` ## خروجی نمونه ۲ ``` 9 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- جدولی $n \times m$ داریم. سطرهای این جدول از بالا به پایین با اعداد ۱ تا $n$ و ستون‌های این جدول از چپ به راست با اعداد ۱ تا $m$ شماره‌گذاری شده‌اند. هر خانه از این جدول را می‌توان با یک زوج مرتب $(r, c)$ نشان داد که $r$ شماره‌ی سطر و $c$ شماره‌ی ستون جدول را نشان می‌دهد. دزدی وارد این جدول شده و از خانه‌ی $(1,1)$ آن دزدی کرده و قصد دارد به خانه $(n,m)$ برود تا بتواند از جدول خارج شود. این دزد در یک حرکت می‌تواند از یک خانه به خانه‌ی بالا، پایین، چپ یا راست (در صورت وجود) برود.  یک سگ نگهبان، در خانه‌ی $(x, y)$ این جدول، زندگی می‌کند. این سگ از خانه‌های با فاصله‌ی حداکثر $s$ از خانه‌اش محافظت می‌کند. در اینجا منظور از فاصله‌ی خانه‌ی $(a, b)$ تا خانه‌ی $(c, d)$ یعنی کمترین تعداد حرکتی که دزد نیاز دارد تا از خانه‌ی $(a, b)$ به خانه‌ی $(c, d)$ برسد. می‌دانیم اگر دزد به خانه‌ای برود که سگ نگهبان از آن محافظت می‌کند، اسیر می‌شود.حال به دزد بگویید آیا می‌تواند راهی از خانه‌ی $(1, 1)$ به خانه‌ی $(n, m)$ پیدا کند یا نه. # ورودی در خط اول ورودی، عدد صحیح $t$ آمده که تعداد پرسش‌ها را نشان می‌دهد. $$ 1 \leq t\leq 10^5 $$ سپس در $t$ خط بعدی، در هر خط به ترتیب پنج عدد صحیح $n , m , x , y , s$ به شما داده می‌شود. $$1 \leq x \leq n \leq 10^9$$ $$ 1 \leq y \leq m \leq 10^9$$ $$1 \leq s \leq 10^9$$ # خروجی خروجی شما باید شامل $t$ خط باشد. برای هر پرسش اگر دزد می‌تواند به خانه $(n,m)$ برود `YES` و در غیر این صورت `NO` خروجی دهید. # مثال‌ها ## ورودی نمونه ۱ ``` 2 4 4 2 3 1 5 6 3 3 2 ``` ## خروجی نمونه ۱ ``` YES NO ``` 

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- گاتهام خیابانی است با طول بی‌نهایت که از نقطه ۰ شروع می‌شود. اگر مبدا زمانی ما از ابتدای ثانیه ۱ آغاز شود، می‌دانیم که جوکر در هر لحظه از شروع تا پایان ثانیه $t$ام، (به مدت ۱ ثانیه) در نقطه‌ای با فاصله $L$ از ابتدای خیابان ایستاده است. به طوری که تمام عرض خیابان را اشغال کرده است. در نقطه ۰ خیابان، بتمن $n$ ماشین دارد که قرار است به ترتیب در ابتدای هر ثانیه یکی از آن‌ها از نقطه ۰ خیابان حرکت کند. به این معنا که در ابتدای ثانیه ۱ یکی از ماشین‌ها حرکت می‌کند، در ابتدای ثانیه ۲ دیگری حرکت می‌کند و همین‌طور ادامه می‌یابد تا جایی که در ابتدای ثانیه $n$ام، آخرین ماشین حرکت می‌کند. سرعت تمام ماشین‌ها به شما داده شده است. هدف بتمن این است که جوکر حتماً توسط یکی از ماشین‌ها زیر گرفته شود. در قرن جدید، ماشین‌ها خودشان رانندگی می‌کنند و ممکن است قبل از رسیدن به جوکر ترمز کنند. بتمن می‌خواهد طوری ماشین‌ها را ترتیب دهد که احتمال مرگ جوکر بیشترین مقدار ممکن باشد. به عبارت دیگر، بیشترین تعداد ماشین‌ها که در هر بازه زمانی از ابتدای ثانیه ۱ تا انتهای ثانیه $t$، می‌توانند از روی جوکر عبور کنند، باید تعیین شود. # ورودی خط اول ورودی عدد طبیعی و مثبت $q$ تعداد سناریو ها به شما داده می‌شود. $$1 \leq q \leq 10^5$$ در خط اول هر سناریو به ترتیب سه عدد طبیعی و مثبت $n$، $L$ و $t$ به شما ورودی داده می‌شوند. $$ 1 \leq n \leq 10^5 $$ در خط دوم هر سناریو $n$ عدد طبیعی و مثبت $v_1, v_2, \dots, v_n$ ورودی داده می‌شوند که هر کدام سرعت یکی از ماشین‌های بتمن را نشان می‌دهد. $$ 1 \leq v_i, t, L\leq 10^9 $$ $$ \sum_{i=1}^{q}n_i \leq10^5$$ # خروجی خروجی $q$ خط دارد. برای هر سناریو، در یک خط باید بیشترین تعداد ماشین‌هایی که ممکن است در قسمتی از حرکتشان از روی جوکر عبور کنند، چاپ شود. # مثال‌ها ## ورودی نمونه ۱ ``` 5 2 1 1 1 1 3 18 5 3 4 5 3 9 1 1 3 9 3 24 2 4 12 12 3 10 5 10 5 13 ``` ## خروجی نمونه ۱ ``` 1 2 1 1 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- می‌خواهیم $n$ ساختمان $h_1, h_2, \dots, h_n$ طبقه‌ای کنار هم در یک ردیف بسازیم. ساختمان در یک طبقه زمانی نورگیر است که از سمت چپ یا راست به فضای باز دسترسی داشته باشد. به‌‌عنوان مثال ساختمان‌های انتهای چیدمان (یعنی در سمت چپ یا راست)، تمام واحدهای آن نورگیر خواهند بود. هدف این است که ساختمان‌ها را به ترتیبی بچینیم که تعداد واحدهای نورگیر به حداکثر برسد. تعداد حداکثری واحدهای نورگیر را پیدا کنید. # ورودی در خط اول ورودی عدد $n$ تعداد ساختمان ها داده می شود. $$ 1 \leq n\leq 10^5 $$ سپس در خط بعدی به ترتیب $h_1$ تا $h_n$ داده می شود. $$ 1 \leq h_i\leq 10^9 $$ # خروجی در یک خط، حداکثر تعداد واحد های نورگیر را خروجی دهید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 3 2 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 5 1 3 3 3 3 ``` ## خروجی نمونه ۲ ``` 10 ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فرض کنید می‌خواهیم جایگشت‌های `a` تا `z` را از بیشترین به کمترین ارزش مرتب کنیم (اگر دو جایگشت ارزش برابر داشتند، جایگشتی که از نظر ترتیب الفبایی کوچک‌تر باشد، دارای اولویت بالاتر است). ارزش یک جایگشت به شکل زیر تعریف می‌شود: $$ value(\pi) = \sum_{c='a'}^{'z'} \left( cnt_c - cnt_{\pi_c} \right) ^ 2 $$ منظور از $cnt_c$، تعداد تکرار حرف $c$ در رشته‌ است. از آن‌جایی که تعداد این جایگشت‌ها بسیار زیادند، کافی‌است تنها $k$ جایگشت اول را در دنباله‌ نزولی مرتب‌شده جایگشت‌ها خروجی دهید. # ورودی در خط اول، عدد صحیح $k$ می‌آید. $$ 1 \leq k \leq 100 $$ سپس در خط بعد ورودی یک آرایه $cnt$ از اعداد صحیح به طول $26$ داده می‌شود که نشان‌دهنده تعداد تکرارهای هر حرف از الفبا است. $$ 0 \leq cnt_i \leq 10^6 $$ تضمین می‌شود که $cnt$ها اعداد متمایز باشند. # خروجی در $k$ خط خروجی، در هر خط یک جایگشت از حروف `a` تا `z` با فاصله از هم خروجی دهید که خط $i$ام نشان ‌دهنده جایگشت‌ $i$ام است. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ```` ## خروجی نمونه ۱ ``` z y x w v u t s r q p o n m l k j i h g f e d c b a y z x w v u t s r q p o n m l k j i h g f e d c b a z x y w v u t s r q p o n m l k j i h g f e d c b a ````

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در این سوال، شما سیستمی برای مدیریت آگهی‌های مسکن طراحی می‌کنید. هر آگهی می‌تواند برای فروش، رهن یا اجاره باشد و دارای ویژگی‌هایی از جمله عنوان، قیمت، متراژ، نوع ملک (آپارتمان یا حیاط)، وضعیت (فروش، رهن یا اجاره)، و مختصات جغرافیایی (عرض و طول جغرافیایی) خواهد بود. شما باید این ویژگی‌ها را در کوئری‌های مختلف مانند افزودن آگهی، جستجو و حذف آگهی‌ها مدیریت کنید. # دستورها <details class="blue"> <summary> دستور `add_house` </summary> ---------- فرم کلی این دستور به صورت زیر است: ``` add_house -name="<title>" -type="<type>" -status="<status>" -price=<price> -area=<area> -latitude=<latitude> -longitude=<longitude> [-desc="<description>"] ``` + `<title>` عنوان آگهی (منحصربه‌فرد و اجباری). + `<type>` نوع ملک (مانند `apartment` برای آپارتمان یا `yard` برای حیاط و اجباری). + `<status>` وضعیت ملک (`sale` برای فروش، `rent` برای رهن یا اجاره و اجباری). + `<price>` قیمت ملک (عدد صحیح و مثبت به تومان و اجباری). + `<area>` متراژ ملک (عدد صحیح و مثبت بر حسب متر مربع و اجباری). + `<latitude>` عرض جغرافیایی ملک (عدد حقیقی و اجباری). + `<longitude>` طول جغرافیایی ملک (عدد حقیقی و اجباری). + `[description]` توضیحات اختیاری. اگر عنوان آگهی قبلاً ثبت شده باشد، پیام `invalid title` چاپ شود. در غیر این صورت، پیام `house added successfully` چاپ شود. </details> <details class="blue"> <summary> دستور `get_houses` </summary> ---------- فرم کلی این دستور به صورت زیر است: ``` get_houses -type="<type>" -status="<status>" [-min_price=<min_price>] [-max_price=<max_price>] [-min_area=<min_area>] [-max_area=<max_area>] -latitude=<latitude> -longitude=<longitude> ``` این دستور به معنی جستجو برای آگهی‌هایی با ویژگی‌های مشخص است. + `<type>` نوع ملک (مانند `apartment` یا `yard` و اجباری). + `<status>` وضعیت ملک (`sale` یا `rent` و اجباری). + `[min_price]` حداقل قیمت آگهی (عدد صحیح و اختیاری). + `[max_price]` حداکثر قیمت آگهی (عدد صحیح و اختیاری). + `[min_area]` حداقل متراژ آگهی (عدد صحیح وختیاری). + `[max_area]` حداکثر متراژ آگهی (عدد صحیح و اختیاری). + `<latitude>` عرض جغرافیایی منطقه جستجو (عدد حقیقی و اجباری). + `<longitude>` طول جغرافیایی منطقه جستجو (عدد حقیقی و اجباری). در این دستور، آگهی‌ها باید بر اساس **نزدیکی جغرافیایی** به منطقه جستجو مرتب شوند. آگهی‌هایی که نزدیک‌تر به مختصات جستجو هستند، اول نمایش داده شوند. برای محاسبه نزدیکی از فرمول فاصله هاروارد ($Haversine Formula$) استفاده کنید. سپس نام آگهی‌های مرتب‌شده را به ترتیب در یک خط و با یک فاصله بین آن‌ها چاپ کنید. (نزدیک‌ترین آگهی باید در ابتدای خط چاپ شود.) اگر لیستی که باید چاپ شود خالی است، عبارت `no house found!` را چاپ کنید. </details> <details class="blue"> <summary> دستور `remove_house` </summary> فرم کلی این دستور به صورت زیر است: ``` remove_house -name="<title>" ``` این دستور به معنی حذف آگهی با عنوان `<title>` است. + اگر آگهی با این عنوان موجود نباشد، پیام `invalid title` چاپ شود. + در غیر این صورت، پیام `house removed successfully` چاپ شود. </details> # نکات 1. تمام ورودی‌ها حروف کوچک انگلیسی و اعداد هستند و حداکثر طول هر رشته ۲۰ است. 2. قیمت و متراژ همگی مقادیر صحیح و مثبت هستند. 3. مختصات جغرافیایی (عرض و طول) مقادیر حقیقی و دقیق هستند و تا ۴ رقم اعشار در ورودی داده می‌شوند. 4. مقایسه فاصله‌ها باید تا حداقل ۴ رقم اعشار دقیق باشند و داوری کد بر اساس ۴ رقم اول اعداد انجام می‌شود. 5. تضمین می‌شود فرمت دستورهای ورودی، مطابق با صورت مسئله و معتبر هستند. 6. به حروف کوچک و بزرگ در عبارات خروجی‌ دقت کنید. برای گرفتن امتیاز کامل، خروجی شما باید کاملا شبیه عبارات در صورت مسئله باشند. # ورودی در سطر اول عدد صحیح و مثبت $n$ داده می‌شود که تعداد دستورها را مشخص می‌کند. $$1 \leq n \leq 100$$ در $n$ سطر بعدی، هر سطر شامل یک دستور از نوع‌های تعریف‌شده است. # خروجی خروجی شامل $n$ سطر است که پاسخ مناسب به هر دستور را چاپ می‌کند. # مثال‌ها ## ورودی نمونه ۱ ``` 7 add_house -name="apartment1" -type="apartment" -status="sale" -price=3000000 -area=80 -latitude=35.6895 -longitude=51.3890 add_house -name="yard1" -type="yard" -status="rent" -price=5000000 -area=200 -latitude=35.6995 -longitude=51.3900 add_house -name="yard2" -type="yard" -status="rent" -price=5000000 -area=200 -latitude=35.6995 -longitude=51.3900 add_house -name="apartment2" -type="apartment" -status="sale" -price=4000000 -area=100 -latitude=35.6985 -longitude=51.3850 get_houses -type="apartment" -status="sale" -latitude=35.6890 -longitude=51.3880 remove_house -name="yard1" get_houses -type="yard" -status="rent" -latitude=35.6890 -longitude=51.3890 ``` ## خروجی نمونه ۱ ``` house added successfully house added successfully house added successfully house added successfully apartment1 apartment2 house removed successfully yard2 ``` ## ورودی نمونه ۲ ``` 5 add_house -name="apartment1" -type="apartment" -status="sale" -price=3500000 -area=90 -latitude=35.7100 -longitude=51.3800 add_house -name="apartment2" -type="apartment" -status="sale" -price=3800000 -area=110 -latitude=35.7200 -longitude=51.3700 get_houses -type="apartment" -status="sale" -latitude=35.7100 -longitude=51.3800 get_houses -type="apartment" -status="sale" -latitude=35.7100 -longitude=51.3800 -min_price=3600000 remove_house -name="apartment2" ``` ## خروجی نمونه ۲ ``` house added successfully house added successfully apartment1 apartment2 apartment2 house removed successfully ```