Just another programmer

Coding with Emacs and e2wm, a brilliant emacs windows manager

2012-07-21T23:33:00.001+09:00

I've been using emacs for a while now and never intend to move on to vi, and especially other gui IDEs, because I simply just cant move my pinky finger from ctrl, it just automatically gets stuck there lol. and the IDEs editors are just too fancy for me.

Anyway the most annoying problem when developing with emacs is the project management, right? Since I believe you don't wanna ctrl+x ctrl+c to grep for some stuffs, and just split the emacs window to then do some shell stuffs there. It's pretty troublesome when you quit your emacs and then you have to split the windows to your preference again. Times like these, you have to define the splitting functions to .emacs and it's gonna suck more of your precious time again.

Well brace yourself, this tool is the perfect tool for project management for emacs, e2wm! Basically there are 5 kinds of perspectives you can choose for splitting the windows, Code, Two, Doc, Dashboard, and Array perspective, which is respectively equipped with various emacs tools.

To use e2wm is simple, what you have to do is just download e2wm-config.el, e2wm-vcs.el, and e2wm.el and then put it in your emacs path, and then add:

(require 'e2wm)
(global-set-key (kbd "M-+") 'e2wm:start-management)

to your .emacs file!

this is the link to kiwanami's github (the author of e2wm, thanks!): https://github.com/kiwanami
and this is the link to e2wm's github repo: https://github.com/kiwanami/emacs-window-manager

Intel OpenCL Implicit Vectorizer

2012-07-21T23:04:00.003+09:00

OpenCL compiler differs depending on its vendor, and Intel optimizes its compiler to auto-vectorize some loops that may take the advantage of the SSE and AVX instructions.

For example, the Black-Scholes equation when executed with single thread C99 and single thread OpenCL thread gives the execution time as below:

Input: 10MB of data
calculates both call and put option
both uses -O3 compiler option of gcc-4.4

c99 : 1612.203 ms
OpenCL : 673.248 ms

This 'hidden' optimization is kinda cool, isn't it?

Let's parallelize everything

2012-07-18T23:21:00.002+09:00

Who does not want to see his programs run faster? Using exactly the same machine, same cpu, same gpu, same programming language? Many parallel programming frameworks/APIs have been developed and released recently, and with the help of many amazing programmers worldwide, these APIs have also been wrapped beautifully into many front-end languages such as Python, Ruby, or even Javascript. Some also are under development to be ported to more delicate programming languages such as Haskell, Scala, or Clojure. Soo for those of you who haven't seen/experienced the elegance of parallel computing, what are you waiting for? Let's parallelize everything!

Let me share here some of the parallel programming frameworks I know, and I believe they are famous enough to not get disappointed when using it.

First of all, there is CUDA, developed by NVIDIA, a leading company in the Graphics Processing Unit devices. I have been developing some programs using CUDA for 2 years now, and the API itself is pretty simple and straightforward to use, and I am amazed with the number of sample programs they provided inside the CUDA Toolkit, makes us incredibly easy to learn some stuffs, not only how to use CUDA API but also some important algorithms and tuning-up for developing a parallel executed program. Having said so, actually it was pretty hard to develop using CUDA back then (when it was still version 1.x), but NVIDIA just released a new version of CUDA (CUA 4.2 going to CUDA 5) and everything just became easier, to understand, to install, and to develop with that. Most important thing, note that since NVIDIA is the developer and it is not an open source software, CUDA is only available for NVIDIA's GPUs (from GeForce 8800 to the newest one). The technique of having your computation that is supposed to run sequentially on CPU is basically called a GPGPU (General Purposed GPU) computing.

And then there is OpenCL, derived from Open Computing Language, initially developed Apple and Khronos Group. OpenCL is a framework for parallelization and is aimed to be able to execute in many platforms. At first OpenCL was only released with the standard C99 API but then they added the C++ wrappers to the runtime API, hence makes us easier to do some OOP stuffs. OpenCL can run on some major vendors' devices: AMD, Intel, and NVIDIA, where each vendor has its own compiler (or library) to interpret and/or optimize the standardized OpenCL runtime API. afaik it is Khronos who's been leading the OpenCL development and standardizing the API. Since every vendor has different technology equipped to its device, each of them releases its own OpenCL programming SDK and this can be seen inside the website respectively: AMD OpenCL SDK, Intel OpenCL SDK, and NVIDIA OpenCL SDK which comes with the CUDA Toolkit. Each SDK is provided with a unique library and some sample programs, and each vendor's compiler has its own way to optimize in compile time. IMO, learning OpenCL will not be that hard if you have previously done some CUDA programming.

Those two above are the APIs I've been using for a while to do some parallel stuffs, and there are plenty more out there and you can get some of them for free (or maybe even already installed in your computer) but some aren't.
Examples for free APIs: OpenMP, Intel's TBB, Intel's ArBB, Pthreads
Not free: PGI's Compiler with OpenACC, CAPS' Compiler with OpenACC

Facebook is blocked in your office? Maybe this will help you a bit ;)

2012-04-15T15:35:00.002+09:00

I think there aren't few of you who want to access your facebook page, but the page is being blocked by the server and you can't visit it.

Maybe this will give you a hint to backdoor the security!

First of all, you should know that every website has its own ip address, which will give you a unique identifier so your system will make sure that it visits the right page, even though there are two websites with the same name.

For example, Twitter's IP address is 199.59.150.39
If you hit http://199.59.150.39 to your address bar, then boom, twitter page will show up.

But that is not only it, this IP address will then be translated again to a 'human' number which is the true unique identifier.

How? First we translate the IP address to a sequence of binary numbers.
Twitter's IP address above will be translated to:

11000111 . 00111011 . 10010110 . 00100111
(Learn how to convert a number to binary)

And then, the dots exist in between will vanish and all sequences will be joined.

11000111001110111001011000100111

Guess what, this will also be the unique identifier if you convert it back again to the decimal number,
which will give us:

3342571047

Try to check it out!
hit http://3342571047 to your address bar.

Anyway, all of these conversions can be done in python within 2 lines.

#!/usr/bin/env python
# ip_trans.py

import sys
print 'http://%i' % int(''.join([bin(int(x)+256)[3:] for x in sys.argv[1].split('.')]),2)

And run the program with an ip address as the argument:

$ python ip_trans.py 199.59.150.39
http://3342571047

ipython-0.12 installation in Cygwin

2012-04-15T14:46:00.002+09:00

ipython with numpy+scipy+matplotlib Installation Procedures: (as of April 2012)

1. Install some packages from cygwin setup.exe:
   * liblapack
   * fortran compilers and some fortran packages (best to download all related to fortran)
   * libgfortran
   * python packages
   * libpng
   * freetype2
   * c/c++ compilers
   * libboost

2. Install libffi (required for ipython)
   * Download libffi-3.0.11
   * Extract folder
   * Configure the installation
     ./configure
   * Install
     make install

3. Install ATLAS (Automatic Tuned Linear Algebra Software) (required for numpy+scipy)
   * caution: this installation may cause stress due to the installation time, which may take all day.
   * Download atlas-3.8.4
   * Extract folder
   * Make build folder (Installation procedure is written inside INSTALL.txt)
     mkdir cygwin_build
   * Configure (there is only 32-bit version)
     ../configure -b 32
   * Install
     make
     make check
     make ptcheck
     make time
     make install

4. Install nose (testing package for scipy+numpy)
   * Download nose-1.1.2
   * Extract folder
   * Build file
     python setup.py build
   * Install
     python setup.py install

5. Install numpy (required for matplotlib and for.... python programmer.)
   * Download numpy-1.6.1
   * Extract folder
   * Build file (I faced some bugs when doing this, if you also happen to face them, I'll try my best to help)
     python setup.py build
   * Install
     python setup.py install

6. Install scipy (required for.... python programmer.)
   * Download scipy-0.10.1
   * Extract folder
   * Build file
     python setup.py build (also some bugs here)
   * Install
     python setup.py install

7. Install matplotlib (required for ipython)
   * Download matplotlib-1.1.0
   * Extract folder
   * Copy the setup.cfg.template to setup.cfg
     cp setup.cfg.template setup.cfg
   * Uncomment line 70
     tkagg = False
   * Try to build the program
     python setup.py build
   * If there is an error saying unable to remap a dll file or such, we have to run the rebase command of cygwin, using CO\MMAND PROMPT:
     cd C\cygwin\bin
     ash
     PATH=. rebaseall -v

     ...wait until it finishes

   * Try to build the program once again
     python setup.py build
   * Look at the pkg_config, if it says it's not configured right for libffi package, put this in your .bashrc:
     export PKG_CONFIG_PATH=/usr/local/lib/pkconfig (after making sure that libffi.pc is here)
   * And also make sre that you satisfied all dependencies.
   * After the build succeed, install
     python setup.py install

8. FINALLY. Install ipython.
   * Download ipython-0.12
   * Extract folder
   * Build file
     python setup.py build (also some bugs here)
   * Install
     python setup.py install

9. Now that we finished all installations, let's run some tests.
   * open ipython
     ipython --pylab
   * show a sin(x) figure
      x = arange(-5,5,0.1)
      y = sin(x)
plot(x,y)
savefig("sin_x.png")
   * And that code should have shown you a figure of a beautiful sin(x) wave:

cygwin + ipython. a perfection.

2012-04-15T14:27:00.000+09:00

I'm one of those programmer who just loves anything about Unix, but just feels weird about using Linux GUI hence stuck with Windows 7.

The most perfect tool for us is ofcourse, Cygwin.

However, there are some (many, actually) weaknesses in Cygwin such as sometime you have to manually figure out how to install some softwares manually, instead of just invoking sudo apt-get in a Linux system.

I recently just faced this problem when trying to install ipython with numpy+scipy+matplotlib in my system in Cygwin, and had to waste all-saturday to finally have it installed correctly.

Nevertheless, It was really worth the time.

Cygwin + Ipython. is. just. amazing.
You can literally do anything you want since there are ridiculously many amazing python libraries that you can invoke anytime you want anything you need.

I seriously recommend to every python programmer who uses Cygwin out there.

Turning Python-nese

2012-04-15T14:18:00.000+09:00

Just recently I'm in love with python language, not just because it fastens your software development milestone, it only also has brilliant developers who make this language more convenient to use. PyOpenCL and PyCUDA are only some simple examples. ipython is another amazing tool.

Check out the project here

Fresh graduate

2012-04-15T14:12:00.000+09:00

Having been busy throughout the entire senior year of my undergrad, finally I got my bachelor degree of Computer Science. The new journey as a professional programmer has started! Looking forward into any kinds of job waiting ahead.

SPOJ, FCTRL2, Small Factorials

2011-02-10T23:36:00.000+09:00

SPOJ Problem Set (classical)

24. Small factorials

Problem code: FCTRL2

You are asked to calculate factorials of some small positive integers.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output

For each integer n given at input, display a line with the value of n!

Example

Sample input:
4
1
2
5
3
Sample output:

1
2
120
6

struct Bigint {
  string a;
  int sign;
  Bigint() {}
  Bigint( string b ) { (*this) = b; }
  int size() { return a.size(); }
   Bigint inverseSign() { sign *= -1; return (*this); }
   Bigint normalize( int newSign ) {
   sign = newSign;
   for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- ) a.erase(a.begin() + i);
   if( a.size() == 1 && a[0] == '0' ) sign = 1;
   return (*this);
   }
   void operator = ( string b ) {
   a = b[0] == '-' ? b.substr(1) : b;
   reverse( a.begin(), a.end() );
   this->normalize( b[0] == '-' ? -1 : 1 );
   }

   bool operator < ( const Bigint &b ) const {
   if( a.size() != b.a.size() ) return a.size() < b.a.size();
   for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] ) return a[i] < b.a[i];
   return false;
   }

   Bigint operator + ( Bigint b ) {
   if( sign != b.sign ) return (*this) - b.inverseSign();
   Bigint c;
   for( int i = 0, carry = 0; i < (int)a.size() || i < (int)b.size() || carry; i++ ) {
   carry += (i < (int)a.size() ? a[i] - 48 : 0) + (i < (int)b.a.size() ? b.a[i] - 48 : 0);
   c.a += (carry % 10 + 48);
   carry /= 10;
   }
   return c.normalize(sign);
   }
   Bigint operator - ( Bigint b ) {
   if( sign != b.sign ) return (*this) + b.inverseSign();
   if( (*this) < b ) return (b - (*this)).inverseSign();
   Bigint c;
   for( int i = 0, borrow = 0; i < (int)a.size(); i++ ) {
   borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
   c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
   borrow = borrow >= 0 ? 0 : 1;
   }
   return c.normalize(sign);
   }
   Bigint operator * ( Bigint b ) {
   Bigint c("0");
   for( int i = 0, k = a[i]; i < (int)a.size(); i++, k = a[i] ) {
   while(k-- - 48) c = c + b;
   b.a.insert(b.a.begin(), '0');
   }
   return c.normalize(sign * b.sign);
   }
   Bigint operator / ( Bigint b ) {
   if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
   Bigint c("0"), d;
   for( int j = 0; j < (int)a.size(); j++ ) d.a += "0";
   int dSign = sign * b.sign; b.sign = 1;
   for( int i = a.size() - 1; i >= 0; i-- ) {
   c.a.insert( c.a.begin(), '0');
   c = c + a.substr( i, 1 );
   while( !( c < b ) ) c = c - b, d.a[i]++;
   }
   return d.normalize(dSign);
   }
   Bigint operator % ( Bigint b ) {
   if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
   Bigint c("0");
   int cSign = sign * b.sign; b.sign = 1;
   for( int i = a.size() - 1; i >= 0; i-- ) {
   c.a.insert( c.a.begin(), '0');
   c = c + a.substr( i, 1 );
   while( !( c < b ) ) c = c - b;
   }
   return c.normalize(cSign);
   }
   void print() {
   if( sign == -1 ) putchar('-');
   for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
   }
};

