شارژ موبایل


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

باتری تلفن همراه مرد مالیاتچی‌ تمام شده‌است.

می‌دانیم تلفن مرد مالیاتچی برای اینکه از ii درصد شارژ به i+1i + 1 درصد برسد i+1i + 1 دقیقه زمان می‌برد.

حال ما از شما می‌خواهیم با دریافت عدد kk بگویید چند دقیقه طول می‌کشد که تلفن مرد مالیاتچی از صفر درصد شارژ به kk درصد شارژ برسد.

ورودی🔗

در یک خط عدد kk به شما داده می‌شود.

1k100 1 \le k \le 100

خروجی🔗

در یک خط مجموع دقایقی که طول می‌کشد را چاپ کنید.

مثال🔗

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

1
Plain text

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

1
Plain text

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

3
Plain text

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

6
Plain text

تکسلنگ


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

در شهر مرد مالیاتچی مردم به زبان Taxlang با یک دیگر سخن میگویند که شامل حروف T و A و X و M و N میباشد. بدلیل اینکه این شهر مربوط به سال 1717 قبل از میلاد است برای نوشتن یک عبارت، بلوک هایی متناظر با کاراکتر های آنرا بر روی دیواره ی غارها حک می‌کنند. به طور دقیق تر این زبان از چپ به راست خوانده شده و شامل بلوک هایی به طول ۵ و ارتفاع ۳ می‌باشد و هر بلوک دقیقا با یکی از حروف این زبان متناظر است که با مشاهده ورودی‌های نمونه می‌توانید به راحتی تناظر میان آنها را کشف کنید.

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

ورودی🔗

ورودی شامل سه خط از کاراکترها می‌باشد. طول هر خط مضربی از ۵ بوده و حداکثر ۱۰۰ می‌باشد.

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

خروجی🔗

در تنها سطر خروجی ترجمه متن داده شده را خروجی دهید.

مثال🔗

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

*****
oo*oo
oo*oo
Plain text

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

T
Plain text

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

oo*oo
o***o
*ooo*
Plain text

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

A
Plain text

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

*ooo*
oo*oo
*ooo*
Plain text

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

X
Plain text

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

**o**
*o*o*
*ooo*
Plain text

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

M
Plain text

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

*ooo*
*o*o*
*ooo*
Plain text

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

N
Plain text

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

*****oo*oo*ooo***o**oo*oo*ooo*
oo*ooo***ooo*oo*o*o*o***o*o*o*
oo*oo*ooo**ooo**ooo**ooo**ooo*
Plain text

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

TAXMAN
Plain text

مرد مالیاتچی و جاعل


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

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

یک فیش مالیاتی رشته‌ای به طول nn است که تنها از ۰ و ۱ درست شده است.

حال فیشی تقلبی است که حداقل یکی از رشته‌های زیر، حداقل یک بار، در آن آمده باشد:

110,101,111,011 110, 101, 111, 011

برای فهم بیشتر به نمونه‌ها و توضیحشان مراجعه کنید.

دقت کنید که هر فیشی که تقلبی نباشد اصل است.

ورودی🔗

در تنها سطر ورودی nn آمده است که نمایانگر اندازه‌ی رشته‌ی فیش‌ها می‌باشد. 1n100 0001 \le n \le 100 \ 000

خروجی🔗

در تنها سطر خروجی باقیمانده‌ی تعداد فیش‌های اصل بر 109+710^9 + 7 را چاپ کنید.

مثال🔗

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

4
Plain text

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

6
Plain text

توضیح نمونه‌ی اول

فیش‌های زیر تقلبی اند: 0011,0101,0110,0111,1010,1011,1100,1101,1110,1111 0011, 0101, 0110, 0111, 1010, 1011, 1100, 1101, 1110, 1111 فیش‌های زیر اصل هستند: 0000,0001,0010,0100,1000,1001 0000, 0001, 0010, 0100, 1000, 1001

پس از کل ۱۶ حالت فیش‌ها، ۱۰ تا تقلبی و ۶ تا اصل هستند که چون سوال تعداد اصل‌ها را خواسته‌ است جواب برابر ۶ می‌شود.

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

3
Plain text

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

4
Plain text

اداره مالیات


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

در اداره مالیات nn مالیات‌چی وجود دارد.

مالیات‌چی ii ام می‌تواند از aia_i نفر خاص در شهر مالیات بگیرد.

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

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

مثلا مالیات چی اول و دوم هر کدام می‌توانند به ترتیب از ۷ و ۸ نفر در شهر مالیات بگیرند اما ۳ نفر از این افراد مشترک است، پس چنانچه بخواهیم دو نفر مالیات‌چی نگه داریم و این دو نفر را انتخاب کنیم ما از ۱۲ نفر می‌توانیم مالیات بگیریم نه از ۱۵ نفر.

برای فهم بهتر سوال بخش ورودی را بخوانید.

ورودی🔗

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

سپس در خط بعد nn عدد که aia_i هاست به شما داده می‌شود.

در خط سوم qq به شما داده می‌شود و در qq خط بعدی در هر خط ابتدا یک عدد tit_i می‌آید و سپس tit_i تا عدد که اندیس مالیات‌چی‌هاست و یک عدد kik_i که یعنی آن tit_i تا مالیات‌چی در kik_i تا از مردم شهر با هم مشترک هستند.

** دقت کنید که اشتراک‌هایی که به شما داده می‌شوند از هم جدا و کاملا مستقل هستند؛ یعنی مثلا اگر مالیاتچی‌های ۱ و ۲ و ۳ در ۵ نفر و مالیاتچی‌های ۱ و ۲ در ۴ نفر با هم اشتراک داشته باشند، طبیعتا این ۴ نفر کاملا مستقل از آن ۵ نفر بوده و هیچ اشتراکی ندارند. **

1mn20 1 \le m \le n \le 20 1q10 1 \le q \le 10 2tin 2 \le t_i \le n 1ai100 1 \le a_i \le 100

برای فهم بهتر توضیح نمونه ۱ را بخوانید.

خروجی🔗

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

مثال🔗

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

5 3
15 20 25 30 24
5
2 1 2 7
3 1 2 3 3
2 2 3 2
2 3 4 5
2 4 5 6 
Plain text

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

68
Plain text

بهترین حالت این است که مالیات‌چی دوم و چهارم و پنجم را انتخاب کنیم، که از آنجایی که مالیات چی ۴ و ۵ در ۶ نفر باهم مشترک هستند جواب آخر برابرست با ۶ - ۲۰ + ۳۰ + ۲۴.

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

3 3
3 3 3
1
3 1 2 3 2
Plain text

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

5
Plain text

فرار مالیاتچی


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

متاسفانه باخبر شدیم که آقای مالیاتچی، به کشور فلان فرار مالیاتی کرده است!

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

به یک رشته خوب می‌گوییم اگر حرفی در آن وجود داشته باشد که حداقل به اندازه‌ی نصف طول آن رشته آمده باشد. برای مثال رشته‌ی abab خوب است در حالی که رشته‌ی abcabc خوب نیست. حال به شما یک رشته می‌دهیم و شما باید تعداد زیررشته‌های خوب آن را خروجی دهید.

ورودی🔗

در تنها سطر ورودی یک رشته که تنها از حروف کوچک انگلیسی درست شده است آمده است. طول این رشته بین ۱ تا 10510^5 می‌باشد.

خروجی🔗

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

مثال🔗

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

aaa
Plain text

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

6
Plain text

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

z
Plain text

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

1
Plain text