+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای ـــــ به تازگی به ریاست یک سازمان فوقِ فوقِ مافوقِ سرّی درآمده است! امّا چند صباحی است که از منبعی موثّق شنیده در آن سازمان یک نفر مشغول جاسوسی است. نام‌برده از آن روز تا همین لحظه آرام و قرار ندارد؛ حتّی نزدیکانش نقل کرده‌اند از فرط اضطراب، آمار مصرف قرص‌های اعصابش سر به فلک کشیده است. مشاوران آقای ـــــ که بسیار نگران حال وی هستند، تصمیم گرفتند جاسوس را بیابند بلکه حال عمومی او بهبود یابد. تعداد کارمندان اداره بسیار زیاد است و برای جمعیت اندک مشاوران و معتمدان آقای ـــــ ، پیدا کردن جاسوس از بین این حجم کارمند، مانند پیدا کردن سوزنی در انبار کاه است. لذا آن‌ها تصمیم گرفتند از هر کارمند بخواهند اگر در میان افراد زیردستش به کسی مشکوک است، نام آن را سریعا اعلام کند. در این اداره هر کارمند به جز آقای ـــــ یک مدیر دارد. فرض کنید کارمندان را با اعداد طبیعی از ۱ تا $n$ شماره‌گذاری کرده‌ایم.(آقای ـــــ هم یکی از این $n$ کارمند است) شماره‌ی مدیر کارمند $i$ام را با $m_i$ نشان می‌دهیم. $m$ به ازای آقای ـــــ نیز برابر با $-1$ خواهد بود. هم‌چنین هر کارمند یک میزان اعتبار در اداره دارد. اعتبار کارمند $i$ام را $c_i$ می‌نامیم. هم‌چنین اگر کسی بخواهد بررسی کند که کارمند $i$ام جاسوس است یا نه، نیاز به صرف $t_i$ دقیقه وقت دارد. می‌گوییم کارمند $A$ زیردست کارمند $B$ است، در صورتی که $B$ مدیر $A$ باشد و یا کارمندی که مدیر $A$ است، زیردست $B$ باشد. هر کارمند برای بررسی وجود جاسوس در بین زیردستانش، باید تمام زیردستانش که اعتبارشان از اعتبار او کم‌تر است را بررسی کند و همان طور که گفته شد برای بررسی هر یک از آن‌ها نیاز به مقداری وقت دارد. شما باید به ازای هر کارمند بگویید چه قدر طول می‌کشد تا آن کارمند زیردستانش را بررسی کند. پ.ن.: نام آقای ـــــ به دلیل درخواست مکرّر مراجع قضایی از صورت سوال حذف گشت. **ویرایش:** در این سوال ممکن نیست به ازای دو کارمند، کارمند اول زیردست کارمند دوم باشد و کارمند دوم زیر دست کارمند اوّل باشد. # ورودی در سطر اوّل ورودی عدد $n$ می‌آید. در هر یک از $n$ خط بعد به ترتیب سه عدد $m_i$ و $c_i$ و $t_i$ می‌آیند. $$1 \le n, t_i, c_i \le 100 000$$ # خروجی در خط $i$ام از $n$ خط خروجی، زمانی که طول می‌کشد کارمند $i$ام زیردستانش با اعتبار کم‌تر را بررسی کند را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۵ | $n \le 5000$ | | ۲ | ۱۰ | اعتبار هر کارمند از زیردستانش بیش‌تر است | | ۳ | ۲۰ | هر کارمند زیردست حداکثر ۲۰ نفر دیگر است | | ۴ | ۶۵ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 4 4 80 1 1 40 -1 10 60 3 5 50 4 8 70 ``` ## خروجی نمونه ۱ ``` 40 0 240 120 0 ```

فوق سری

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

آقای ـــــ به تازگی به ریاست یک سازمان فوقِ فوقِ مافوقِ سرّی درآمده است! امّا چند صباحی است که از منبعی موثّق شنیده در آن سازمان یک نفر مشغول جاسوسی است. نام‌برده از آن روز تا همین لحظه آرام و قرار ندارد؛ حتّی نزدیکانش نقل کرده‌اند از فرط اضطراب، آمار مصرف قرص‌های اعصابش سر به فلک کشیده است.

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

در این اداره هر کارمند به جز آقای ـــــ یک مدیر دارد. فرض کنید کارمندان را با اعداد طبیعی از ۱ تا $n$ شماره‌گذاری کرده‌ایم.(آقای ـــــ هم یکی از این $n$ کارمند است) شماره‌ی مدیر کارمند $i$ ام را با $m_i$ نشان می‌دهیم. $m$ به ازای آقای ـــــ نیز برابر با $-1$ خواهد بود. هم‌چنین هر کارمند یک میزان اعتبار در اداره دارد. اعتبار کارمند $i$ ام را $c_i$ می‌نامیم. هم‌چنین اگر کسی بخواهد بررسی کند که کارمند $i$ ام جاسوس است یا نه، نیاز به صرف $t_i$ دقیقه وقت دارد.

می‌گوییم کارمند $A$ زیردست کارمند $B$ است، در صورتی که $B$ مدیر $A$ باشد و یا کارمندی که مدیر $A$ است، زیردست $B$ باشد.

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

پ.ن.: نام آقای ـــــ به دلیل درخواست مکرّر مراجع قضایی از صورت سوال حذف گشت.

ویرایش: در این سوال ممکن نیست به ازای دو کارمند، کارمند اول زیردست کارمند دوم باشد و کارمند دوم زیر دست کارمند اوّل باشد.