Bigint fact(Bigint n){
  string s = n.a;
  if(s=="1")return Bigint("1");
  return n*fact(n-Bigint("1"));
}

int main(){
  int nTests;
  scanf("%d ",&nTests);
  repe(test,1,nTests) {
   //if (1) fprintf(stderr,"Case %d/%d",test,nTests);
   Bigint n;
   string s;
   cin >>s;
   n = s;
   n = fact(n);
   n.print();
   cout<<endl;
  }

  return 0;
}

SPOJ, NSTEPS, Number Steps

2011-02-10T23:33:00.000+09:00

SPOJ Problem Set (classical)

1112. Number Steps

Problem code: NSTEPS

Starting from point (0,0) on a plane, we have written all non-negative integers 0, 1, 2,... as shown in the figure. For example, 1, 2, and 3 has been written at points (1,1), (2,0), and (3, 1) respectively and this pattern has continued.

You are to write a program that reads the coordinates of a point (x, y), and writes the number (if any) that has been written at that point. (x, y) coordinates in the input are in the range 0...10000.

Input

The first line of the input is N, the number of test cases for this problem. In each of the N following lines, there is x, and y representing the coordinates (x, y) of a point.

Output

For each point in the input, write the number written at that point or write No Number if there is none.

Example

Input:
3
4 2
6 6
3 4

