/*
Time: 0.012 sec
UserName: php(Hasib Al Muhaimin)
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=293
*/
#include<cstdio>
#include<iostream>
using namespace std;
#define MAX 30001
int coins[5];
unsigned long long int dp[MAX];
void change()
{
for(int i = 0; i<5; i++)
{
for(int j = coins[i]; j<MAX; j++)
{
dp[j] += dp[j - coins[i]];
}
}
}
int main()
{
coins[0] = 1;
coins[1] = 5;
coins[2] = 10;
coins[3] = 25;
coins[4] = 50;
dp[0] = 1;
change();
int i;
while(scanf("%d", &i) == 1)
{
if(dp[i]>1)
{
//cout<<"There are "<<dp[i]<<" ways to produce "<<i<<" cents change.\n";
printf("There are %llu ways to produce %d cents change.\n", dp[i], i);
}
else
{
//cout<<"There is only 1 way to produce "<<i<<" cents change.\n";
printf("There is only 1 way to produce %d cents change.\n", i);
}
}
}
Monthly Archives: October 2012
(UVa) 674 – Coin Change
0
/*
UserName: php(Hasib Al Muhaimin)
Time: 0.032
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=615
*/
#include<cstdio>
#define MAX 7490
int coins[] = {1, 5, 10, 25, 50};
unsigned long long int dp[MAX];
int main()
{
dp[0] = 1;
for(int i = 0; i<5; i++)
{
for(int j = coins[i]; j<MAX; j++)
{
dp[j] += dp[j - coins[i]];
}
}
int i;
while(scanf("%d", &i) == 1)
{
printf("%llu\n", dp[i]);
}
return 0;
}
(UVa) 11137 – Ingenuous Cubrency
0This problem/solution introduce with Unlimited Coin Change problem. Note How the unsigned int used… Without using huge sized int, there may be overflow occurred.
/*
Time: 0.008 sec
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2078
UserName: php(Hasib Al Muhaimin)
*/
#include<iostream>
using namespace std;
#define MAX 10000
int cube(int i)
{
return i*i*i;
}
unsigned long long int dp[MAX];
void coinChange()
{
for(int i = 1; i<22; i++)
{
int cube_of_i = cube(i);
for(int j = cube_of_i; j<MAX; j++)
{
dp[j] = dp[j - cube_of_i] + dp[j];
}
}
}
int main()
{
for(int i = 1; i<MAX; i++ )
dp[i] = 0;
dp[0] = 1;
coinChange();
int i;
while(cin>>i)
{
cout<<dp[i]<<endl;
}
return 0;
}
PHP Standard I/O (for Contest)
0
<?php
if($_SERVER['HTTP_HOST'] == '127.0.0.1') {
$file = fopen('input.txt', 'r');
} else {
$file = STDIN;
}
while(($line = fgets($file)) !== false) {
$line = trim($line);
if($line == 42)
break;
echo $line . "\n";
}
?>
(UVa) 10664 – Luggage
0
/*
problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1605&mosmsg=Submission+received+with+ID+10809486
Username: php
Time: 0.008s
*/
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std;
#define MAX 200
#define pb push_back
#define SZ size()
void free(int ara[])
{
for(int i=0; i<MAX; i++)
{
ara[i] = 0;
}
}
int main()
{
int load[MAX];
int cases;
char *ptr, str[10000];
int i;
int totalSum;
queue<int> Q;
cin>>cases;
gets(str);
while(cases--)
{
free(load);
load[0] = 1;
while(Q.SZ)
{
Q.pop();
}
totalSum = 0;
gets(str);
for(ptr = strtok(str, " "); ptr; ptr = strtok(NULL, " "))
{
i = atoi(ptr);
Q.push(i);
totalSum += i;
}
if(totalSum % 2 || totalSum == 0)
{
cout<<"NO"<<endl;
continue;
}
totalSum = totalSum / 2;
while(Q.SZ)
{
i = Q.front();
for(int j = totalSum-1; j>-1; j--)
{
if(i+j <= totalSum && load[j] != 0)
{
load[i+j] = load[i] + load[j];
}
}
Q.pop();
}
if(load[totalSum] != 0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
(lightOj) 1005 – Rooks
0Sometimes Overflow causes a Great problem!! It can hang you on WA. Here is a code which will overflow if we use Multiplication before Division. As we Use Division first then Multiplication, The chance to Overflow reduced.
//lightOj
//problem id: 1005 - Rooks
// link: http://lightoj.com/volume_showproblem.php?problem=1005
#include<iostream>
#include<cstdio>
using namespace std;
unsigned long long dp[1000];
unsigned long long rec(int i)
{
if(i==1)
{
return 1;
}
if(dp[i] != 0)
{
return dp[i];
}
dp[i] = i * rec(i-1);
return dp[i];
}
int main()
{
int cases, caseno = 0;
int n, k;
cin>>cases;
unsigned long long result;
unsigned long long backTrack;
while(cases--)
{
cin>>n>>k;
if(k==0)
{
printf("Case %d: 1\n", ++caseno);
continue;
}
if(n<k)
{
printf("Case %d: 0\n", ++caseno);
continue;
}
result = n*n;
backTrack = n*n;
for(int i=1; i<k; i++)
{
backTrack = (backTrack - 2*n + 1);
result = (result / i)*backTrack ; //note that how the overflow avoided!!
n--;
}
result /= k;
cout<<"Case "<<++caseno<<": "<<result<<endl;
}
return 0;
}
(UVa) 100 – The 3n + 1 problem
0
//UVa User: php(Hasib Al Muhaimin)
//Time Limit: 0.020 s
//problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
// I don't know why The time limit is changing if i change the array size
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<map>
using namespace std;
#define MAX 100000
int dp[MAX];
int rec(int n)
{
if(n==1)
{
return 1;
}
if(n<MAX)
{
if(dp[n] != -1)
{
return dp[n];
}
if(n%2 == 0)
{
dp[n] = 1 + rec(n/2);
}
else
{
dp[n] = 1 + rec(3*n + 1);
}
return dp[n];
}
else
{
if(n%2 == 0)
{
return 1 + rec(n/2);
}
else
{
return 1 + rec(3*n + 1);
}
}
}
int main()
{
for(int i=0; i<MAX; i++)
{
dp[i] = -1;
}
int a, b;
int max, r;
int i, j;
while(cin>>a>>b)
{
i = a;
j = b;
if( a > b){
a ^= b ^= a ^= b;
}
max = 0;
b++;
for(int i=a; i<b; i++)
{
r = rec(i);
if(r>max)
{
max = r;
}
}
cout<<i<<" "<<j<<" "<<max<<endl;
}
return 0;
}
গণনাযন্ত্র পূর্বলিখন (শুরুর কথা)
2গণিতবিদ চার্লস ব্যাবেজ সাহেব যখন কম্পিউটার এর ধারণা দিয়েছিলেন তখন তিনি ভেবেছিলেন এই যন্ত্রখানা দিয়ে অনেক জটিল জটিল হিসাব নিকাশ খুব সহজে করা যাবে। তো তারপর অনেকগুলা বছর কেটে গেল। কম্পিউটার এর এত বেশী উন্নতি সাধন হল যে কম্পিউটার এর আসল উদ্দেশ্য থেকে আমরা যোজন যোজন দূরে গিয়ে শুধু মাত্র গেমস খেলা, মুভি দেখা, গান শোনাতেই মগ্ন থাকি। ব্যাপারটা বেশ পীড়াদায়ক!!! তাই চেষ্টা করব প্রোগ্রামিং এর শুরুর দিকের কিছু এখানে লিখে রাখতে। তবে একটা জিনিস, এই ব্লগ টা পড়ে থেমে থাকবে না!! আমি শুধু দরজাটা দেখিয়ে দিতে পারি, দরজা খুলে করিডোরে হাঁটা, আর করিডোর এর সব দরজা খুলে দেখা তোমাদের দায়িত্ব!!!
তো প্রোগ্রামিং শেখার শুরু করার জন্য যে জিনিসটা লাগবে সেটা হল একটা কম্পাইলার। কম্পাইলার জিনিসটা অনেকটা দোভাষীর মতো কাজ করে। আগে কম্পিউটার এর সাথে কথা বলার জন্য মোটামুটি কম্পিউটার এর নিজের ভাষা(বাইনারি) এর কাছাকাছি কথা বলা লাগত। এখন প্রোগ্রামিং জিনিসটা অনেক বেশী সহজ হয়ে গিয়েছে। আমি এখানে সি++ ল্যাঙ্গুয়েজ টাই শিখানোর চেষ্টা করব। কারণ সি++ ল্যাঙ্গুয়েজ টা বোঝা খুব বেশী সহজ এবং সি/সি++ কেউ শেখার পর তার জন্য অন্য যেকোনো প্রোগ্রামিং ল্যাঙ্গুয়েজ শেখা খুব সহজ। আরেকটা কারণ ও কিন্তু আছে। দুনিয়ায় যত প্রোগ্রামিং কনটেস্ট আছে সবখানে মাত্র অল্প কয়েকটা ল্যাঙ্গুয়েজ ইউজ করতে দেয়!! বেশিরভাগ ক্ষেত্রেই সি, সি++ আর জাভা। এদের মধ্যে শুরু করার জন্য সি++ সবচেয়ে ভাল এবং সি++ তে কোড লিখলে কেমন যেন কনটেস্ট মুড আসে!! যেটা সবচেয়ে মজার!!
তো বেশীর ভাগ মানুষ ইউজ করে কোড ব্লক্স। এটা ওপেন কোর্স+ফ্রী সফটওয়্যার। সফটওয়্যার টা ফ্রী ডাউনলোড করা যাবে কোডব্লক্স এর অফিসিয়াল ওয়েবসাইট থেকে। আর যাদের কাছে এই মুহুর্তে কম্পিউটার নেই তারাও কিন্তু শিখতে পারো যদি ইন্টারনেট কানেকশন থাকে!! http://ideone.com/ এও কোড লিখতে পারো, কোন কিছু ডাউনলোড না করেই, আর ইচ্ছা করলে মোবাইল থেকেও কোড লিখতে পারবে এখনে!!! ইনস্টল করার পর ওপেন করে একটা নিউ empty ফাইল[ctrl+shift+N] বানাও। ফাইল টা যেকোনো জায়গায় hello.cpp নাম দিয়ে সেভ করে ফেলো। তারপর নিচের কোডটা হুবুহু লিখে ফেলো!!
#include<iostream>
using namespace std;
int main()
{
cout<<"Hello World!!!"<<endl;
return 0;
}
তারপর বিল্ড মেন্যুতে গিয়ে “বিল্ড অ্যান্ড রান” করেও!! যদি ঠিকভাবে লিখতে পারো তবে তোমার সামনে প্রোগ্রামিং এর কালো দুনিয়ার বাক্স ওপেন হয়ে বলবে ‘হ্যালো ওয়ার্ল্ড’!!! কোড টুকু কিভাবে কাজ করে সেটা পরের পর্বে বুঝাব। সে পর্যন্ত প্রোগ্রামিং এর কালো দুনিয়ায় স্বাগতম!!!
Problem Reading Input(to Read Empty String too)
0You have problem in reading input.When you have to consider empty string you need to use gets().So use gets.and when you use gets() keep one thing in mind you have to read a dummy string if you take input before for taking newline.Like :
scanf("%d",&n);
gets(text); //dummy input
for(j=1;j<=n;j++)
{
o=0;
input[o]='\0';
//scanf("%s",text);
gets(text);
}
[link ]
Hello world!
0Hello Coders!!!
Here I may post my UnLucky Codes which will Never Works!!! So Keep calm and Gangnam Style!!!
and The last thing, Y U NO comment??
UnLucky Codes 