Solution to Contest Problems (with explanation in bangla)
shahidul.cse.brur
Solution to Contest problem
Contest name: BRUR An easy long run contest for B5 & B6
Contest link: acm.hust.edu.cn/vjudge/contest/view.action?cid=64541#overview
Password: xyz
Contest Arranged by:
Md. Abul Kalam Azad, lecturer, BRUR.
Email: akaz...@gmail.com
--------------------------------
This solution is prepared by-
Md. Shahidul Islam,
Student of CSE, BRUR (5th batch),
Email: shahidul...@gmail.com
Contact: 01731 749956
01521 426424
Problem A
এটি একটি অত্যন্ত সহজ প্রোবলেম ছিল । ১ থেকে ৯ পর্যন্ত নামতা প্রিন্ট করতে হবে । তবে প্রত্যেক নামতা হবে ৯ম টার্ম পর্যন্ত । কোন ইনপুট দেয়া থাকবে না।
এক্ষেত্রে দুইটা লুপ চলবে, একটি নামতার ঘরের জন্য , অন্যটি টার্ম এর জন্য ।
Code:
#include<stdio.h>
int main()
{
int i, j;
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
printf("%dx%d=%d\n",i,j,i*j);
}
return 0;
}
Problem B
অত্যন্ত সহজ সমস্যা । একটি স্ট্রিং দেয়া থাকবে, উলটা করে প্রিন্ট করতে হবে ।
টেকনিকঃ
প্রথমে স্ট্রিং ইনপুট নিয়ে length বের করব । তারপর শেষ থেকে শুরু পর্যন্ত প্রিন্ট করব ।
Code:
#include<stdio.h>
#include<string.h>
int main()
{
char str[50];
int len, i;
scanf("%s",&str);
len=strlen(str);
for(i=len-1;i>=0;i--)
printf("%c",str[i]);
printf("\n");
return 0;
}
Problem C
একটি নাম্বার সিকুয়েন্স দেয়া থাকবে, এদের মাঝে কতগুলি সংখ্যা এমন আছে যেটি তার আগের ও পরের সংখ্যার চেয়ে বড় ।
প্রথমে টেস্ট কেস এর মান (t) দেয়া থাকবে । তারপর প্রত্যেক কেসে মোট কতগুলি সংখ্যা থাকবে তার মান (n) দেয়া থাকবে । তারপর n সংখ্যক নাম্বার দেয়া থাকবে, যা অ্যারেতে ইনপুট নিতে হবে ।
যেহেতু আগের ও পরের সংখ্যার সাথে তুলনা করতে হবে, তাই লুপ দুই থেকে n-1 পর্যন্ত চলবে ।
Code:
#include<stdio.h>
int main()
{
freopen("input.txt", "r", stdin);
int t, n, i,pk, num[60];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
pk=0;
for(i=2;i<=n-1;i++)
if(num[i]>num[i-1] && num[i]>num[i+1])
pk++;
printf("%d\n",pk);
}
return 0;
}
Problem D
এটি ছিল সবচেয়ে সহজ প্রোবলেম । একটি সংখ্যা (a) দেয়া থাকবে , যাকে দুইটি সংখ্যার যোগফল (b+c) আকারে দেখাতে হবে ।
টেকনিকঃ
সহজ বুদ্ধি হল সবসময় একটি সংখ্যাকে 1 ধরে অপর সংখ্যা হবে a-1 ।
অর্থাৎ, 1+(a-1)=a
b=1, c=a-1
Code:
#include<stdio.h>
int main()
{
int a, b, c;
while(scanf("%d",&a)!=EOF)
{
b=1;
c=a-b;
printf("%d %d\n",b,c);
}
return 0;
}
Problem E
এটি ছিল জ্যামিতি রিলেটেড মিডিয়াম প্রোবলেম । একটা কুয়া থাকবে আর কিছু ঢাকনা থাকবে, প্রিন্ট করতে হবে কতগুলি ঢাকনা কুয়ার ভিতর ফেলা যাবে ।
প্রথম লাইনে দুইটি সংখ্যা (f ও s) দেয়া থাকবে , যা দিয়ে কুয়ার ধরন ও উপরের অংশের দৈর্ঘ্য বুঝা যাবে । f=1 হলে কুয়াটি বৃত্তাকার এবং s দিয়ে এর ব্যাসার্ধ বুঝাবে। f=2 হলে বর্গাকার, f=3 হলে ত্রিভুজাকার বুঝাবে, সেক্ষেত্রে s দিয়ে দৈর্ঘ্য বুঝাবে ।
দ্বিতীয় লাইনে একটি নাম্বার n দেয়া থাকবে, যা দিয়ে বুঝাবে n সংখ্যক ঢাকনা আছে ।
এরপর n সংখ্যা লাইনে প্রত্যেক ঢাকনার বর্ণনা থাকবে, যাদের প্রত্যেক লাইনে দুইটি করে সংখ্যা থাকবে । এর প্রথম সংখ্যা ঢাকনার ধরন ও দ্বিতীয় সংখ্যা এর দৈর্ঘ্য বুঝাবে (কুয়ার মত)।
টেকনিকঃ
কুয়ার মুখের সর্বোচ্চ ফাকা স্পেস বের করব, আর ঢাকনার মুখের সর্বনিম্ন দৈর্ঘ্য বের করব । তারপর চেক করব যে ঢাকনার মুখের সর্বনিম্ন দৈর্ঘ্য কুয়ার মুখের সর্বোচ্চ ফাকা স্পেস এর চেয়ে ছোট কিনা । ছোট হলে ঢাকনা কুয়ার ভিতর ফেলা যাবে, নতুবা যাবে না ।
কুয়ার সর্বোচ্চ ফাকা স্পেস নির্ণয়ঃ
বৃত্তাকার হলে, ব্যাসই হবে কুয়ার সর্বোচ্চ ফাকা স্পেস ।
বর্গাকার হলে, কর্ণই হবে কুয়ার সর্বোচ্চ ফাকা স্পেস ।
ত্রিভুজাকার হলে, বাহুর দৈর্ঘ্যই হবে কুয়ার সর্বোচ্চ ফাকা স্পেস ।
ঢাকনার সর্বনিম্ন দৈর্ঘ্য নির্ণয়ঃ
ঢাকনা বৃত্তাকার হলে, ব্যাস (২*ব্যাসার্ধ) হবে ঢাকনার সর্বনিম্ন দৈর্ঘ্য।
বর্গাকার হলে, বাহুর প্রদত্ত দৈর্ঘ্যই হবে ঢাকনার সর্বনিম্ন দৈর্ঘ্য।
ত্রিভুজাকার হলে, যে কোন শীর্ষবিন্দু থেকে তার বিপরীত বাহুর উপর অংকিত লম্বই হবে ঢাকনার সর্বনিম্ন দৈর্ঘ্য, যা বিপরীত বাহুকে সমদ্বিখন্ডিত করবে । যদি বাহুর দৈর্ঘ্য siz দিয়ে প্রকাশ করি, তবে
Siz^2 = (বিপরীত বাহুর উপর অংকিত লম্ব )^2 + (siz/2)^2
So, বিপরীত বাহুর উপর অংকিত লম্ব = sqrt(3.0)/2.0*siz;
Sqrt() এর ব্যবহার আছে বলে, কিছু ভেরিয়েবল double হিসেবে নিতে হবে ।
Code:
#include<stdio.h>
#include<math.h>
#define M 1e-6
int main()
{
freopen("input.txt", "r", stdin);
int f, corno, lombo, i, n, cover, cnt;
double maximum, minimum, s, siz;
scanf("%d %lf",&f,&s);
if(f==1)
{
maximum=s*2.0;
}
else if(f==2)
{
maximum=sqrt(2.0)*s;
}
else if(f==3)
{
maximum=s;
}
scanf("%d",&n);
cnt=0;
for(i=1;i<=n;i++)
{
scanf("%d %lf",&cover, &siz);
if(cover==1)
minimum=2.0*siz;
else if(cover==2)
minimum=siz;
else if(cover==3)
minimum=sqrt(3.0)/2.0*siz;
if(minimum<=maximum)
cnt++;
}
printf("%d\n",cnt);
return 0;
}
Problem F
সমস্যা ও সমাধান টেকনিকঃ
অনেক মজার সমস্যা এটি । মনে করি, ১ম ঝুড়িতে a সংখ্যক বেরী ও ২য় ঝুড়িতে b সংখ্যক বেরী ছিল ।
প্রথমে বেরী ভর্তি ১ম ঝুড়ি ও ২য় ঝুড়ির ভর মাপা হল (a1 ও b1) ।
এখানে, a1= ১ম খালি ঝুড়ি + a ----------------------(১)
আর b1= ২য় খালি ঝুড়ি + b ------------------------(২)
এবার ২য় ঝুড়ির সব বেরী ১ম ঝুড়িতে ঢালা হল । অতপর ১ম ঝুড়ির ভর হল a2 ও এবং ২য় খালি ঝুড়ির ভর পাওয়া গেল b2 ।
তাহলে (২) থেকে পাই, b=b1 - ২য় খালি ঝুড়ি
= b1 –b2 ;
এবার ১ম ঝুড়ির সব বেরী ২য় ঝুড়িতে ঢালা হল । এবং ১ম খালি ঝুড়ির ভর পাওয়া গেল a3 .
তাহলে (২) থেকে পাই, a=a1 – ১ম খালি ঝুড়ি
= a1 – a3 ;
Code:
#include <stdio.h>
int main()
{
int a1,b1,a2,b2,a3,b3,a,b;
scanf("%d %d",&a1,&b1);
scanf("%d %d",&a2,&b2);
scanf("%d %d",&a3,&b3);
a=a1-a3;
b=b1-b2;
printf("%d %d\n",a,b);
return 0;
}
Problem G
আমি এটি সমাধান করিনি । :D
Problem H
একটি অ্যারেতে N সংখ্যক নাম্বার আছে । এখন ০ থেকে M পর্যন্ত প্রত্যেকটি সংখ্যা এই অ্যারেতে কয় বার আছে, তা চেক করতে মোট কত সেকেন্ড সময় লাগবে বের করতে হবে, যেখানে প্রত্যেক লাইন লিখতে ১ সেকেন্ড লাগে, আর প্রত্যেক কন্ডিশন একটি আলাদা লাইনে লেখা হয় । তার মানে মোট কতগুলি কন্ডিশন চেক করতে হবে সেটাই বের করতে হবে।
0 থেকে M পর্যন্ত মোট M+1 টি সংখ্যা আছে। অ্যারের N সংখ্যক ইন্ডেক্স এর প্রত্যেক টিতেই M+1 টি কন্ডিশন চেক করতে হবে, তাই মোট কন্ডিশন হবে N*(M+1) সংখ্যক ।
Code:
#include<stdio.h>
int main()
{
int m, n, ans;
scanf("%d %d", &n, &m);
ans=n*(m+1);
printf("%d\n", ans);
return 0;
}
Problem I
দুইটি স্ট্রিং দেয়ে আছে, এরা পরস্পর রিভার্স বা Palindrome হলে YES নতুবা NO প্রিন্ট করতে হবে ।
Code:
#include<stdio.h>
#include<string.h>
int main()
{
int i, j, k, len;
char f[150],s[150], rev[150];
scanf("%s",&f);
scanf("%s",&s);
len=strlen(f);
for(i=0;i<len;i++)
rev[i]=f[len-1-i];
rev[len]='\0';
if(strcmp(s, rev)==0)
printf("YES\n");
else
printf("NO\n");
return 0;
}
Problem J
প্রাথমিক ভাবে আমার কাছে কিছু টাকা (b) আছে, এবং n সংখ্যক দিনের কোন দিন ডলারের দাম কত তা দেয়া আছে । n সংখ্যক দিন শেষে সর্বোচ্চ মোট কত টাকা হবে তা বের করতে হবে । ডলার শুধু একবারই বিক্রি করা যাবে ।
টেকনিকঃ
যেদিন কিনব কেবল তার পরের যে কোন দিনেই বিক্রি করতে পারব, কারন অই দিনেই বিক্রি করলে আসল থাকবে, লাভ হবে না ।
n সংখ্যক দিনের কোন দিন ডলারের দাম কত তা a[] অ্যারেতে রাখব । এবার দুইটা লুপ চালাব । ১ম দিন থেকে n-1 দিন পর্যন্ত প্রত্যেক দিনেই ডলার এর ক্রয়মুল্যের জন্য (i), তার পর দিন থেকে শেষ দিন পর্যন্ত
( j ) বিক্রয় মুল্য চেক করব । যে ক্ষেত্রে সবচেয়ে বেশী লাভ হবে, সেটিই সঠিক উত্তর ।
a[i] টাকায় কেনা যায় ১ ডলার
So, b টাকায় কেনা যায় b/a[i] ডলার
So, amount= b/a[i]
ক্রয়মুল্য = amount*a[i]
রইল = b- amount*a[i]
বিক্রয়মুল্য = amount*a[ j ]
হল = b- amount*a[i] + amount*a[ j ]
আমরা শুধু b- amount*a[i] + amount*a[ j ] চেক করব, যেটা বেশী হবে সেটাই উত্তর ।
Code:
#include<stdio.h>
int main()
{
long long int n, b, a[2009], i, j, last, amount;
scanf("%lld %lld",&n,&b);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
last=b;
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
amount=b/a[i];
if(b-amount*a[i] + amount*a[j] > last)
last=b-amount*a[i] + amount*a[j];
}
}
printf("%lld\n", last);
return 0;
}
Problem K
N এর মান দেয়া আছে এবং তারপর N সংখ্যক স্ট্রিং দেয়া আছে । যে স্ট্রিং এর দৈর্ঘ্য ১০ এর বড় নয় তা প্রিন্ট করতে হবে । আর ১০ এর বড় হলে ১ম character ও শেষ character প্রিন্ট করতে হবে, এবং এই দুই character এর মাঝে এই দুই character ছাড়া আর যতগুলি character আছে সেই সংখ্যাটি প্রিন্ট করতে হবে ।
টেকনিকঃ
প্রথমে strlen() দিয়ে স্ট্রিং এর দৈর্ঘ্য বের করব । ১০ এর বড় হলে ১ম character ও শেষ character প্রিন্ট করতে হবে, এবং এই দুই character এর মাঝে এই দুই character ছাড়া আর যতগুলি character আছে সেই সংখ্যাটি (length – 2) প্রিন্ট করতে হবে ।
Code:
#include<stdio.h>
#include<string.h>
int main()
{
char wrd[150];
int n, len, i;
scanf("%d",&n);
while(n--)
{
scanf("%s",&wrd);
len=strlen(wrd);
if(len>10)
{
printf("%c",wrd[0]);
printf("%d",len-2);
printf("%c\n",wrd[len-1]);
}
else
printf("%s\n",wrd);
}
return 0;
}
Problem L
সমান সংখ্যক 4 ও 7 নিয়ে গঠিত সংখ্যাই সুপার লাকি সংখ্যা । একটি সংখ্যা(n) দেয়া আছে, এর সমান বা বড় সুপার লাকি সংখ্যাটি প্রিন্ট করতে হবে ।
টেকনিকঃ
n এর সর্বোচ্চ মান 10^9 পর্যন্ত দেয়া হবে । তাই আমরা ২, ৪, ৬ ও ৮ ডিজিটের সব সুপার লাকি সংখ্যা ছোট থেকে বড় আকারে অ্যারেতে রাখব । শেষে ১০ ডিজিটের সব চেয়ে ছোট সুপার লাকি সংখ্যাটি রাখব । এরপর n এর মান ইনপুটের পর লুপ চালিয়ে চেক করব, যখনই কোন মান n এর সমান বা বড় হবে সেটিই হবে উত্তর, আর লুপ থামিয়ে দেব ।
Code:
#include<stdio.h>
int main()
{
long long int L[]={47,74, 4477,4747,4774,7447,7474,7744, 444777,447477,447747, 447774,474477,474747,474774,
477447,477474,477744,744477,744747,744774,747447,747474,747744,774447,774474,774744,777444,
44447777,44474777,44477477,44477747,44477774,44744777,44747477,44747747,44747774,
44774477,44774747,44774774,44777447,44777474,44777744,47444777,47447477,47447747,47447774,47474774,47477447,47477474,
47477744,47747744,47774744,47777444,74444777,74447477,74447747,74447774,74474477,74474747,74474774,74477447,74477474,
74477744,74744477,74744747,74744774,74747447,74747474,74747744,74774447,74774474,74774744,74777444,77444477,77444747,
77444774,77447447,77447474,77447744,77474447,77474474,77474744,77477444,77744447,77744474,77744744,77747444,77774444,4444477777};
long long int i,n,ans;
scanf("%lld",&n);
for(i=0;i<=89;i++)
{
if(L[i]>=n)
{
ans=L[i];
break;
}
}
printf("%lld\n",ans);
return 0;
}
Problem M
letter, space, ও punctuation সহ একটি স্ট্রিং দেয়া থাকবে, নিচের নিয়ম অনুযায়ী মডিফাই করতে হবে-
১। একাধিক স্পেস পাশাপাশি থাকতে পারবে না ।
২। punctuation এর পর অবশ্যই স্পেস হবে ।
৩। punctuation এর আগে অবশ্যই স্পেস হবে না।
টেকনিকঃ
আমরা এডিট করে সেভ করব না, বরং সাথে সাথেই প্রিন্ট করব ।
স্ট্রিং length বের করে ১ম থেকে শেষ পর্যন্ত প্রতি character জন্য লুপ চালাব ।
১। যদি character টি letter হয়, তবে প্রিন্ট করব ।
২। যদি character টি space হয়, তবে এরপরে যতক্ষন space আছে, ignore করব । তারপর দেখব এই স্পেসের পরের character টি letter হয়, তবেই space প্রিন্ট করব ।
৩। যদি character টি punctuation হয়, তবে তা প্রিন্ট করব এবং এরপরেই space প্রিন্ট করব ।
এরপরে যতক্ষন space আছে, ignore করব ।
৪। সবশেষে একটি \n print করব ।
Code:
#include<stdio.h>
#include<string.h>
int main()
{
char ln[10009];
int i, len;
gets(ln);
len=strlen(ln);
for(i=0;i<len;i++)
{
if(ln[i]>='a' && ln[i]<='z')
{
printf("%c",ln[i]);
}
else if(ln[i]==' ')
{
while(ln[i]==' ')
{
i++;
}
if(ln[i]>='a' && ln[i]<='z')
{
printf(" ");
}
i--;
}
else
{
printf("%c ",ln[i]);
i++;
while(ln[i]==' ')
{
i++;
}
i--;
}
}
printf("\n");
return 0;
}
Problem N
দেয়ালে পোস্টকার্ড ও ফটো আছে । এখান থেকে এদেরকে নিভৃত কক্ষে বা রুমে নিয়ে যেতে হবে । একই সাথে দুই প্রকার অর্থাৎ, পোস্টকার্ড ও ফটো একই সাথে হাতে নেয়া যাবে না । একপ্রকার হাতে থাকা অবস্থায় অন্য প্রকার এসে গেলে হাতে যেটা আছে সেটা আগে রুমে রেখে আসতে হবে । আবার একই সাথে একপ্রকারের (পোস্টকার্ড বা ফটো) ৫ টির বেশী হাতে থাকা যাবে না, সেগুলো আগে রুমে রেখে আসতে হবে।
একটি স্ট্রিং দেয়া থাকবে যাতে কেবল C ও P থাকবে । C মানে পোস্টকার্ড আর P মানে ফটো) ।
প্রিন্ট করতে হবে সর্বনিম্ন কতবার রুমে যেতে হবে ।
টেকনিকঃ
Variable cnt ও hand যথাক্রমে রুমে যাবার সংখ্যা ও হাতে থাকা পোস্টকার্ড বা ফটো এর সংখ্যা বুঝাবে ।
১। যদি পরপর দুটি letter একই না হয়, তবে cnt এর মান এক বাড়াব এবং hand মান ০ করব ।
২। যদি পরপর দুটি letter একই হয়, তবে hand এর মান এক বাড়াব । যখনি hand এর মান ৫ হবে cnt এর মান এক বাড়াব এবং hand মান ০ করব ।
Code:
#include<stdio.h>
#include<string.h>
int main()
{
int i, cnt, hand, len;
char str[120];
scanf("%s",&str);
len=strlen(str);
cnt=hand=0;
for(i=0;i<len-1;i++)
{
if(str[i]!=str[i+1])
{
cnt++;
hand=0;
}
else if(str[i]==str[i+1])
{
hand++;
if(hand==5)
{
cnt++;
hand=0;
}
}
}
cnt++;
printf("%d\n",cnt);
return 0;
}
Problem O
N সংখ্যক ইন্তেজার নাম্বারের সিকুয়েন্সকে permutation বলা হবে, যদি সিকুয়েন্সে ১ থেকে N পর্যন্ত সব সংখ্যাই একবার থাকে।
N সংখ্যক ইন্তেজার নাম্বারের সিকুয়েন্স দেয়া আছে । মিনিমাম কতটি সংখ্যা চেঞ্জ করলে এটি permutation হবে তা প্রিন্ট করতে হবে ।
টেকনিকঃ
ইনপুট নেবার আগেই অ্যারের সব মান ০ করে রেখে দেব ।
তারপর যে নাম্বার ইনপুট দেয়া হবে , সেই ইন্ডেক্স্বে অ্যারের মান ১ করে দেব । ফাইনালি, দেখব অ্যারেতে কতগুলো ০ আছে , সেটাই হবে উত্তর ।
Code:
#include<stdio.h>
int main()
{
int prev[5009], n, i, cnt, a;
scanf("%d",&n);
for(i=1;i<=5000;i++)
prev[i]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a);
prev[a]=1;
}
cnt=0;
for(i=1;i<=n;i++)
{
if(prev[i]==0)
cnt++;
}
printf("%d\n",cnt);
return 0;
}
Problem P
ত্রিভুজের ৩ বাহু (a,b,C) দেয়া আছে, এটি সমকোণী হলে yes আর না হলে no প্রিন্ট করতে হবে ।
টেকনিকঃ
জাস্ট পীথাগোরাসের উপপাদ্য ।
Code:
#include<stdio.h>
int main()
{
long long int a, b, c, t, cas;
scanf("%lld",&t);
for(cas=1;cas<=t;cas++)
{
scanf("%lld %lld %lld",&a,&b,&c);
if(a*a==(b*b+c*c) || b*b==(a*a+c*c) || c*c==(b*b+a*a))
printf("Case %lld: yes\n",cas);
else
printf("Case %lld: no\n",cas);
}
return 0;
}
Problem Q
একটি ফাংশন দেয়া আছে, অপ্টিমাইজ করে rewrite করতে হবে ।
টেকনিকঃ
এটা Fibonacci number এর মত । এক্ষেত্রে শুধু দুইটির পরিবর্তে পুর্ববর্তী ৬ টি সংখ্যা যোগ করে নতুন সংখ্যা বানাতে হবে ।
যেহেতু কোড যেভাবে দেয়া আছে, তাতে Data overflow ও Time Limit Exceed হবে তাই মডুলার অ্যারিথম্যাটিকস ব্যবহার করতে হবে ।
সুত্রঃ
(a+b+c+……..)%m =(a%m + b%m + c%m +……………)%m
এবং (a*b*c*……..)%m =(a%m * b%m *c%m *……………)%m
Code:
#include<stdio.h>
int main()
{
long long int cas, t, sq[10010],a,b,c,d,e,f,n,i;
scanf("%lld", &t);
for(cas=1;cas<=t;cas++)
{
scanf("%lld %lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &e, &f, &n);
sq[0]=a;
sq[1]=b;
sq[2]=c;
sq[3]=d;
sq[4]=e;
sq[5]=f;
for(i=6;i<=n;i++)
{
sq[i]=(sq[i-1]%10000007+sq[i-2]%10000007+sq[i-3]%10000007+sq[i-4]%10000007+sq[i-5]%10000007+sq[i-6]%10000007)%10000007;
}
printf("Case %lld: %lld\n", cas, sq[n] % 10000007);
}
return 0;
}