/*
user: php
time: 0.304 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1249
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 10002
vector<int>graph[MAXX];
int cost[MAXX][MAXX];
ll dist[MAXX];
bool visited[MAXX];
int farnode1;
ll bfs(int u)
{
mem(visited, false);
queue<int>Q;
ll maxdist = 0;
visited[u] = 1;
Q.push(u);
dist[u] = 0;
int v;
int len;
while( !Q.empty() )
{
u = Q.front();
if(dist[u] > maxdist)
{
maxdist = dist[u];
farnode1 = u;
}
len = SZ(graph[u]);
loop(i, len)
{
v = graph[u][i];
if(!visited[v])
{
visited[v] = 1;
dist[v] = dist[u] + cost[u][v];
Q.push(v);
}
}
Q.pop();
}
return maxdist;
}
int main()
{
//read();
int p, q, cst;
string str;
stringstream ss;
while( ! cin.eof() )
{
getline(cin, str);
if(str == "")
{
pf("0\n");
getline(cin, str);
continue;
}
loop(i, MAXX) graph[i].clear();
while( !cin.eof() && SZ(str) > 0 )
{
if(str == "") break;
ss.clear();
ss<<str;
ss>>p>>q>>cst;
graph[p].pb(q);
graph[q].pb(p);
cost[p][q] = cst;
cost[q][p] = cst;
getline(cin, str);
}
bfs(1);
pf("%lld\n", bfs(farnode1));
}
return 0;
}
Category Archives: I/O
(LightOj) 1337 – The Crystal Maze
0In this code, read() = freopen() isn’t working properly… I don’t know why?? đĻ
/*
user: php
time: 0.128 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1337
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<vector>
using namespace std;
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof(a))
#define SZ size()
#define pi acos(-1.0)
#define INF 1<<29
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define mod(a) (a>0?(a):(-a))
#define get(n) scanf("%d", &n)
#define MAXX 505
#define debug cout<<"ok"
int count_row, count_column;
char graph[MAXX][MAXX];
int* dp[MAXX][MAXX];
int value[MAXX][MAXX];
bool visited[MAXX][MAXX];
int p, q;
void dfs(int x, int y)
{
if(x<0 || x == count_row || y<0 || y == count_column || visited[x][y] || graph[x][y] == '#') return;
dp[x][y] = &value[p][q];
visited[x][y] = true;
if(graph[x][y] == 'C')
{
value[p][q]++;
}
dfs(x+1, y);
dfs(x-1, y);
dfs(x, y-1);
dfs(x, y+1);
return;
}
int main()
{
int kases, kaseno = 0;
int query;
get(kases);
while(kases--)
{
mem(visited, false);
get(count_row);
get(count_column);
get(query);
loop(i, count_row)
{
scanf("%s", graph[i]);
}
printf("Case %d:\n", ++kaseno);
loop(i, query)
{
get(p);
get(q);
p--;
q--;
if(graph[p][q] == '#')
{
printf("0\n");
continue;
}
if( ! visited[p][q] )
{
value[p][q] = 0;
dfs(p, q);
}
printf("%d\n", *(dp[p][q]));
}
}
return 0;
}
Scanf and Printf for Double Variable
0For printing and scanning double variables we must to use %lf, not %llf. I must must remember this in contest and problem solving time!! It can ruin my life!!!
(UVa) 10282 – Babelfish
0
/*
user: php
time: 0.444 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1223
*/
#include<iostream>
#include<map>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;
map<string, string> dic;
int main()
{
string english, foreign;
char inp[100];
char *ptr;
while(gets(inp))
{
if(strlen(inp) == 0) break;
ptr = strtok(inp, " ");
english = ptr;
ptr = strtok(NULL,"");
foreign = ptr;
dic[foreign] = english;
}
while(gets(inp))
{
foreign = inp;
if(dic[foreign].length() == 0)
{
printf("eh\n");
}
else
{
printf("%s\n", dic[foreign].c_str());
}
}
return 0;
}
(UVa) 591 – Box of Bricks
0I don’t know what the reason for printing two newline after each input set for getting accepted!!! The Problem statement said to print one!!! :O
/*
UserNAme: php
Time:0.008 sec
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=532
*/
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n, sum, h[51], result, caseno=0;
while(cin>>n)
{
if(n==0) break;
sum = 0;
result = 0;
for(int i=0; i<n; i++)
{
cin>>h[i];
sum += h[i];
}
sum /= n;
for(int i=0; i<n; i++)
{
if(h[i]>sum)
{
result += h[i] - sum;
}
}
printf("Set #%d\nThe minimum number of moves is %d.\n\n", ++caseno, result);
}
return 0;
}
(UVa) 10038 – Jolly Jumpers
0Remind One very Important thing. When you use “scanf” in loop/condition, you must check that it equals to exactly some integer value!!!
/*
UserName: php
Time: 0.012 sec
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=979
*/
#include<cstdio>
#include<cstdlib>
int main()
{
bool ch[3001];
int n, a, diff, past, flag, i;
while(scanf("%d", &n)==1)
{
for(i=1; i<n; i++) ch[i] = false;
flag = true;
past = 0;
for(i=0; i<n; i++)
{
scanf("%d", &a);
ch[abs(past - a)] = true;
past = a;
}
for(i=1; i<n; i++)
{
if(!ch[i])
{
flag = false;
break;
}
}
if(flag)
{
printf("Jolly\n");
}
else
{
printf("Not jolly\n");
}
}
return 0;
}
(UVa) 166 – Making Change
0For the first time I got PresentationE. đ It’s nothing but,
Presentation Error means that your program worked well for all the testcases but the position of your output might not be put in order…
For example,the problem encourages you not to put a blank line after the last testcase,but your program did it…
/*
UserName: php(HAsib Al Muhaimin)
Time: 0.008 sec
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=102
*/
//Note: I reduced the array size and everything by thinking N$ as (N/5)$.
#include<iostream>
using namespace std;
#define MAX 200
#include<cstdio>
#define INFINITE 1073741824
#define MIN(a, b) a<b?a:b
int dp[MAX];
int values[] = {1, 2, 4, 10, 20, 40};
int minimumChange(int v)
{
for(int i = 5; i>-1; i--)
{
if(v>= values[i])
{
return 1 + minimumChange(v - values[i]);
}
}
return 0;
}
int main()
{
int coins[6], minimum;
double target;
while(cin>>coins[0]>>coins[1]>>coins[2]>>coins[3]>>coins[4]>>coins[5]>>target)
{
if(coins[0]+coins[1]+coins[2]+coins[3]+coins[4]+coins[5] == 0) break;
dp[0] = 0;
minimum = INFINITE;
for(int i = 1; i<MAX; i++) dp[i] = INFINITE;
for(int c = 0; c<6; c++)
{
while(coins[c])
{
for(int i = MAX - values[c] - 1; i> -1; i--)
{
if(dp[i] < INFINITE )
{
dp[i + values[c]] = MIN(dp[i]+1, dp[i+values[c]]);
}
}
coins[c]--;
}
}
target = target * 20.0;
for(int i = target; i < MAX; i++)
{
minimum = MIN(minimum, dp[i] + minimumChange(i - target));
}
printf("%3d\n", minimum);
}
return 0;
}
(UVa) 11658 – Best Coalitions
0At the first time, I got WA when i did full code with double!!! I have no Idea Why đŽ
/*
UserName: php
Time: 0.020
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2705
*/
#include<cstdio>
#define MAX 10001
int dp[MAX];
int main()
{
int n, x, p, q;
int money, remaining, personal;
double result;
scanf("%d", &n);
scanf("%d", &x);
while(n+x>0)
{
dp[0] = 1;
for(int i = 1; i<MAX; i++) dp[i] = 0;
x--;
for(int i=0; i<n; i++)
{
scanf("%d.%d", &p, &q);
money = 100 * p + q;
if(i==x)
{
personal = money;
}
else
{
for(int j = MAX-1; j>-1; j--)
{
if(dp[j] > 0)
{
dp[j + money] = 1;
}
}
}
}
if(personal > 5000)
{
printf("100.00\n");
}
else
{
remaining = 5000 - personal;
for(int i = remaining + 1; i < MAX; i++)
{
if(dp[i] > 0)
{
result = (100.0 * personal)/(personal+i);
printf("%.2lf\n", result);
break;
}
}
}
scanf("%d", &n);
scanf("%d", &x);
}
return 0;
}
(UVa) 147 – Dollars
0Unsigned long long int = %llu
%3lld means WIDTH will be at least 3 unit.
/*
UserName: php
Time: 0.012 sec
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=83
*/
#include<cstdio>
#define MAX 30001
int coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
unsigned long long int dp[MAX];
int main()
{
dp[0] = 1;
for(int i = 0; i<11; i++)
{
for(int j = coins[i]; j<MAX; j++)
{
dp[j] += dp[j - coins[i]];
}
}
long long x, y;
while(scanf("%lld.%lld", &x, &y)==2)
{
if(x == 0 && y == 0) break;
printf("%3lld.%lld%lld%17llu\n", x, y/10, y%10, dp[x*100+y]);
}
return 0;
}
(UVa) 357 – Let Me Count The Ways
0
/*
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);
}
}
}
UnLucky Codes 