سلام.
امروز تقریبا از ساعت ۱:۳۰ تا ۳:۳۰ دومین دوره‌ی مسابقه‌ی برنامه نویسی ب.ب.م (بهترین برنامه نویس مدرسه) در دبیرستان دوره‌ی نخست (راهنمایی) استعدادهای درخشان شهیدصدوقی برگذار شد.
این آزمون دارای ۶ سوال بود که مسابقه‌دهندگان باید سوالات رو در مدت ۱ساعت و ۴۵ دقیقه حل می‌کرد و خوش بختانه مثل پارسال نشد و میشد همه‌ی سوالا رو با بیسیک(!) (زبان جالبی نیست اگه نمیدونید چیه بهتره ندونید!) بنویسن!
همچنین برای اینکه استرس بهشون وارد کنم هر مدت میومدم بهشون میگفتم تا الآن چندم هستن که اذیت بشن در حد مطلوب! :)
خوب حالا میریم دیگه سر اصل مطلب.
در آغاز فایل مسابقه و همچنین فایل کدبازش رو قرار میدم. ( که در اون تمام عکس‌های استفاده شده و همچنین پی‌اس‌دی اشون وجود داره)
http://bayanbox.ir/id/1999472901411073344
البته سوال ششم رو یه اشتباهی کرده بودم که سوال ششم داده بودم چون پاسخش ساده بود ولی الگوریتمش رو میخواستی بزنی به فنا می‌رفتی!
پرسش نخست - برادر علی
برادر علی به تازگی با مقسوم علیه‌های اعداد آشنا شده‌است و می‌داند مثلا عدد ۱۵ مضربی از ۳ است و حال برای تمرین بیشتر از علی می‌خواهد تا برای او سوالی مطرح کند تا او بیشتر یاد بگیرد.
علی به او می‌گوید «برو و مجموع اعداد ۱ تا 139۳ که مضرب ۳ یا ۵ یا ۷ یا ۱۳ هستند را پیدا کن و به من بگو»
به برادر علی کمک کنید تا پاسخ این سوال را پیدا کند.
دقیقن چیزی که گفته رو بنویسیم پاسخ پرسش به دست میاد.
یعنی گفته برای اعداد ۱ تا ۱۳۹۳ پس یه فور میزنی برای i از ۱ تا ۱۳۹۳
گفته اگه بر ۳ یا ۵ یا ۷ یا ۱۳ بخش پذیر بود این i امون بیا جمعش رو بگو.. این هم یه متغیر s تعریف میکنی و اینجا i تا بهش اضافه میکنی.
کد فایل برای basic
dim s as long For i = 1 to 1393 if i mod 3 = 0 or i mod 5 = 0 or i mod 7 = 0 or i mod 13 = 0 then s = s + i Next print s
کد فایل به زبان c++
#include <iostream>
#include <conio.h>
using namespace std;
int main(){
int s = 0;
for(int i = 1;i<=1393;i++) {
if(i%3 == 0 || i%5 == 0 || i%7==0 || i%13 == 0) s+=i;
}
cout<<s;
getch();
return 0;
}
پرسش دوم - مقسوم‌علیه‌ها
برادر علی بعد از آشنایی با مقسوم علیه‌ها ، سوالی در ذهنش پیش آمد، سوال او از این قرار بود ۱۴ امین مقسوم علیه عدد ۱۳۹۲ چند است؟
به برادر علی کمک کنید تا به پاسخ سوالش برسد.
برای مثال مجموعه مقسوم علیه‌های عدد ۱۲ {1,2,3,4,6,12} است که پنجمین مقسوم علیه آن ۶ است.
خوب این سوال هم مثل برنامه‌ی محاسبه تعداد مقسوم علیه‌ها هست با این تفاوت که وقتی ۱۴ شد باید عدد رو چاپ کنه! :)
cls c = 0 For i = 1 to 1392 if 1392 mod i = 0 then c = c + 1 if c = 14 then print i:end end if Next
و با c++:
#include <iostream>
#include <conio.h>
using namespace std;
int main(){
int c = 0;
for(int i = 1;i<=1392;i++) {
if ( 1392 % i == 0) {
c++;
if (c == 14) {
cout<<i;
break;
}
}
}
getch();
return 0;
}
پرسش سوم قدیم: (این پرسش برای اینکه به نظرمیرسیده سخت هست حذف شده و پرسش سوم کنونی که پرسش دوم قدیم بوده اومده جاش و پرسش دوم ساده تر طرح شده)
علی کتابی n صفحه‌ای دارد، او شماره‌ی صفحات این کتاب را به ترتیب از چپ به راست پشت سر هم می‌نویسد و یک عدد بزرگ به دست می‌آورد مثل
۱۲۳۴۵۶۷۸۹۱۰۱۱۱۲۱۳۱۴۱۵۱۶۱۷۱۸۱۹۲۰۲۱۲۲۲۳۲۴۲۵۲۶۲۷۲۸۲۹۳۰...
علی این عدد بزرگ را نزد خودش نگه می‌دارد و از این عدد بزرگ یک معما ساخته و به برادرش می‌گوید. معمای علی از این قراراست «عددی که من روی این کاغذ نوشته‌ام دارای ۱۳۹۳ رقم یک است، کتاب من چند صفحه دارد؟»
به برادر علی کمک کنید و پاسخ این معما را در کادر پاسخ بنویسید.
خوب این سوالش بوده، چون توی آزمون نبوده حوصله ندارم جوابش رو بدم ولی خیلی ساده هست اولش یه حلقه درست میکنی با while چون تعداد مهم نیست یا با for مثلا برای از ۱ تا ۳۰۰۰ تعداد یکها رو میشماری به این صورت که مثلا یکان میشه عدد باقی‌مانده‌اش بر ۱۰ - دهگان میشه باقی‌مانده‌ی عدد بر ۱۰۰ تقسیم بر ۱۰ و ... یکان دهگان صدگان و اینا رو محاسبه میکنی و می‌بینی اونایی که یک بود متغیر شمارنده‌ی ۱ هات مثلا c رو +1 میکنی بعدش چک میکنی اگه = 1393 بود عدد رو چاپ میکنی.
پرسش سوم جدید! - خرد کردن پول
پدر علی برای گرفتن پول به یکی از دستگاه‌های خودپرداز (ATM) می‌رود.
این دستگاه خود پرداز اسکناس‌های ۱۰تومانی، ۵۰تومانی و ۱۰۰ تومانی به مقدار بینهایت دارد.
پدر علی مقدار ۲۵۰۰ تومان پول را به چندطریق میتواند از این دستگاه خودپرداز بگیرد؟مثال ۱: به طور مثال ۲۵۰۰ تومان پول برابر با ۵۰ تا اسکناس ۵۰ تومانی است یا برابر با ۴۸ تا اسکناس پنجاه تومانی و۱ اسکناس ۱۰۰ تومانی است.
مثال ۲: اگر مقدار پولی که پدر علی می‌خواست ۲۵۰ تومان بود، ۱۲ حالت مختلف برای اینکار وجود داشت.
خوب این هم ساده هست(من خودم این سوال رو توی ۳۰ ثانیه حل کردم با اول که دیدم!)
۳ تا فور تودرتو برای تعداد ۱۰ تومانی‌ها و ۵۰ تومانی‌ها و ۱۰۰ تومانی‌ها که مثلا اولیش از ۱ تا ۲۵۰ - دومیش از ۱ تا ۵۰ - سومیش از ۱ تا ۲۵ بعد میای می‌بینی این تعداد سکه برابر با ۲۵۰۰ میشه یا نه، اگه شد c رو +1 می‌کنیم.
کد به زبان بیسیک:
cls
for i = 1 to 250
for j = 1 to 50
for k = 1 to 25
if i * 10 + j * 50 + k * 100 = 2500 then c = c +1
Next
Next
Next
print c
کد به زبان c++ :
#include <iostream>
#include <coino.h>
using namespace std;
int main(){
int s = 0;
for(int i = 0;i<=250;i++)
for(int j = 0;j<=250;j++)
for(int k = 0;k<=250;k++)
if(i*10+j*50+k*100 == 2500) s++;
cout<<s;
getch();
return 0;
}
پرسش چهارم - فاکتوریل بزرگ
در هفته‌ی بعد پرسش نخست، برادر علی با مفهوم فاکتوریل آشنا می‌شود، او می‌داند که مقدار
n! = 1×۲×۳×...×(n-1)×n
است، این‌بار معلم ریاضی ایشان به آنها گفته‌که «هرکس بتواند بگوید که در مقابل !۱۰۰۰۰ چند صفر قرار دارد، به نمره‌ی مستر او ۲ نمره اضافه خواهد کرد»
حال برادر علی از علی می‌خواهد تا برنامه‌ای بنویسد که پاسخ این سوال را بیابد، برای اینکار به علی کمک کنید.
به طور مثال !۱۰ برابر با 3628800 بوده و در مقابل آن ۲ صفر وجود دارد.
این سوال هم ساده هست. برای به‌دست آوردن تعداد ۰ های یک عدد باید ببینیم چندتا عامل ۱۰ داره، تعداد عامل‌های ۱۰ هم برابر با تعداد عامل‌های ۵ هست چون یکی در میون حداقل یکی ۲ توش هست پس ۵ ها حتما کمترن.
خوب ۵ تا ۵ تا ۱ عامل پنج دیده میشه - عدد ۲۵ دوتا عامل پنج داره پس ۲۵ تا ۲۵ تا یکی دیگه عامل پنج دیده میشه - ۱۲۵ تا ۱۲۵ تا دوباره یکی دیگه و ....
خوب همین رو کدش رو بنویسید.
cls i = 1 c = 0 while 5 ^ i <= 10000 c = c + ( 10000 \ (5 ^ i)) i = i + 1 Wend print c
و برای c++ :
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
int main(){
int n,c,i;
n = 10000;
c = 0;
i = 1;
while(pow(5,i) <= n) {
c += (n / pow(5,i));
i++;
}
cout<<c;
getch();
return 0;
}
پرسش پنجم - ماشین حساب
علی با کمک دوستانش یک ماشین‌حساب جدید اختراع کرده‌اند.
این ماشین‌حساب تنها ۳ کلید به نام‌های ۱و ۲ و ۳ دارد.
کلید ۱ عدد ماشین‌حساب را سه‌برابر می‌کند.
کلید ۲ عدد ماشین‌حساب را به‌اضافه‌ی ۴ می‌کند.
کلید 3 عدد ماشین‌حساب را به‌اضافه‌ی ۵ می‌کند.
برای به‌دست‌آوردن عدد ۹۳ درصورتی که نخست عدد دو را داشته‌باشیم چه حرکاتی نیاز است؟ (حداقل حالت ممکن)
به طور مثال برای عدد ۱۲کافی است دو‌بار عدد را به‌اضافه‌ی ۵ کنیم یعنی باید در کادر پاسخ‌گویی عبارت ۳۳ را بنویسیم.
این سوال رو خیلیا ننوشتن کدش و خودشون رو به فنا دادن با تست کردن جواب رو به دست آوردن!
ولی حالا حلش.
سوال ۳ رو اگه بلد باشید و این رو بلد نباشید یعنی سوال ۳ رو بلد نیستید! :)
حالا روش حل.
بدیهی هست که با یک کلید نمیشه حل کرد سوال رو.
با دوتا کلید حداکثر عددی که میشه به دست آورد ۲۱ هست که پس به درد نمی‌خوره.
با سه‌تا کلید حداکثر عددی که بهش میشه رسید ۶۳ هست پس به درد نمی‌خوره.
با چهار تا کلید به عدد ۱۸۹ حداکثر میشه رسید پس باید به ۹۳ هم بشه رسید.
ما ۴ تا فور تودرتو می‌نویسیم (که همه‌اشون از ۱ تا ۳ هستن) برای ۴ تا کلیدی که میزنیم.
بعد میایم با این چهارتا کلید می‌بینم به چه عددی می‌رسیم اگه ۹۳ بود چهارتا متغیر فور‌هامون رو چاپ می‌کنیم.
خوب حل شد دیگه! :)
کد با بیسیک:
توضیح دادم کافیه دیگه!
کد با c++ :
#include <iostream>
#include <conio.h>
using namespace std;
void mashin(int &a,int action) {
switch(action) {
case 1:
a *= 3;
break;
case 2:
a += 4;
break;
case 3:
a += 5;
break;
}
}
int main(){
int a;
for (int i1 = 1; i1 <= 3;i1++) {
for (int i2 = 1; i2 <= 3;i2++) {
for (int i3 = 1; i3 <= 3;i3++) {
for (int i3 = 1; i3 <= 3;i3++) {
a = 2;
mashin(a,i1);
mashin(a,i2);
mashin(a,i3);
mashin(a,i4);
if( a == 93) {
cout<<i1<<i2<<i3<<i4;
getch();
return 0;
}
}
}
}
}
getch();
return 0;
}
پرسش ششم - علی و جعبه‌ها
علی دارای تعدادی جعبه با تحمل‌های متفاوت است، برای مثال اگر تحمل جعبه‌ای x باشد به معنی این است که می‌توان x جعبه روی این جعبه گذاشت.
علی می‌خواهد این جعبه‌ها را روی هم بچیند و کمترین تعداد ستون ممکن را بسازد.
برای مثال اگر ۳ جعبه با ظرفیت‌های ۲و۱و۱ داشته باشد میتواند جعبه با ظرفیت ۲ را در زیر و سپس دو جعبه با ظرفیت ۱ را روی آنها قرار دهد و یک ستون بسازد.
حال علی دارای ۱۰۰ جعبه هست که ۴۰ تا از آنها ظرفیت ۱، ۳۰ تا از آنها ظرفیت ۲، ۲۰ تا ازآنها ظرفیت ۳و ۱۰ تا از آنها ظرفیت ۴ دارد، علی این جعبه‌ها را حداقل در چند ستون میتواند قرار دهد؟
به طور مثال با جعبه‌هایی با ظرفیت ۰،۰،۱۰ دو ستون و با ظرفیت‌های ۰،۱،۲،۳،۴ یک ستون و با ظرفیت‌های ۰،۰،۰،۰ نیاز به چهار ستون جعبه است.
فکر کنم این تنها سوالی هست که علی به برادرش نمی‌گه سوالاش رو حل کنه! :دی
خوب من این سوال رو از کانتست ۲۲۸ وب‌سایت کدفورسز برداشتم البته در اونجا باید کدی می‌نوشتی که برای همه‌ی چیزها جواب بده.
پس :
راه حل یکم:
این راه حل بسیار دشوار هست و من خودم چون دوباره روی سوال تغییر کرده فکر نکردم فکر کردم بچه‌ها هم دنبال این راه حل می‌گردن ولی اینطور نبود!
ما الگوریتم چیدن روی هم رو میزنیم.
به این صورت که اول میایم جعبه‌ها رو به ترتیب ظرفیت به صورت از بزرگ به کوچیک مرتب می‌کنیم.
فرض می‌کنیم همه‌اشون رو توی n ستون چیدیم که هر ستون فقط یک جعبه داشته باشه.
یک متغیر هم تعریف می‌کنیم برای تعداد ستون‌ها، هر ستون چندتا چیز داره ۱- تعداد جعبه‌ی داخلش ۲- ظرفیت باقی مانده اش و همچنین هر جعبه‌هم دوتا چیز داره ۱- ظرفیتش ۲- ستونی که درش قرار داره
بعد میایم اولین ستون رو درنظر می‌گیرم که بیشترین ظرفیت رو داره، تا جای ممکن ستون‌های بعدیش رو به این انتقال می‌دیم.
بعد برای ستون دوم هم همین کار رو می‌کنیم.
تا آخر.
بعد در آخر تعداد ستون‌ها رو توی یک متغیر ریخته بودیم اون رو چاپ می‌کنیم.
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
int n, max,maxid, c,d, x;
n = 100;
x = n;
int a[n],b[n],m[n],e[n];
for(int i =0;i<40;i++) a[i] = 1;
for(int i =40;i<70;i++) a[i] = 2;
for(int i =70;i<90;i++) a[i] = 3;
for(int i =90;i<100;i++) a[i] = 4;
for(int i = 0;i<n;i++) {
max = -1;
for(int j = i;j<n;j++) {
if(a[j] > max) {
max = a[j];
maxid = j;
}
}
c = a[maxid];
a[maxid] = a[i];
a[i] = c;
}
for(int i = 0;i<n;i++) {
b[i] = i;
m[i] = a[i];
e[i] = 1;
}
for(int i = (n-1);i>=1;i--) {
for(int j = (i-1);j>= 0;j--) {
if(m[j] >= e[i]) {
// کل ستون رو بدیم به ستون اون یکی
for(int k = 0;k<n;k++) {
if(b[k] == i) {
b[k] = j;
}
}
m[j] = m[j] - e[i];
if(m[i] < m[j]) m[j] = m[i];
e[j] = e[j] + e[i];
x = x-1;
break;
}
}
}
if( x<= 0) x = 1;
cout<<x;
system("PAUSE");
return 0;
}
البته نویسنده‌اش با باینری سرچ حلش کرده تقریبا که خیلی الگوریتمش از الگوریتم من بهتره و ساده تره.
https://github.com/ATofighi/CF228/blob/master/D1A.cpp
خوب راه دوم:
اگه ما یک ۴ رو اول - بعد روش یک ۳ - بعد یه ۲ - بعد دوتا ۱ بزاریم یک ستون با حداکثر چیزی که میشد ساختیم.
اگه تا جای ممکن این ستون رو بسازیم، ۱۰ تا ستون ساخته شد
حالا ۲۰ تا ۱ - ۲۰ تا ۲ - ۱۰ تا ۳ و ۰ تا ۴ داریم.
حالا می‌تونیم ۳ - ۲ - ۱ - ۱ رو بسازیم که این هم ۱۰ تا ستون میشه ساخت باهاش.
باقی مانده میشه ۱۰ تا ۲
ما می‌تونیم با این ۲ هامون چنین ستونی بسازیم.
۲-۲-۲ که ۳ تا ستون اینجوری ساخته میشه.
و یک ۲ باقی میمونه که اون رو هم توی یک ستون می‌زاریم که در مجموع
۱۰+۱۰+۳+۱=۲۴ :)
مواردی که نیاز می‌دونم بگم.
خوب کسایی که شرکت کردید خوب دادید مغرور نشید چون سوالا سخت نبودن و زمان زیادی داشت! :)
کسایی که خوب ندادید، سعی کنید نگاهتون رو به برنامه نویسی عوض کنید، قبل از کدنویسی درباره چیزی که باید بنویسید فکر کنید، خود سوال داره داد میزنه راه حلم چیه :) و همچنین کاغذ و قلم هم چیز خوبیه هم برای فکر کردن باهاش و هم برای نوشتن فکرتون.
بقیه‌ی بحثم با کسایی هست که خوب دادن:
حتما بشینید C++ رو یاد بگیرید اگه می‌خواید خفن بشید.
برای بیشتر آشنا شدن یه گروه تشکیل بدید توی حلی‌نت شرکت کنید، تا متوجه ضعیف بودنتون بشید. :)
وقتی C++ یاد گرفتید توی سایت codeforces.com عضو بشید و توی کانتست هاش شرکت کنید تا یاد بگیرید.
سعی کنید مسائل مربوط به ترکیبیات رو بخونید و یاد بگیرید چون کاربرد زیادی توی کامپیوتر داره
برید الگوریتم هم بفهمید چیه الگوریتم های مرتب سازی و اینا رو هم یاد بگیرید.
اگه می‌خواید المپیادی بشید سعی کنید توی باشگاه علمی پژوهشی جوان عضو باشید و چندهفته یکبار زنگ بزنید ببینید کلاسی چیزی نذاشته باشن چون عموما یادشون میره اطلاع رسانی کنند! :)
دیگه کاریتون ندارم.
برید خوش باشید.
----
پانوشت:
کدهایی که با بیسیک نوشته شده رو تست نکردم ممکنه مثلا متغیری که آخر باید چاپ می‌کردم رو اشتباه نوشته باشم مثلا چون در حین نوشتن همین پست کدها رو هم همینجا نوشتم! :)
خلیلی
