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

امین عاشق بیسکویت ساقه طلایی شکلاتی است. هر بسته بیسکویت ساقه طلایی شکلاتی شامل $n$ عدد بیسکویت است و هر بیسکویت دارای $x$ گرم روکش شکلات است.

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

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

ورودی🔗

در تنها سطر ورودی، سه عدد $n$، $x$ و $k$ با فاصله می‌آیند که به ترتیب نشان‌دهنده تعداد بیسکویت‌های در هر بسته، مقدار شکلات اولیه‌ی روی هر بیسکویت و تعداد بیسکویت‌های برداشته شده توسط امین است. $1 \leq n, x \leq 10,000$ $1 \leq k \leq n$

خروجی🔗

در تنها سطر خروجی، مجموع مقدار شکلات روی بیسکویت‌های برداشته شده توسط امین را خروجی دهید.

مثال‌ها🔗

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

10 500 4

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

1500

در این حالت $n = 10$ بیسکویت شکلاتی در بسته قرار دارد و روی هر بیسکویت $x = 500$ گرم شکلات قرار دارد، امین $k = 4$ بیسکویت اول را بر می‌دارد، پس شکلات‌های مابین بیسکویت اول و دوم، دوم و سوم و سوم و چهارم را خواهد خورد که در مجموع $3 \times 500 = 1500$ گرم می‌شود.

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

9 100 9

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

800

در این حالت $n = 9$ بیسکویت شکلاتی در بسته قرار دارد و روی هر بیسکویت $x = 100$ گرم شکلات قرار دارد، امین هر $k = 9$ بیسکویت را بر می‌دارد، پس همه‌ی شکلات‌ها به‌جز شکلات روی بیسکویت آخر را خواهد خورد که در مجموع $8 \times 100 = 800$ گرم می‌شود.

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

17 150 1

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

0

در این حالت $n = 17$ بیسکویت شکلاتی در بسته قرار دارد و روی هر بیسکویت $x = 150$ گرم شکلات قرار دارد، امین هر $k = 1$ بیسکویت را بر می‌دارد که هیچ شکلاتی روی آن قرار ندارد.

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

ما یک رشته‌ی $m$ بیتی داریم (یعنی تمام کاراکترهای آن 0 و 1 هستند) به صورت $a_1, a_2, \dots, a_m\,$ و این رشته را با استفاده از کدگذاری همینگ ($Hamming \,Code$) کدگذاری کرده‌ایم.

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

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

در روش کدگذاری همینگ، اگر $m$ تعداد بیت‌های رشته‌ی اصلی و $r$ تعداد بیت‌های توازن باشد، شرط زیر باید برقرار باشد: $2^r \geq m + r + 1$

برای محاسبه‌ی $r$، کوچک‌ترین عدد طبیعی را انتخاب می‌کنیم که این رابطه را ارضا کند.
برای مثال، اگر $m = 11$ باشد، مقدار $r = 4$ خواهد بود.

سپس رشته‌ی جدیدی به طول $n = m + r$ (شامل بیت‌های اصلی و بیت‌های توازن) به صورت $b_1, b_2, \dots, b_{n}$ می‌سازیم. بیت‌های توانی از ۲ ($1, 2, 4, 8, \dots$) برای بیت‌های توازن رزرو می‌شوند و باقی بیت‌ها به ترتیب از رشته‌ی اصلی پر می‌شوند.

برای مثال، اگر $m = 11$ و رشته‌ی اصلی برابر 01010111010 باشد، رشته‌ی جدید به صورت ??0?101?0111010 ساخته می‌شود.

در مرحله‌ی بعد، مقدار هر بیت توازن $b_{2^i}$ ($i$ از $0$ تا $r-1$) را به صورت یای‌انحصاری ($XOR$) بیت‌هایی از رشته‌ی $b$ که در موقعیت‌های باینری آن‌ها بیت $i$ برابر ۱ است، محاسبه می‌کنیم.

یک رشته‌ی $n$ بیتی به ما داده شده که طبق کدگذاری همینگ ساخته شده است. از شما خواسته می‌شود که بررسی کنید آیا رشته دارای خطا است یا خیر و اگر رشته دقیقاً یک خطا دارد، موقعیت خطا را شناسایی و رشته را اصلاح کنید و اگر رشته معتبر نباشد (مثلاً بیش از یک خطا داشته باشد)، INVALID چاپ کنید.

ورودی🔗

در خط سطر اول ورودی، عدد صحیح $t$ آمده که تعداد تست‌ها را نشان می‌دهد.

$1 \leq t \leq 1000$

در سطر اول هر تست، یک عدد صحیح $n$ آمده که طول رشته‌ی باینری کدگذاری شده را نشان می‌دهد. $2 \leq n \leq 100,000$