Output:
6
12
No Number

int main(){
  int nTests;
  scanf("%d ",&nTests);
  repe(test,1,nTests) {
   int a,b;
   cin>>a>>b;
   if(a!=b&&a-b!=2){cout<<"No Number\n";continue;}
   if(a%2==0&&b%2==0)cout<<a+b<<endl;
   else cout<<a+b-1<<endl;
  }

  return 0;
}

SPOJ TOANDFRO, To and Fro

2011-02-10T23:32:00.000+09:00

SPOJ Problem Set (classical)

400. To and Fro

Problem code: TOANDFRO

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down

t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx
Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.

Input

There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2...20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.

Output

Each input set should generate one line of output, giving the original plaintext message, with no spaces.

Example

Input:

5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0

Output:

theresnoplacelikehomeonasnowynightx
thisistheeasyoneab

int main(){

  int cl;
  cin>>cl;
  while(cl){
   string s,t,temp;
   cin>>s;
   int k=0;
   rep(i,0,sz(s)/cl){
   rep(j,0,cl){
temp+=s[k++];
   }
   if(i%2)reverse(all(temp));
   t+=temp;
   temp.clear();
   }
   rep(i,0,cl){
   rep(j,0,sz(t)/cl){
cout<<t[i+j*cl];
   }
   }
   cout<<endl;
   cin>>cl;
  }
  return 0;
}

