- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سورنا برای کسب درآمد به کشوری سفر می‌کند که $n + 1$ جزیره دارد و جزیره‌های آن به ترتیب با اعداد $0$ تا $n$ شماره گذاری شده‌اند. او با خودش تمام زیرمجموعه‌های اعداد ۱ تا $n$ را برده است تا بفروشد!
سفر سورنا از جزیره‌ی $0$ آغاز می‌شود و هر بار از جزیره‌ی شماره $k$، به جزیره‌ی $k + 1$ می‌رود. (او نمی‌خواهد این ترتیب را تغییر دهد.)
اهالی جزیره‌ی شماره $k$، حاضرند همه زیرمجموعه‌های $k$ عضوی او را بخرند و به ازای هر زیرمجموعه، یک سکه طلا به سورنا بدهند.
تجارت پر سودی است اما مشکل اینجاست که ارزش ۱ سکه طلا $2^n$ ریال است و زمانی که سورنا از یک جزیره به جزیره‌ی بعدی می‌رود، قیمت یک سکه طلا نصف می‌شود.
توجه کنید سورنا نمی‌تواند همان لحظه بعد از معامله سکه را به پول نقد تبدیل کند و باید وقتی به کشورش برگشت سکه‌ها را تبدیل کند.
از شما می‌خواهیم کوچک‌ترین $k$ را پیدا کنید که اگر سورنا سفرش را در جزیره $k$ام پایان دهد، سود او بیشینه می‌شود.
ورودی
ورودی $t$ تست‌کیس دارد. $$1 \leq t \leq 100$$
برای هر تست، در یک سطر ورودی عدد صحیح و مثبت $n$ آمده است.
$$2 \leq n \leq 10^{18}$$
خروجی
برای هر تست، در یک سطر، کوچک‌ترین $k$ای را چاپ کنید که اگر سورنا سفرش را در این جزیره پایان دهد، سود او بیشینه می‌شود.
مثال
ورودی نمونه ۱
3
2
12
5
خروجی نمونه ۱
1
4
2
توضیح تست‌کیس سوم:
این کشور ۶ جزیره با شماره‌های ۰ تا ۵ دارد.
سورنا با خودش همه زیرمجموعه‌های مجموعه‌ی ${1, 2, \dots, 5}$ را می‌برد. همانطور که می‌دانید این مجموعه:
- ۱ زیرمجموعه‌ی ۰ عضوی
- ۵ زیرمجموعه‌ی ۱ عضوی
- ۱۰ زیرمجموعه‌ی ۲ عضوی
- ۱۰ زیرمجموعه‌ی ۳ عضوی
- ۵ زیرمجموعه‌ی ۴ عضوی
- ۱ زیرمجموعه‌ی ۵ عضوی دارد.
همچنین قیمت یک سکه طلا، ۳۲ ریال است.
- اگر سورنا بخواهد در جزیره‌ی ۰ به سفرش پایان دهد تنها زیرمجموعه تهی را می‌تواند بفروشد و ۱ سکه طلا بدست می‌آورد. باتوجه به اینکه هنوز سفر بین جزیره‌ای انجام نشده، قیمت سکه ۳۲ ریال است. پس می‌تواند در مجموع ۳۲ ریال سود کند.
- اگر سورنا بخواهد در جزیره‌ی ۱ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰ و پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱ بفروشد. پس می‌تواند ۶ سکه طلا بدست بیاورد. باتوجه به اینکه یک سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۱۶ ریال است. پس می‌تواند در مجموع ۹۶ ریال سود کند.
- اگر سورنا بخواهد در جزیره‌ی ۲ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱ و ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲ بفروشد. پس می‌تواند ۱۶ سکه طلا بدست بیاورد. باتوجه به اینکه دو سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۸ ریال است. پس می‌تواند در مجموع ۱۲۸ ریال سود کند.
- اگر سورنا بخواهد در جزیره‌ی ۳ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲ و ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳ بفروشد. پس می‌تواند ۲۶ سکه طلا بدست بیاورد. باتوجه به اینکه سه سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۴ ریال است. پس می‌تواند در مجموع ۱۰۴ ریال سود کند.
- اگر سورنا بخواهد در جزیره‌ی ۴ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲، ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳ و پنج زیرمجموعه‌ی چهار عضوی را در جزیره‌ی ۴ بفروشد. پس می‌تواند ۳۱ سکه طلا بدست بیاورد. باتوجه به اینکه چهار سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۲ ریال است. پس می‌تواند در مجموع ۶۲ ریال سود کند.
- اگر سورنا بخواهد در جزیره‌ی ۵ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲، ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳، پنج زیرمجموعه‌ی چهار عضوی را در جزیره‌ی ۴ و یک زیرمجموعه‌ی پنج عضوی را در جزیره‌ی شماره ۵ بفروشد. پس می‌تواند ۳۲ سکه طلا بدست بیاورد. باتوجه به اینکه پنج سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۱ ریال است. پس می‌تواند در مجموع ۳۲ ریال سود کند.
بنابراین بیشترین سودی که می‌تواند بکند زمانی است که در جزیره‌ی شماره ۲ به سفرش پایان دهد.
ارسال پاسخ برای این سؤال