ورودی🔗

در سطر اوّل ورودی عدد $n$ می‌آید.

در هر یک از $n$ خط بعد به ترتیب سه عدد $m_i$ و $c_i$ و $t_i$ می‌آیند.

$1 \le n, t_i, c_i \le 100 000$

خروجی🔗

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

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۵	$n \le 5000$
۲	۱۰	اعتبار هر کارمند از زیردستانش بیش‌تر است
۳	۲۰	هر کارمند زیردست حداکثر ۲۰ نفر دیگر است
۴	۶۵	بدون محدودیت اضافی

مثال🔗

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

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

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: COCI 2013/2014 ---------- هوشنگ خان که به تازگی در کلاس‌های **هشینگ** ثبت نام کرده، به همه‌ی روش‌هایی که به رشته‌ها عدد نسبت می‌دهند علاقه‌ی خاصی پیدا کرده است. آخرین روشی که به او گفته شده، بیش از همه‌ی روش‌های پیشین نظر او را به خود جلب کرده؛ این روش بصورت بازگشتی و به شکل زیر تعریف می‌شود. + اگر $s$ یک رشته‌ی خالی باشد، $f(s) = 0$ + داریم $w$ یک رشته است و $c$ یک حرف کوچک انگلیسی، هم‌چنین $ord(c)$ به معنای شماره حرف $c$ بین حروف انگلیسی است؛ یعنی $ord(a) = 1$ و $ord(z) = 26$. با این‌ها، داریم: $$ f(w + c) = ((f(w) \times 33)\ xor\ ord (c)) \mod 2^m$$ که $w + c$ یعنی اضافه کردن حرف $c$ به انتهای رشته‌ی $w$. هوشنگ‌خان پس از مدتی بررسی، به امنیت این روش مشکوک شده است. برای همین به شما مقادیر $n$ و $m$ و $x$ را می‌دهد و از شما می‌خواهد که تعداد رشته‌های $n$ حرفی از حروف کوچک انگلیسی را بشمارید که مقدار $f$ برای آن‌ها برابر $x$ می‌شود. # ورودی در سطر اوّل ورودی سه عدد $n$ و $x$ و $m$ می‌آید. $$1 \le n \le 10$$ $$6 \le m \le 25$$ $$0 \le x \le 2^m$$ # خروجی در تنها خط خروجی یک عدد چاپ کنید که برابر پاسه مسئله است. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۲ | $n \le 5$ | | ۲ | ۶۸ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 1 0 10 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 1 2 10 ``` ## خروجی نمونه ۲ ``` 1 ``` کلمه‌ی تک‌حرفی `b` در این مثال شمرده می‌شود. ## ورودی نمونه ۳ ``` 3 16 10 ``` ## خروجی نمونه ۳ ``` 4 ``` این ۴ کلمه، `dxl` و `hph` و `lxd` و `xpx` هستند.

هش‌های هوشنگ

محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت
منبع: COCI 2013/2014

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

اگر $s$ یک رشته‌ی خالی باشد، $f(s) = 0$
داریم $w$ یک رشته است و $c$ یک حرف کوچک انگلیسی، هم‌چنین $ord(c)$ به معنای شماره حرف $c$ بین حروف انگلیسی است؛ یعنی $ord(a) = 1$ و $ord(z) = 26$ . با این‌ها، داریم: $f(w + c) = ((f(w) \times 33)\ xor\ ord (c)) \mod 2^m$ که $w + c$ یعنی اضافه کردن حرف $c$ به انتهای رشته‌ی $w$ .

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

ورودی🔗

در سطر اوّل ورودی سه عدد $n$ و $x$ و $m$ می‌آید.

$1 \le n \le 10$ $6 \le m \le 25$ $0 \le x \le 2^m$

خروجی🔗

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

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۳۲	$n \le 5$
۲	۶۸	بدون محدودیت اضافی

مثال🔗

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

1 0 10

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

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

1 2 10

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

کلمه‌ی تک‌حرفی b در این مثال شمرده می‌شود.

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

3 16 10

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

این ۴ کلمه، dxl و hph و lxd و xpx هستند.

کیمیا زورو

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

کیمیا که به تازگی در کلاس‌های شمشیر بازی ثبت‌نام کرده، یکی از لازمه های یک شمشیر باز ماهر را امضا زدنِ با شمشیر می‌داند. به همین منظور ابتدا ۲ عدد $A$ و $B$ را انتخاب می‌کند و سپس به ازای تمامی مقادیر صحیح ** $0 \le a < A$ و $0 \le b < B$ **خطی به معادله‌ی $y = ax + b$ روی یک کاغذ می‌کشد. (این اتفاق در کمتر از ۱ نانو ثانیه می‌افتد!) و پس از این که تمامی خطوط را با شمشیرش کشید، به یک باره تمامی کاغذ به قطعه های حاصل از ضربات شمشیر تبدیل می‌شود. وظیفه ی شما شمردن این تکه هاست! :)

ورودی🔗

در تنها خط ورودی ۲ عدد ‌ $A$ و $B$ داده می‌شود. $1 \le A , B \le 1\ 200$

خروجی🔗

در تنها خط خروجی تعداد تکه های کاغذ بعد از ضربات مرگبار کیمیا را چاپ کنید.

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۳۰	$A, B \le 200$
۲	۷۰	بدون محدودیت اضافی

مثال🔗

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

1 1

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

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

2 2

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

شکل پس از ضربات برای نمونه ۲

شکل پس از ضربات برای نمونه بالا