February 11, 2009 by Blog Admin
Posted in Common | Tagged Sticky post | 2 Comments »
February 7, 2010 by Blog Admin
২টি সংখ্যা দেয়া থাকবে । বলতে হবে,
১. প্রথম সংখ্যাটি বড় কিনা
২. প্রথম সংখ্যাটি ছোট কিনা
৩. ২ টি সংখ্যা সমান কিনা
লক্ষ্য রাখার মত বিষয়গুলো হচ্ছে,
১. সংখ্যা ২ টির absolute value 1000000001 থেকে ছোট ।
তার মানে, সংখ্যা ২ টির প্রকৃত মান হবে, -1000000001 থেকে +1000000001 এর মধ্যে ।
এই কাজটি করার জন্য তাহলে Integer Data type যথেষ্ট ।
কারন, 32 bit এ Integer ‘র মান -2147483648 থেকে +2147483647 পর্যন্ত ।
২. ১৪ টি সেট থাকতে পারে । প্রতিটি সেটে ২ টি করে সংখ্যা থাকবে ।
যদি প্রথম সংখ্যাটি ছোট হয় তাহলে আউটপুট হবে <
যদি প্রথম সংখ্যাটি বড় হয় তাহলে আউটপুট হবে >
আর সংখ্যা দু‘টি সমান হলে আউটপুট হবে =
basic structure of this program is given below :
// @BEGIN_OF_SOURCE_CODE
#include <stdio.h>
int main ()
{
int t; // sets of input
scanf ("%d", &t);
while ( t != 0 ) {
int a; // first number
int b; // second number
scanf ("%d %d", &a, &b);
if ( ... )
printf ("<");
else if ( ... )
printf (">");
else
printf ("=");
printf ("\n");
t--;
}
return 0;
}
// @END_OF_SOURCE_CODE
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 5, 2010 by Blog Admin
import java.math.BigInteger;
import java.util.Scanner;
/**
*
* @author Md. Shahab Uddin
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner input = new Scanner (System.in);
int testCase = input.nextInt();
int cases = 0;
while ( testCase-- != 0 ) {
BigInteger first = input.nextBigInteger();
BigInteger second = input.nextBigInteger();
BigInteger firstSum;
BigInteger secondSum;
System.out.printf ("Scenario #%d:\n", ++cases);
if ( first.compareTo(BigInteger.ZERO) < 0 && second.compareTo(BigInteger.ZERO) < 0 ) {
first = first.multiply(BigInteger.valueOf(-1));
second = second.add(BigInteger.ONE);
second = second.multiply(BigInteger.valueOf(-1));
firstSum = (first.multiply(first.add(BigInteger.ONE))).divide(BigInteger.valueOf(2));
secondSum = (second.multiply(second.add(BigInteger.ONE))).divide(BigInteger.valueOf(2));
//System.out.println (firstSum);
//System.out.println (secondSum);
//System.out.println ("-");
System.out.println (secondSum.subtract(firstSum));
}
else if ( first.compareTo(BigInteger.ZERO) >= 0 && second.compareTo(BigInteger.ZERO) >= 0 ) {
if ( first.compareTo(BigInteger.ZERO) > 0 )
first = first.subtract(BigInteger.ONE);
firstSum = (first.multiply(first.add(BigInteger.ONE))).divide(BigInteger.valueOf(2));
secondSum = (second.multiply(second.add(BigInteger.ONE))).divide(BigInteger.valueOf(2));
System.out.println (secondSum.subtract(firstSum));
//System.out.println ("both plus");
}
else {
first = first.multiply(BigInteger.valueOf(-1));
firstSum = (first.multiply(first.add(BigInteger.ONE))).divide(BigInteger.valueOf(2));
//firstSum = firstSum.multiply(BigInteger.valueOf(-1));
secondSum = (second.multiply(second.add(BigInteger.ONE))).divide(BigInteger.valueOf(2));
System.out.println (secondSum.subtract(firstSum));
}
System.out.println ();
}
}
}
Posted in ACM (TJU) | Leave a Comment »
February 5, 2010 by Blog Admin
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <map>
#include <cmath>
#include <math.h>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define N 1000000
using namespace std;
bool mark [N];
vector <int> list;
struct node {
int mu;
int M;
} a [N];
void sieve ()
{
memset (mark, true, N);
mark [0] = mark [1] = false;
for ( int i = 4; i < N; i += 2 )
mark [i] = false;
for ( int i = 3; i * i <= N; i += 2 ) {
if ( mark [i] ) {
for ( int j = i * i; j < N; j += 2 * i )
mark [j] = false;
}
}
list.clear ();
list.push_back (2);
for ( int i = 3; i < N; i += 2 ) {
if ( mark [i] )
list.push_back (i);
}
//printf ("%d\n", list.size ());
}
int main ()
{
sieve ();
a [0].mu = a [0].M = 1;
for ( int i = 2; i <= N; i++ ) {
int length = (int) sqrt (i);
int save = i;
int index = 0;
int count = 0;
int square = 0;
while ( list [index] <= length ) {
while ( save % list [index] == 0 ) {
count++;
save /= list [index];
square++;
}
if ( square > 1 ) {
a [i - 1].mu = 0;
break;
}
square = 0;
index++;
}
if ( save > 1 )
count++;
if ( square < 2 ) {
if ( count % 2 )
a [i - 1].mu = -1;
else
a [i - 1].mu = 1;
}
}
for ( int i = 1; i < N; i++ )
a [i].M += (a [i - 1].M + a [i].mu);
int n;
while ( scanf ("%d", &n) && n ) {
printf ("%8d%8d%8d\n", n, a [n - 1].mu, a [n - 1].M);
}
return 0;
}
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 5, 2010 by Blog Admin
#include <stdio.h>
#include <math.h>
int main ()
{
int s;
double d;
while ( scanf ("%d %lf", &s, &d) != EOF ) {
int below = (s * (s - 1)) / 2;
d += below;
d *= 2;
double n = ceil ((sqrt (1 + 4 * d) - 1) / 2.0);
printf ("%0.lf\n", n);
}
return 0;
}
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 5, 2010 by Blog Admin
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <map>
#include <cmath>
#include <math.h>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define N 10000002
using namespace std;
bool mark [N];
void sieve ()
{
memset (mark, true, N);
mark [0] = mark [1] = false;
for ( int i = 4; i < N; i += 2 )
mark [i] = false;
for ( int i = 3; i * i <= N; i += 2 ) {
if ( mark [i] ) {
for ( int j = i * i; j < N; j += 2 * i )
mark [j] = false;
}
}
}
void find_prime (int x)
{
if ( mark [x - 2] ) {
printf ("2 %d", x - 2);
return;
}
for ( int i = 3; i < N; i += 2 ) {
if ( mark [x - i] && mark [i] ) {
printf ("%d %d", i, x - i);
return;
}
}
}
int main ()
{
sieve ();
int n;
while ( scanf ("%d", &n) != EOF ) {
if ( n < 8 ) {
printf ("Impossible.\n");
continue;
}
if ( n % 2 ) {
printf ("2 3 ");
find_prime (n - 5);
}
else {
printf ("2 2 ");
find_prime (n - 4);
}
printf ("\n");
}
return 0;
}
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 5, 2010 by Blog Admin
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <set>
#include <math.h>
#define For(a) for ( i = 0; i < a; i++ )
#define Rep(a, b) for ( i = a; i <= b; i++ )
#define N 1000000
using namespace std;
int row;
int column;
int enter;
char grid [1000] [1000];
bool visited [1000] [1000];
int steps;
int steps_b4_stuck;
int stuck;
void function ()
{
steps = stuck = steps_b4_stuck = 0;
for ( int i = 0; i < 1000; i++ ) {
for ( int j = 0; j < 1000; j++ )
visited [i] [j] = false;
}
int enter_x = 0;
int enter_y = enter - 1;
while ( enter_x >= 0 && enter_x < row && enter_y >= 0 && enter_y < column ) {
if ( visited [enter_x] [enter_y] == true )
break;
visited [enter_x] [enter_y] = true;
if ( grid [enter_x] [enter_y] == 'N' )
enter_x--;
else if ( grid [enter_x] [enter_y] == 'S' )
enter_x++;
else if ( grid [enter_x] [enter_y] == 'E' )
enter_y++;
else if ( grid [enter_x] [enter_y] == 'W' )
enter_y--;
steps++;
}
if ( visited [enter_x] [enter_y] == false )
return;
steps = 0;
int x = 0;
int y = enter - 1;
while ( x != enter_x || y != enter_y ) {
if ( grid [x] [y] == 'N' )
x--;
else if ( grid [x] [y] == 'S' )
x++;
else if ( grid [x] [y] == 'E' )
y++;
else if ( grid [x] [y] == 'W' )
y--;
steps_b4_stuck++;
}
x = enter_x;
y = enter_y;
do {
if ( grid [x] [y] == 'N' )
x--;
else if ( grid [x] [y] == 'S' )
x++;
else if ( grid [x] [y] == 'E' )
y++;
else if ( grid [x] [y] == 'W' )
y--;
stuck++;
} while ( x != enter_x || y != enter_y );
}
int main ()
{
while ( scanf ("%d %d %d", &row, &column, &enter) ) {
if ( row == 0 && column == 0 && enter == 0 )
break;
for ( int i = 0; i < row; i++ )
scanf ("%s", grid [i]);
function ();
if (steps)
printf ("%d step(s) to exit\n", steps);
else
printf ("%d step(s) before a loop of %d step(s)\n", steps_b4_stuck, stuck);
}
return 0;
}
// @END_OF_SOURCE_CODE
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 5, 2010 by Blog Admin
#include <algorithm>
using namespace std;
bool kuti;
bool space;
void convert (char *temp)
{
if ( strcmp (temp, "0000000") == 0 )
return;
char x [3];
x [0] = temp [0];
x [1] = temp [1];
x [3] = 0;
int number = atoi (x);
if ( number ) {
if ( space ) printf (" ");
space = true;
printf ("%d lakh", number);
}
// hazar
x [0] = temp [2];
x [1] = temp [3];
x [3] = 0;
number = atoi (x);
if ( number ) {
if ( space ) printf (" ");
space = true;
printf ("%d hajar", number);
}
x [0] = temp [4];
x [1] = 0;
number = atoi (x);
if ( number ) {
if ( space ) printf (" ");
space = true;
printf ("%d shata", number);
}
x [0] = temp [5];
x [1] = temp [6];
x [3] = 0;
number = atoi (x);
if ( number ) {
if ( space ) printf (" ");
space = true;
printf ("%d", number);
}
kuti = true;
}
int main ()
{
char input [20];
int cases = 0;
while ( gets (input) ) {
printf ("%4d. ", ++cases);
kuti = false;
space = false;
if ( strcmp (input, "0") == 0 ) {
printf ("0\n");
continue;
}
int length = strlen (input);
reverse (input, input + length);
for ( int i = length; i < 15; i++ )
input [i] = '0';
input [15] = 0;
reverse (input, input + 15);
if ( input [0] - '0' ) {
printf ("%d kuti", input [0] - '0');
kuti = space = true;
}
char temp [10];
for ( int i = 1; i <= 7; i++ )
temp [i - 1] = input [i];
temp [7] = 0;
convert (temp);
if ( kuti )
printf (" kuti");
for ( int i = 8; i < 15; i++ )
temp [i - 8] = input [i];
temp [15] = 0;
convert (temp);
printf ("\n");
}
return 0;
}
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 5, 2010 by Blog Admin
#include <stdio.h>
#include <math.h>
void sa ()
{
double u;
double v;
double t;
scanf ("%lf %lf %lf", &u, &v, &t);
double a = (v - u) / t;
double s = (v * v - u * u) / (2 * a);
printf ("%.3lf %.3lf\n", s, a);
}
void st ()
{
double u;
double v;
double a;
scanf ("%lf %lf %lf", &u, &v, &a);
double t = (v - u) / a;
double s = (v * v - u * u) / (2 * a);
printf ("%.3lf %.3lf\n", s, t);
}
void vt ()
{
double u;
double a;
double s;
scanf ("%lf %lf %lf", &u, &a, &s);
double v = sqrt (pow (u, 2) + 2 * a * s);
double t = (v - u) / a;
printf ("%.3lf %.3lf\n", v, t);
}
void ut ()
{
double v;
double a;
double s;
scanf ("%lf %lf %lf", &v, &a, &s);
double u = sqrt (pow (v, 2) - 2 * a * s);
double t = (v - u) / a;
printf ("%.3lf %.3lf\n", u, t);
}
int main ()
{
int dataset;
int cases = 0;
while ( scanf ("%d", &dataset) && dataset ) {
printf ("Case %d: ", ++cases);
switch (dataset) {
case 1 :
sa ();
break;
case 2 :
st ();
break;
case 3 :
vt ();
break;
case 4 :
ut ();
break;
}
}
return 0;
}
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 5, 2010 by Blog Admin
#include <stdio.h>
#include <string.h>
bool is_vowel (char x)
{
if ( x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' )
return true;
return false;
}
bool check (char x [], char y [])
{
int len_x = strlen (x);
int len_y = strlen (y);
if ( len_x != len_y )
return false;
for ( int i = 0; i < len_x; i++ ) {
if (!is_vowel (x [i]) && x [i] != y [i])
return false;
}
return true;
}
int main ()
{
int testCase;
scanf ("%d", &testCase);
while ( testCase-- ) {
char first [25];
char second [25];
scanf ("%s %s", first, second);
if ( check (first, second) )
printf ("Yes\n");
else
printf ("No\n");
}
return 0;
}
Posted in ACM (UVa) Algorithm | Leave a Comment »
February 4, 2010 by Blog Admin
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <algorithm>
using namespace std;
char a [1005] [25];
bool anagram (int x, int y)
{
int len_x = strlen (a [x]);
int len_y = strlen (a [y]);
if ( len_x == 0 || len_y == 0 )
return false;
if ( len_x != len_y )
return false;
int frq [26];
for ( int i = 0; i < 26; i++ )
frq [i] = 0;
for ( int i = 0; i < len_x; i++ )
frq [tolower (a [x] [i]) - 'a']++;
for ( int i = 0; i < len_y; i++ )
frq [tolower (a [y] [i]) - 'a']--;
for ( int i = 0; i < 26; i++ ) {
if ( frq [i] )
return false;
}
return true;
}
int main ()
{
int index = 0;
while (scanf ("%s", a [index])) {
if ( strcmp (a [index], "#") == 0 )
break;
index++;
}
bool flag;
for ( int i = 0; i < index; i++ ) {
flag = false;
for ( int j = i + 1; j < index; j++ ) {
if ( anagram (i, j) ) {
a [j] [0] = 0;
flag = true;
}
}
if ( flag )
a [i] [0] = 0;
}
// sort
for ( int i = 0; i < index; i++ ) {
for ( int j = i + 1; j < index; j++ ) {
if ( strcmp (a [i], a [j]) > 0 ) {
char temp [25];
strcpy (temp, a [i]);
strcpy (a [i], a [j]);
strcpy (a [j], temp);
}
}
}
for ( int i = 0; i < index; i++ ) {
if ( a [i] [0] != 0 )
printf ("%s\n", a [i]);
}
return 0;
}
Posted in ACM (UVa) Algorithm | Leave a Comment »