SPOJ JULKA, Julka

2011-02-10T23:31:00.000+09:00

SPOJ Problem Set (classical)

54. Julka

Problem code: JULKA

Julka surprised her teacher at preschool by solving the following riddle:

Klaudia and Natalia have 10 apples together, but Klaudia has two apples more than Natalia. How many apples does each of he girls have?

Julka said without thinking: Klaudia has 6 apples and Natalia 4 apples. The teacher tried to check if Julka's answer wasn't accidental and repeated the riddle every time increasing the numbers. Every time Julka answered correctly. The surprised teacher wanted to continue questioning Julka, but with big numbers she could't solve the riddle fast enough herself. Help the teacher and write a program which will give her the right answers.

Task

Write a program which

reads from standard input the number of apples the girls have together and how many more apples Klaudia has,
counts the number of apples belonging to Klaudia and the number of apples belonging to Natalia,
writes the outcome to standard output
Input

Ten test cases (given one under another, you have to process all!). Every test case consists of two lines. The first line says how many apples both girls have together. The second line says how many more apples Klaudia has. Both numbers are positive integers. It is known that both girls have no more than 10100 (1 and 100 zeros) apples together. As you can see apples can be very small.

Output

For every test case your program should output two lines. The first line should contain the number of apples belonging to Klaudia. The second line should contain the number of apples belonging to Natalia.

Example

Input:
10
2
[and 9 test cases more]

Output:
6
4
[and 9 test cases more]

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <cstring>
using namespace std;
typedef long long int lli;
typedef long unsigned long llu;

//definitions
#define mem_prep(varx) memset(varx,0,sizeof(varx))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define repe(i,a,n) for(int i=(a);i<=(n);i++)
#define forsz(i,a,v) rep(i,a,sz(v))
#define repsz(i,v) rep(i,0,sz(v))
#define vi vector<int>
#define vs vector<string>

