All of you studying cse must have known what is an Onlinejudge and most of us don't know how it works. Btw, I'm not going to talk about that here. It's a simple Linux Shell Scripting example / tutorial which will show you how to handle other programs in Bash and how to access all the files in a specific folder not knowing exactly how many are there.
The following snippet works very simply. It takes a target [.cpp] file as a command line argument and compiles it using g++, generates output files for all the input files provided with. And last, it compares those files with original output files and checks whether your program generated all the outputs correctly. So you can use it for your own purposes by making proper modification. It's also very easy to understand.
Note:
The folder from where you run this script must have these in it:
1. in // it will contain the input files with [.in] extension.
2. pout // it will hold the output files generated by your program.
3. jout // it will contain the correct judge output files for testing.
4. The program you are checking for with obviously [.cpp] extension and it's name is to be passed by command line argument.
Unless you change them in the code as you like. It is always a good practice to experiment with codes. :)
[.sh]
# Author: Zobayer Hasan
# CSE DU - 22/10/2009
# Check whether target file is provided or exists
# If available, compile and make it executable
clear
if [ $# != 1 ]; then
echo "parameter missing"
exit
elif [ ! -f "$1" ]; then
echo "file not found"
exit
else
if [ -f PROG ]; then
rm PROG
fi
g++ -o PROG "$1"
if [ ! -f PROG ]; then
echo "Compilation Error!"
echo "Your program could not be compiled."
echo ;
exit
fi
chmod -c 777 PROG > log.txt
fi
# Run the executable for each file in the "in" directory
# And generate their output files in "pout" directory
# Then match with the correct files in "jout" directory
echo ;
N=0
values=$( ls ./in/*.in )
for LINE in $values
do
./PROG < "$LINE" > "./pout/$N.out"
diff ./pout/$N.out ./jout/$N.out > log.txt
if [ $? -eq 1 ]; then
echo "Wrong Answer!"
echo "For file $LINE. Check log file."
echo ;
exit
fi
N=$(( N + 1 ))
done
echo "Accepted!"
echo "All tests passed successfully."
echo ;
# End of script :)
[.sh]
Have fun with bash !!!
Your are given two integers a and b. You have to find all the primes within range a and b. Here, 1 ≤ a ≤ b ≤ 231-1 and b - a ≤ 105.
Note: You have to handle 1, 2 and even numbers for appropriate case of your own.
[.cpp]
#include <string.h>
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032
unsigned base[MAX/64], segment[RNG/64], primes[LEN];
#define sq(x) ((x)*(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))
/* Generates all the necessary prime numbers and marks them in base[]*/
void sieve()
{
unsigned i, j, k;
for(i=3; i<LMT; i+=2)
if(!chkC(base, i))
for(j=i*i, k=i<<1; j<MAX; j+=k)
setC(base, j);
for(i=3, j=0; i<MAX; i+=2)
if(!chkC(base, i))
primes[j++] = i;
}
/* Returns the prime-count within range [a,b] and marks them in segment[] */
int segmented_sieve(int a, int b)
{
unsigned i, j, k, cnt = (a<=2 && 2<=b)? 1 : 0;
if(b<2) return 0;
if(a<3) a = 3;
if(a%2==0) a++;
mset(segment,0);
for(i=0; sq(primes[i])<=b; i++)
{
j = primes[i] * ( (a+primes[i]-1) / primes[i] );
if(j%2==0) j += primes[i];
for(k=primes[i]<<1; j<=b; j+=k)
if(j!=primes[i])
setC(segment, (j-a));
}
for(i=0; i<=b-a; i+=2)
if(!chkC(segment, i))
cnt++;
return cnt;
}
[.cpp]This is a sample program which demonstrates segmented sieve. Very fast and memory efficient version. 'base' is the array which holds the flags for all the primes upto √(231-1), i.e. the square-root of the max limit, and all the primes are stored in the 'primes' array. Later, these primes are used to determine whether a number is a composite or not within a certain range in the segmented sieve. To avoid overflow and sign bit problems, unsigned type is used.
[.cpp]
/*
user: zobayer
task: template
*/
#pragma disable(warning:4786)
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <utility>
using namespace std;
#define i64 long long
#define eps 1e-10
#define OFF ios::sync_with_stdio(false)
#define IOR freopen("in.txt","r",stdin)
#define IOW freopen("out.txt","w",stdout)
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define clr(x) x.clear()
#define sz size()
#define mset(x,v) memset(x,v,sizeof(x))
int main()
{
OFF; cout << "Hello World\n";
return 0;
}
[.cpp][pseudo-code]
function nCr(n, r):
if n == r:
return 1
if r == 1:
return n
if r == 0:
return 1
return nCr(n-1, r) + nCr(n-1, r-1)
[pseudo-code][pseudo-code]
table dp[N][R]
function nCr(n, r):
if n == r:
dp[n][r] = 1
if r == 1:
dp[n][r] = n
if r == 0:
dp[n][r] = 1
if dp[n][r] is not yet calculated:
dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1)
return dp[n][r]
[pseudo-code][.cpp]
#include <stdio.h>
#define i64 unsigned long long
i64 dp[66][33];
i64 nCr(int n, int r)
{
if(n==r) return dp[n][r] = 1;
if(r==0) return dp[n][r] = 1;
if(r==1) return dp[n][r] = (i64)n;
if(dp[n][r]) return dp[n][r];
return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}
int main()
{
int n, r;
while(scanf("%d %d",&n,&r)==2)
{
r = (r<n-r)? r : n-r;
printf("%llu\n",nCr(n,r));
}
return 0;
}
[.cpp]
This method computes expressions of the form ri = axi + byi for the remainder in each step i of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:
By substitution, this gives:
The first two values are the initial arguments to the algorithm:
The expression for the last non-zero remainder gives the desired results since this method computes every remainder in terms of a and b, as desired.
Example: Compute the GCD of 120 and 23. Or, more formally, compute: x, y, g for 120x + 23y = g; where x, y are two integers and g is the gcd of 120 and 23...
The computation proceeds as follows:The last line reads 1 = −9×120 + 47×23, which is the required solution: x = −9 and y = 47, and obviously g = gcd(120,23) = 1
This also means that −9 is the multiplicative inverse of 120 modulo 23, and that 47 is the multiplicative inverse of 23 modulo 120.
[.cpp]
#include <stdio.h>
/*
Takes a, b as input.
Returns gcd(a, b).
Updates x, y via pointer reference.
*/
int Extended_Euclid(int A, int B, int *X, int *Y)
{
int x, y, u, v, m, n, a, b, q, r;
/* B = A(0) + B(1) */
x = 0; y = 1;
/* A = A(1) + B(0) */
u = 1; v = 0;
for (a = A, b = B; 0 != a; b = a, a = r, x = u, y = v, u = m, v = n)
{
/* b = aq + r and 0 <= r < a */
q = b / a;
r = b % a;
/* r = Ax + By - aq = Ax + By - (Au + Bv)q = A(x - uq) + B(y - vq) */
m = x - (u * q);
n = y - (v * q);
}
/* Ax + By = gcd(A, B) */
*X = x; *Y = y;
return b;
}
int main()
{
int a, b, x, y, g;
scanf("%d %d", &a, &b);
g = Extended_Euclid(a, b, &x, &y);
printf("X = %d; Y = %d; G = %d\n", x, y, g);
return 0;
}
[.cpp]
