noogler's blog

By noogler, 10 years ago, translation, In English

Is this code below works on all platform with C++11 compiler?

I know that earlier we had to to use "%I64d" for Windows platform and "%lld" for linux like platforms.

long long = (long long)1e18;
printf("%lld\n", a);

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By noogler, 11 years ago, In English

Hello everybody, I have no idea to this problem, have you ?

Chess association decided to assign new phone numbers to all the members.

The new numbers should be produced with a knight's move on a phone keypad. 0 and 8 are not valid leading digits.

For instance, the number 340-49-27 matches the criteria.

7  8  9
4  5  6
1  2  3
   0	 

Create a program that computes the number of different phone numbers with a length N.

1 ≤ N ≤ 56'789

It is standard problem with small N, which can be solved by dynamic programming.

I tried to solve it with Matrix Exponentiation (of size 10x10). But it also TL ( O(10 ^ 3 * logn * BigInt) ), because of the multiplying very big numbers.

Full text and comments »

Tags dp
  • Vote: I like it
  • +10
  • Vote: I do not like it