void prepare( )
{
#ifdef WIN32
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}

struct Bigint {
  string a;
  int sign;
  Bigint() {}
  Bigint( string b ) { (*this) = b; }
  int size() { return a.size(); }
   Bigint inverseSign() { sign *= -1; return (*this); }
   Bigint normalize( int newSign ) {
   sign = newSign;
   for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- ) a.erase(a.begin() + i);
   if( a.size() == 1 && a[0] == '0' ) sign = 1;
   return (*this);
   }
   void operator = ( string b ) {
   a = b[0] == '-' ? b.substr(1) : b;
   reverse( a.begin(), a.end() );
   this->normalize( b[0] == '-' ? -1 : 1 );
   }

   bool operator < ( const Bigint &b ) const {
   if( a.size() != b.a.size() ) return a.size() < b.a.size();
   for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] ) return a[i] < b.a[i];
   return false;
   }

   Bigint operator + ( Bigint b ) {
   if( sign != b.sign ) return (*this) - b.inverseSign();
   Bigint c;
   for( int i = 0, carry = 0; i < (int)a.size() || i < (int)b.size() || carry; i++ ) {
   carry += (i < (int)a.size() ? a[i] - 48 : 0) + (i < (int)b.a.size() ? b.a[i] - 48 : 0);
   c.a += (carry % 10 + 48);
   carry /= 10;
   }
   return c.normalize(sign);
   }
   Bigint operator - ( Bigint b ) {
   if( sign != b.sign ) return (*this) + b.inverseSign();
   if( (*this) < b ) return (b - (*this)).inverseSign();
   Bigint c;
   for( int i = 0, borrow = 0; i < (int)a.size(); i++ ) {
   borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
   c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
   borrow = borrow >= 0 ? 0 : 1;
   }
   return c.normalize(sign);
   }
   Bigint operator * ( Bigint b ) {
   Bigint c("0");
   for( int i = 0, k = a[i]; i < (int)a.size(); i++, k = a[i] ) {
   while(k-- - 48) c = c + b;
   b.a.insert(b.a.begin(), '0');
   }
   return c.normalize(sign * b.sign);
   }
   Bigint operator / ( Bigint b ) {
   if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
   Bigint c("0"), d;
   for( int j = 0; j < (int)a.size(); j++ ) d.a += "0";
   int dSign = sign * b.sign; b.sign = 1;
   for( int i = a.size() - 1; i >= 0; i-- ) {
   c.a.insert( c.a.begin(), '0');
   c = c + a.substr( i, 1 );
   while( !( c < b ) ) c = c - b, d.a[i]++;
   }
   return d.normalize(dSign);
   }
   Bigint operator % ( Bigint b ) {
   if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
   Bigint c("0");
   int cSign = sign * b.sign; b.sign = 1;
   for( int i = a.size() - 1; i >= 0; i-- ) {
   c.a.insert( c.a.begin(), '0');
   c = c + a.substr( i, 1 );
   while( !( c < b ) ) c = c - b;
   }
   return c.normalize(cSign);
   }
   void print() {
   if( sign == -1 ) putchar('-');
   for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
   }
};

int main(){
   string s,y;
  while(cin >>s>>y){
   Bigint K,N,n,t;
   Bigint two("2");
   n=s,t=y;
   K=N=n/two;
   Bigint res=t-t/two;
   N=N-t/two;
   K=K+res;
   K.print();
   cout<<endl;
   N.print();
   cout<<endl;
  }
  return 0;
}

SPOJ FCTRL, Factorial

2011-02-10T23:30:00.002+09:00

SPOJ Problem Set (classical)

11. Factorial

Problem code: FCTRL

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.

For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1
Input

There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.

Output

For every number N, output a single line containing the single non-negative integer Z(N).

Example

Sample Input:

6
3
60
100
1024
23456
8735373
Sample Output:

0
14
24
253
5861
2183837

int zeta(int n) {
int ret = 0;
for (int p = 5; p <= n; p*=5)
ret += n/p;
return ret;
}

int main(){
  int nTests;
  scanf("%d ",&nTests);
  repe(test,1,nTests) {
   //if (1) fprintf(stderr,"Case %d/%d",test,nTests);
   int n;
   cin >> n;
   cout << zeta(n) << endl;
  }

  return 0;
}

SPOJ ADDREV, Adding Reversed Numbers

2011-02-10T23:26:00.000+09:00

SPOJ Problem Set (classical)

42. Adding Reversed Numbers

Problem code: ADDREV

The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.

ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).