در سطر دوم هر تست، یک رشته‌ی باینری $n$ بیتی شامل کاراکترهای 0 و 1 داده می‌شود که کاراکترهای رشته‌ی کدگذاری شده را به‌ترتیب نشان می‌دهد.

تضمین می‌شود مجموع مقادیر $n$ در تمام تست‌کیس‌ها از $1,000,000$ بیشتر نخواهد شد.

خروجی🔗

برای هر تست، در سطر اول، YES، اگر رشته دارای خطاست، NO، اگر رشته بدون خطاست و INVALID، اگر رشته نامعتبر است. همچنین اگر رشته خطا داشت و اصلاح شد، در خط دوم رشته‌ی اصلاح‌شده را چاپ کنید.

مثال‌ها🔗

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

3
4
1010
11
10101001110
8
00000000

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

YES
1110
INVALID
NO

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

شرکت ارتباطات سینا دو عدد رجیستر دارد که در هر کدام از آن‌ها یک عدد در مبنا ۲ و با استفاده از $n$ حافظه که هر کدام 0 و یا 1 هستند، ذخیره شده است. می‌خواهیم دو عدد این رجیسترها را با یکدیگر جمع بزنیم. همانطور که در مبنای ۱۰ وقتی می‌خواهیم دو عدد را جمع بزنیم، در هر جایگاه یک رقم بین 0 الی 9 به جایگاه بعدی منتقل می‌شود، در هنگام جمع زدن دو عدد در مبنای ۲، نیز هنگاه جمع زدن دو عدد در هر جایگاه یک رقم که می‌تواند 0 و یا 1 باشد به جایگاه بعدی منتقل می‌شود. به این رقم $carry$ می‌گوییم.

در این سوال دو عددی که داخل رجیسترها ذخیره شده‌اند را داریم. اما در هر دوی رجیسترها بعضی از رقم‌ها نویز داشته‌اند و نمی‌دانیم داخل آن‌ها 0 نوشته شده است و یا 1. اما می‌دانیم حداکثر یکی از این ارقام نویز خورده برابر 1 است و بقیه آن‌ها برابر 0 هستند.

کسی خبر رسانده است که وقتی این دو عدد را جمع می‌کنیم، به ازای هر جایگاهی که $carry$ آن برابر $1$ باشد، رجیسترها یک واحد ناراحت می‌شوند. برای اینکه بتوانیم بیشترین میزان ممکن رجیسترها را ناراحت کنیم سوال زیر از شما پرسیده شده است.

در بین تمام حالاتی که دو عدد ما می‌توانند باشند. به این معنی که حداکثر یکی از ارقام نویز گرفته برابر 1 و بقیه برابر 0 باشند، بیشترین تعداد $carry$ ای که در زمان جمع زدن این دو عدد برابر با 1 خواهد بود چند تا است.

ورودی🔗

در سطر اول ورودی عدد $n$ داده می‌شود که نشان‌دهنده تعداد ارقام دو عدد مورد نظر در مبنا دو است.

$1 \leq n \leq 100,000$

سپس در سطر دوم و سوم دو عدد به طول $n$ رقم و در مبنای دو ورودی داده می‌شوند. هر رقم از این دو عدد با 0 و یا 1 و یا کاراکتر ؟ نمایش داده می‌شود. که علامت سوال نشان‌دهنده نویز در رقم مشخص شده است.

خروجی🔗

در تنها خط خروجی باید یک عدد خروجی دهید که نشان‌دهنده بیشترین تعداد $carry$ برابر با 1 ای است که جمع این دو رجیستر می‌تواند داشته باشد. دقت کنید خروجی شما باید عددی بین $0$ و $n$ باشد.

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

5
101?1
00101

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

3

در این حالت اگر تنها علامت‌سوال را برابر عدد 1 در نظر بگیریم بیشترین میزان ممکن که برابر ۳ عدد $carry$ است را تولید می‌کنیم.

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

5
111?1
0001?

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

5

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

5
1???1
?1111

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

5

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

تعداد $n+1$ لوله آزمایشگاهی داریم که در هر کدام $k$ توپ وجود دارد. توپ‌ها شامل $n$ نوع رنگ هستند که از هر رنگ دقیقا $k$ توپ وجود دارد. لوله آخر یعنی لوله شماره $n+1$ام خالی می‌باشد.

در هر عملیات می‌توان بالاترین توپ یک لوله را به روی توپ‌های یک لوله دیگر قرار داد، در صورتی که لوله مقصد کمتر از $k$ توپ درون آن وجود داشته باشد.

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

ورودی🔗

در سطر اول ورودی عدد $n$ و سپس $k$ داده می‌شود که به ترتیب نشان‌دهنده تعداد انواع رنگ‌ها و ظرفیت هر لوله است.

