Posts Tagged “SPOJ”

Oct 10 2010

用容斥原理计算被Hyperplane切割后的Hyperrectangle体积

Posted by watashi in summary, tags: , ,

被问到上次ZOJ Monthly中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做，然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为

\{(x_1,x_2,\cdots,x_n)|0\le x_1\le X_1, 0\le x_2\le X_2, \cdots, 0\le x_n\le X_n\}

而对应的Hyperplane为
a_1x_1+a_2x_2+\cdots+a_nx_n=b

那么我们实际要求的就是Convex
\{\mathbf{x}|0\le x_i\le X_i,\mathbf{a}^T\mathbf{x}\le b\}

的体积。

不妨先考虑两个二维平面上的例子：

mp-case-1

\{(x,y)|0\le x\le 4,0\le y\le 3,x+y\le 5\}

Comments 14 Comments »

Feb 09 2010

Small factorials

Posted by watashi in solution, tags: , , , , , , , , , , ,

SPOJ24. Small factorials[FCTRL2]就是阶乘计算加高精度运算。以下是用内置大数支持的perl, php, java, ruby, python, haskell, bash, scheme等语言实现的代码。

haskell

main = interact $ unlines . map (\i -> show $ f !! read i) . tail . words
	where f = scanl (*) 1 [1 ..]

perl

#!/usr/bin/perl -w

use strict;
use Math::BigInt lib => 'GMP';

my @f = ();
push @f, Math::BigInt->new(1);
for (my $i = 1; $i <= 100; ++$i) {
	push @f, $f[$#f]->copy()->bmul($i);
}
chomp(my $re = <STDIN>);
for (my $ri = 1; $ri <= $re; ++$ri) {
	chomp(my $n = <STDIN>);
	print "$f[$n]\n";
}

php

Comments 15 Comments »

Dec 24 2009

My SyntaxHighlighter 2.0 Haskell Brush

Posted by watashi in work, tags: , , , , , , , , ,

As I cannot find any appropriate haskell brushes for SyntaxHighlighter, I developed one by myself. You can download it here, I do hope it will be helpful. If you find any bugs or have any suggestions, please comment here or email me.

SyntaxHighlighter提供了大多流行语言的Brush，但是相对而言支持的语言还是比较少的。如果你需要的某种语言不幸不在支持列表内，那么你还可以求助于第三方Brush，这里有一个更加丰富语言列表，不过不是所有的语言都有对应的Brush。更不幸的是，我需要的Haskell语言甚至都不在这个列表里。google了一下还是看到有别人写的Brush，不过功能实在有点弱，所以我开始按照Handy Custom Brushes Development Guide自己写一个Haskell Brush。

在Guide的指导下，在参考着其他语言的Brush和其他平台下Haskell的高亮配置文件，我自己的shBrushHaskell.js也有模有样的完成了。最后要做的就是把它加到wordpress的plugin里，参照Adding A New Brush (Language)便能很容易完成。事实上在在我使用的SyntaxHighlighter Evolved里只要先把shBrushHaskell.js上传到合适的位置，比如$plugin_dir/watashi-no-brushes，再对syntaxhighlighter.php做两处修改就好了：

  1. 在一堆wp_register_script中间插入一句 
    /* register my brush */
wp_register_script('syntaxhighlighter-brush-haskell', plugins_url('syntaxhighlighter/watashi-no-brushes/shBrushHaskell.js'), array('syntaxhighlighter-core'), '20091224'); // ADD_THIS_LINE
  2. 再添加映射

    $this->brushes = (array) apply_filters( 'syntaxhighlighter_brushes', array(
    /* ... */
    'haskell' => 'haskell', // ADD_THIS_LINE
) );

    3. 大功告成。

首先拿A + B Problem做个测试： 

main = do
    input <- getContents
    putStr $ unlines $ map show $ doEMP $ map read $ words input

doEMP [] = []
doEMP (a:b:o) = a + b : doEMP o

再加两个demo，第一个是ProjectEuler的41：

Comments 5 Comments »