Input

The input consists of N cases (equal to about 10000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

Output

For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.

Example

Sample input:

3
24 1
4358 754
305 794

Sample output:

34
1998
1

string rev(string s){

int j=s.size()-1;

rep(i,0,(s.size()/2)){

char temp;

temp=s[i];

s[i]=s[j];

s[j]=temp;

j--;

}

return s;

}

int main(){

int nTests;

scanf("%d ",&nTests);

repe(test,1,nTests) {

string x,y;

int xx,yy;

cin>>x>>y;

x=rev(x);

y=rev(y);

xx=atoi(x.c_str());

yy=atoi(y.c_str());

int res=xx+yy;

ostringstream t;

t << res;

cout<<atoi(rev(t.str()).c_str())<<endl;

}

return 0;

}

TopCoder SRM 148, DIV II, MNS

2011-02-10T11:10:00.000+09:00

Problem Statement

9 numbers need to be arranged in a magic number square. A magic number square is a square of numbers that is arranged such that every row and column has the same sum. For example:

1 2 3
3 2 1
2 2 2
Create a class MNS containing a method combos which takes as an argument a int[] numbers and returns the number of distinct ways those numbers can be arranged in a magic number square. Two magic number squares are distinct if they differ in value at one or more positions. For example, there is only one magic number square that can be made of 9 instances of the same number.

int func(vector <int> num){
  int mgnum=num[0]+num[1]+num[2];
  int k=3;
  rep(i,0,2){
   int temp=0;
   rep(j,0,3){
   temp+=num[k+j];
   }
   if (mgnum!=temp)return 0;
   k+=3;
  }
  k=0;
  rep(i,0,2){
   int temp=0;
   rep(j,0,3){
   temp+=num[k+3*j];
   }
   if(mgnum!=temp)return 0;
   k+=1;
  }
  return 1;
}

class MNS {

public:

int combos(vector <int> numbers) {
sort(all(numbers));
int ans=0;
ans+=func(numbers);
while(next_permutation(all(numbers))){
ans+=func(numbers);
}
return ans;
}

};

TopCoder SRM 148, DIV II, DivisorDigits

2011-02-10T11:09:00.000+09:00

Problem Statement

Create a class DivDigits containing a method howMany which takes as an argument an int number and returns how many digits in number that number itself is divisible by. Count all occurences of such digits in the number, not just the first. See examples for more information.

class DivisorDigits {

public:

int howMany(int number) {
ostringstream ss;
string s;
int ans=0;
ss << number;
s = ss.str();
repsz(i,s){
if(!(s[i]-'0')){continue;}
if(number%(s[i]-'0')==0)ans++;
}
return ans;
}

};

TopCoder SRM 148, DIV II, CeyKaps

2011-02-10T11:08:00.000+09:00

Problem Statement

The keycaps on a keyboard have been switched around, and the user is now trying to remember what he was trying to type.

Create a class CeyKaps containing the method decipher that takes a String typed, representing the visible message on the screen, and a String[] switched, representing the keycap switches. The method should return the original intended message (what keys the user thought he was pressing).

A keycap can be switched around more than once. For example, if someone switched around 'A' and 'S', then switched around 'S' and 'D', then 'D' would be where 'A' originally was, 'S' where 'D' was, and 'A' where 'S' was.

The elements of switches will be formatted as (quotes added for clarity) "*:*", where the *'s represent the keycaps to be switched. The above example would be represented as: {"A:S","S:D","D:A"}, or alternately as {"S:A","D:S","A:D"} or any other such combination. The order of the keycaps doesn't matter, but the order of the switches does.

class CeyKaps {

public:

string decipher(string typed, vector <string> switches) {
vector < pair<char,char> > keys;
repsz(i, switches){
char x,y;
x=switches[i][0];
y=switches[i][2];
keys.pb(mp(x,y));
}
repsz(i,keys){
repsz(j,typed){
if(typed[j]==keys[i].first)typed[j]=keys[i].second;
else if(typed[j]==keys[i].second)typed[j]=keys[i].first;
}
}
return typed;
}

};

Just Another Hacking Tool #2

2011-02-09T02:14:00.000+09:00

In my last post on Just Another Hacking Tool #1, I mentioned a lot about references of basic hacking tool like phishing or penetrating a vulnerable server. And also in that post I mentioned that after reading from the websites (hackpconline, vxchaos, metasploit), I was able to make myself a keylogger. This video will show what I did :D

I made this keylogger with C++, implemented with the usage of openssl, Windows Socket Programming and GUI programming.

Well this is my first self-made keylogger, and I do think that it's 99% FUD (The processing will still be shown in task-manager, and at this point I think all .exe programs cannot run without being scheduled by task manager), but this keylogger is for Windows users only :(

Anyway, this keylogger has the ability to take log characters by characters the victim typed, and by default it will be sent to a defined e-mail in the program. Currently this guy can take around 80 length of characters the victim typed in, but of course It can be easily modified within a second!

The link below shows the video of my keylogger, which I made by using jing, and it's in swf format and I don't know how to insert music in swf file, so, stick with it :D

The video is here

ps: dont spam my email! and if you want me to make one for you, PM me :D

TopCoder SRM 147, DIV II, PeopleCircle

2011-02-08T23:41:00.002+09:00

Problem Statement

There are numMales males and numFemales females arranged in a circle. Starting from a given point, you count clockwise and remove the K'th person from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). After removing that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure numFemales times, there are no females left in the circle.

Given numMales, numFemales and K, your task is to return what the initial arrangement of people in the circle must have been, starting from the starting point and in clockwise order.

For example, if there are 5 males and 3 females and you remove every second person, your return String will be "MFMFMFMM".

class PeopleCircle {

public:

  string order(int m, int f, int K) {
   int tot=m+f;
   int flag[tot];
   memset(flag,1,sizeof(flag));
   string human;
   rep(i,0,tot)human+='M';
   int now=0;
   rep(i,0,f){
   for(int j =0;j<K-1;){
if(now>=tot)now=0;
if(flag[now]){
now++;
while(!flag[now])now++;
j++;
}
else while(!flag[now])now++;
   }
   flag[now]=0;
   while(!flag[now])now++;
   }
   repsz(i,human)if(!flag[i])human[i]='F';
   return human;
  }
};

TopCoder SRM 147, DIV II, CCipher

2011-02-08T23:40:00.000+09:00

Problem Statement

Julius Caesar used a system of cryptography, now known as Caesar Cipher, which shifted each letter 2 places further through the alphabet (e.g. 'A' shifts to 'C', 'R' shifts to 'T', etc.). At the end of the alphabet we wrap around, that is 'Y' shifts to 'A'.

We can, of course, try shifting by any number. Given an encoded text and a number of places to shift, decode it.

For example, "TOPCODER" shifted by 2 places will be encoded as "VQREQFGT". In other words, if given (quotes for clarity) "VQREQFGT" and 2 as input, you will return "TOPCODER". See example 0 below.

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <cstring>
using namespace std;
typedef long long int lli;
typedef long unsigned long llu;

//definitions
#define mem_prep(varx) memset(varx,0,sizeof(varx))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define repe(i,a,n) for(int i=(a);i<=(n);i++)
#define forsz(i,a,v) rep(i,a,sz(v))
#define repsz(i,v) rep(i,0,sz(v))
#define vi vector<int>
#define vs vector<string>

class CCipher {

public:

string decode(string s, int shift) {
repsz(i, s){
s[i]-=shift;
if(s[i]<'A')s[i]+=26;
}
return s;
}

};

Introduction: yuriardila

2011-02-07T21:48:00.000+09:00

Ah, I forgot to introduce myself :D

Like the blog's title, yes, it's my name. yuriardila. And I am currently 21, one step closer to becoming an adult :D Well, I currently live in Japan, 3rd year of Ritsumeikan University, majoring in Computer Science. Not much to tell about my college since I think the education is not too good --no offense :p However, I do learn many stuffs here, and also I make many Japanese friends, and they are all so kind and, unique? And most of them are hardworkers, so you too, better learn from the Japanese!

That's it for my intro!

Cheers,

Just Another Hacking Tool #1

2011-02-07T21:13:00.000+09:00

For those of you who want to learn about hacking, like how do you steal passwords from your friend, or penetrate to a vulnerable server, I got several recommendations of website that you can read:

1. hackpconline
2. or compilation of source codes, vxchaos
3. or find a metasploit penetration testing framework

These sites provide anything there is to help you with hacking, like keylogging tools, phishing templates, XSS softwares, etc.

I myself learn a lot from those websites, and now i can make my own keylogger. So what are you waiting for, hackers-wannabe? :)