$1 \leq n, k \leq 1000$

سپس در $n$ سطر بعدی در هر سطر $k$ عدد داده می‌شود که نشان‌دهنده شماره رنگ توپ‌‌ها ‌در آن لوله از پایین به بالا می‌باشد. شماره گذاری رنگ‌ها از شماره $1$ شروع می‌شوند و رنگ ‌‌$i$ام شماره $i$ را دارد.

خروجی🔗

در سطر اول خروجی یک عدد $m$ خروجی دهید که نشان‌دهنده تعداد عملیات‌های مورد نیاز شما برای رسیدن به هدف می‌باشد. سپس در $m$ سطر بعدی در هر سطر بگویید که در آن مرحله توپ بالایی لوله شماره ‌$a$ را به بالای لوله شماره $b$ می‌اندازید.

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

مثال‌ها🔗

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

2 3
1 1 2 
2 2 1 

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

3
1 3
2 1
3 2

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

3 4
1 1 1 2 
2 2 3 2 
3 3 1 3 

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

6
1 4
3 4
3 1
2 3
4 3
4 2

در این پروژه، باید یک سامانه نظرسنجی آنلاین برای بازی‌های شهرآورد طراحی کنید که از طریق سوکت‌ها، ارتباط بین یک سرور و چندین کلاینت را مدیریت کند. هر کلاینت باید بتواند به سرور متصل شده و به یک گزینه رأی دهد. پس از پایان رأی‌گیری، سرور باید نتایج را جمع‌آوری و به کلاینت‌ها اعلام کند.

پروژه اولیه🔗

پروژه‌ی اولیه را می‌توانید از این لینک دانلود کنید. ساختار این فایل به صورت زیر است:

vote.zip
├── client.c
└── server.c

نحوه‌ی اجرا کردن پروژه🔗

بعد از اجرا کردن دستورهای زیر به ترتیب server و client راه‌اندازی می‌شوند.

gcc -std=gnu11 -o server server.c -lpthread
./server <port>
gcc -std=gnu11 -o client1 client.c 
./client1 <port>
gcc -std=gnu11 -o client2 client.c 
./client2 <port>
...

جزئیات پیاده‌سازی🔗

راه‌اندازی سرور🔗

• سرور باید بتواند چندین کلاینت را به صورت همزمان مدیریت کند.
• سرور باید روی پورت <port> تنظیم شود که مقدار آن به‌صورت آرگمان ورودی داده می‌شود.
• اگر هنگام ساختن سوکت با خطا مواجه شد بلافاصله خطای Socket Error را چاپ کند.
• اگر این پورت قابل استفاده نیست بلافاصله خطای Bind Error را چاپ کند.
• در صورتی که هیچ کدام از خطاهای بالا رخ نداد،‌سرور باید بعد از راه‌اندازی بلافاصله پیام Ready To Get Votes... را به صورت استاندارد چاپ کند.

پس از اتصال هر کلاینت، سرور باید متن و گزینه‌های نظرسنجی را به هر کلاینت ارسال کند و از آن‌ها درخواست کند که یک عدد (نمایانگر گزینه) را به عنوان رای انتخاب کنند. متن پیام نظرسنجی باید عبارت زیر باشد:

Who Is Winner?
1.Persepolis
2.Esteghlal

سرور پس از دریافت رأی از هر کلاینت، باید رأی را ذخیره کرده و بلافاصله پیام We Got Your Vote. را برای تأیید رأی به کلاینت ارسال کند. در صورتی که رأی کاربر برابر 1 یا 2 نیست. بلافاصله عبارت Invalid Vote. را باید به کلاینت ارسال کند.

سرور پس از دریافت هر رأی از از کلاینت‌ها، نتیجه‌ی رای‌گیری را به‌صورت زیر چاپ کند.

Current Votes: Persepolis: 6 Esteghlal: 4

کلاینت🔗

• هر کلاینت باید از طریق همان <port> بتواند به سرور متصل شود و گزینه‌های رأی‌گیری را دریافت کند.
• کلاینت باید بتواند یکی از گزینه‌ها را انتخاب کرده و آن را به سرور ارسال کند.
• پس از ارسال رأی، کلاینت باید پیام تأیید رأی را از سرور دریافت کند.

شرایط و محدودیت‌ها🔗

• برای مدیریت هر کلاینت باید از یک thread یا پروسه جداگانه در سرور استفاده شود.
• از پروتکل TCP برای ارتباط پایدار و از send و recv برای ارسال و دریافت داده‌ها استفاده شود.

آنچه باید آپلود کنید🔗

[your-solution-file-name].zip
├── client.c
└── server.c