TopCoder SRM 192, DIV II, BoxLoader

2011-02-07T20:55:00.002+09:00

Problem Statement

Your company has a new box loading robot. It is your job to program it to pack items into the shipping boxes. The robot does not have a very large program memory so you are restricted to placing all the items into the boxes in the same orientation. Each item is a rectangular solid with dimensions itemX by itemY by itemZ. The box is also rectangular with the dimensions boxX by boxY by boxZ. The items can be placed in the box in any orthogonal orientation (ie. the sides of the items must be parallel to the sides of the box), but only whole items can be placed in the box. Your task here is to determine the greatest number of items that can be packed into the box (with all the items in the same orientation).

For example, if the box is 100x98x81 units and the items are 3x5x7 units, then orienting the items so they are 5x7x3, allows them to fit in the box in a 20x14x27 grid, filling the entire box, which is optimal: 7560 items.

vector<int> items;
vector<int> boxes;

bool func (vector<int> ti, vector<int> tj){
  int mod1=0,mod2=0;
  repsz(i,ti){
   mod1 += boxes[i]%items[ti[i]];
   mod2 += boxes[i]%items[tj[i]];
  }
  return mod1<mod2;
}

class BoxLoader {

public:

int mostItems(int boxX, int boxY, int boxZ, int itemX, int itemY, int itemZ) {
boxes.pb(boxX);
boxes.pb(boxY);
boxes.pb(boxZ);
items.pb(itemX);
items.pb(itemY);
items.pb(itemZ);
int cnt=0;
repsz(i,items){
cnt=0;
repsz(j,boxes)
if(items[i]>boxes[j])cnt++;
if(cnt==3){boxes.clear();items.clear();return 0;}
}
vector<int> perm;
perm.pb(0);
perm.pb(1);
perm.pb(2);
vector<vector<int> > perms;
perms.pb(perm);
while(next_permutation(perm.begin(),perm.end())){
perms.pb(perm);
}
sort(perms.begin(),perms.end(),func);
perm = perms[0];
int ans=1;
repsz(i,perm){
ans*=boxes[i]/items[perm[i]];
}
boxes.clear();items.clear();
return ans;
}

};

TopCoder SRM 293, DIV II, Aquarium

2011-02-07T20:53:00.000+09:00

Problem Statement

You have a fish aquarium. You are given a int[] fishSizes, denoting the size of each fish in the aquarium. They've been getting along pretty well so far, but you would now like to add a new fish (called Bob). You know that fish sometimes eat each other. You estimate that a fish might eat another fish if and only if it is at least two times larger, but no more than ten times larger, than that other fish.

Considering this, you would like to choose Bob's size such that:

- Bob is not in danger of being eaten by any other fish (i.e., its size is not between 1/10 and 1/2, inclusive, the size of any other fish).

- Bob is not tempted to eat any other fish (i.e., no other fish in the aquarium has a size between 1/10 and 1/2, inclusive, of Bob's size).

Your task is to return the number of different integer sizes for Bob between minSize and maxSize, inclusive, that won't cause any eating "conflicts" with other fish.

#include <iostream>
#include <vector>
using namespace std;
#define sz(v) ((int)(v).size())
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define repe(i,a,n) for(int i=(a);i<=(n);i++)
#define forsz(i,a,v) rep(i,a,sz(v))
#define repsz(i,v) rep(i,0,sz(v))
#define vi vector<int>
class Aquarium {

public:

int peaceful(int minSize, int maxSize, vector <int> fishSizes) {
int ans=0,flag;float bob;
int mint=minSize,maxt=maxSize;vi f(fishSizes);
repe(i,mint,maxt){
bob=(float)i;
flag=0;
repsz(j,f){
if((bob/f[j]>0.0999&&bob/f[j]<=0.5)||(bob/f[j]>=2&&bob/f[j]<=10))
{if(bob==1)cout<<"haha"<<endl;flag=1;}
}
if(!flag)ans++;
}
return ans;
}
};

TopCoder SRM 337, DIV II, AnagramList

2011-02-07T20:51:00.001+09:00

Problem Statement

An anagram of a string is any string that contains the same characters in any order. For example, the anagrams of "tree" are, in alphabetical order: "eert", "eetr", "eret", "erte", "eter", "etre", "reet", "rete", "rtee", "teer", "tere" and "tree".

You will be given a String s and an int i. Return the ith (0-based) anagram of s when listed in alphabetical order. If there is no such anagram, return an empty String.

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
typedef long long int lli;
typedef long unsigned long llu;
#define mem_prep(varx) memset(varx,0,sizeof(varx))
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define repe(i,a,n) for(int i=(a);i<=(n);i++)
#define forsz(i,a,v) rep(i,a,sz(v))
#define repsz(i,v) rep(i,0,sz(v))

bool func(string i, string j){
  return i<j;
}

class AnagramList {

public:

  string getAnagram(string s, int i) {
   string ans;
   sort(s.begin(),s.end());
   int n = 1;
   ans = s;
   bool flag = (i!=0);
   while(next_permutation(s.begin(),s.end())){
   if(n==i){ans = s;flag = 1;n--;break;}
   n++;
   }
   if(n>=i)flag=0;
   return ((flag)?ans:"");
  }