Archive

Archive for May, 2010

May SAT2 2400!


仅于此记录首战告捷的喜悦。

Categories: Old Blog Posts

sat2


Categories: Old Blog Posts

猴子爬楼梯


昨天学校数学竞赛时遇到一道很有趣的题,迫于时间,当时只能用凑的方法写上一个答案。后来终于在某节无聊的课上把它解决了。

问题描述:一只猴子在一架共有n级的梯子上爬上爬下,它每次或者上升16级,或者下降9级,如果它能从地面爬到最顶上一级,然后回到地面,那么n的最小值是?

解答:我们把每次走的决策总结成下表:

0 16 32 48 64 80 96 112 128 144
7 23 39 55 71 87 103 119 135
14 30 46 62 78 94 110 126
5 21 37 53 69 85 101 117
12 28 44 60 76 92 108
3 19 35 51 67 83 99
10 26 42 58 74 90
1 17 33 49 65 81
8 24 40 56 72
15 31 47 63
6 22 38 54
13 29 45
4 20 36
11 27
2 18
9
0

左上角是猴子开始时的高度,若向上爬则向右移动一格,下降则向下移动一格,直到碰到0结束,在这样任一条路径中遇到的最大数值就是n的一个可能值,也就是说我们要寻找一条路径,使得这路径上最大的数值最小。

我们先来分析0的可能位置。显然,每一列数的个数是单调递增的,而0只可能出现在某一列的最后一个数,为了尽可能地使路径上的数最小,我们要让路径“尽量靠着边上”,据此不难得出下列算法:

从0出发,每次先加16,再重复减9直到不能减,遇到0结束。这一列数中最大的数就是n的取值。

这里我们给出整个数列:

0, 16, 7, 23, 14, 5, 21, 12, 3, 19, 10, 1, 17, 8, 24, 15, 6, 22, 13, 4, 20, 11, 2, 18, 9, 0

所以n的最小值是24。不难证明,该算法可推广到上下任意步的情形。

Categories: Old Blog Posts

My first LaTeX article


This is my first LaTex product. It described an inequality problem in Mathematics. The source file is also offered.

http://rapidshare.com/files/387520976/1.pdf

http://rapidshare.com/files/387521278/1.tex

Here’s the famous LaTeX tutoring text written in Chinese:

http://rapidshare.com/files/387522883/lshort-cn.pdf

Categories: Old Blog Posts

Daily Report 2010


Start since 4.29.2010

April

29th review SAT2/study ordinary differential equations/Heroes III with labadi

30th reviewSAT2/pretest: Chem 800(76/85) Math800(44/50)  Phys770(61/75)

May

1st SAT2/800+800+800

2nd Mountain Climbing/Avatar/Great Expectations/Thesis

3rd Great Expectations/Heroes III/Edit midi

4th Great Expectations/LaTeX

5th Great Expectations/Lost s6e14/OG/SAT vocabulary

6th Discuss math projects/Great Expectations done/OG

7th Brave New World/OG

8th Brave New World/OG/Make research program/Learn LaTeX and make the fisrt document

9th Learn LaTeX/OG/

10th OG/Preparing for Top Tenth/Brave New World

11th OG/Preparing for Top Tenth/Brave New World

12th OG/Preparing for Top Tenth/judge for Unit 5/discuss the thesis

13th OG/Preliminary round/judge for Unit 8

14th OG/Brave New World done

15th OG/Far From the Madding Crowd/Thesis

16th OG/Far From the Madding Crowd/Thesis/Research Project

17th OG/Thesis

18th OG No.5/Thesis

19th OG/Thesis/School Math Competition

20th OG/recollect simulative test/Thesis

21st~31st OG No.1~No.8/collect new words/Quarter-Final of Top 10: 1th/Far From the Madding Crowd done/Compose the beginning score of Top 10

June

1st~3rd preparing for SAT

4th preparing for SAT/21st anniversary: remembrance

5th SAT Reasoning Test/580+800+530

6th Review Politics

7th Review Geography

8th Review History

9th Academic Level Assessment Test-so easy/But terrible/AAB

10th Recover OI-AC 3 problems/Learn SAP/Review Hungary Algorithm

11th AC 3 problems/Learn Binary Arrays

12th AC 3 problems/Learn rectangular cut, ST algorithm for RMQ problem

13th AC 2 problems/Learn 2-Dimensional Binary Arrays, Merge Tree

14th AC 1 problem/Learn Tarjan Algorithm, SBT

15th AC 5 problems/Practice Net Flow Graph Constructing

16th AC 2 problems/Practice Net Flow Graph Constructing/Accompaniment of Top 10

17th AC 1 problem/Prepare for Top 10/Practice States Compression DP

18th AC 2 problems/Rehearsal of Top 10/

19th Top 10/Third Prize

……….Fighting for OI

July

2nd~6th GDOI/Day1 74/ Day2 66/ Day 3 34 Total 174 Rank 27 Third Prize

……….Continue Fighting for OI:NOI problems, poj..

22nd: Start working on 24 problems in Linear Programming and Net Flow

..25th:24 problems in Linear Programming and Net Flow done

25th~27th: work on graph problems, review Splay, work on cash

28th: review binary arrays, RMQ, LCA, conduction of quadrilateral inequality, decision monotonicity, refinement of SAP

……..~August 6th NOI @ Shandong 334 Copper

August

7th~22th Attend in SAT class/ work on math thesis

23th~ Prepare for TOEFL/ work on math thesis

September

17th The death of my friend

18th TOEFL test(29+26+23+28=106)

19th~ Prepare for SAT/ work on math thesis

30th submit final version of thesis

October

1st~3rd Prepare for SAT/ memorize Barron 3500& high frequency 3500/ test\LaTeX in wordpress

4th~8th Prepare for SAT

9th SAT@Hongkong / Composed score R670 M800 W 760 / Review Calculus & learn mathematical analysis

10th~11th Reviewing Mathematical Analysis

12th CMC

13th Wrote essays

14th~15th returned school; wrote essays

16th NOIP preliminary contest, 81

17th National Mathematics Olympics

18th~19th essays, recommendations and materials

20th~22nd essays, prepare for make-up examination

23rd~24th make-up examination, essays, translation, Barron 3500

25th Teacher Evaluation, essays, translation, Barron 3500

26th essays, Barron 3500, Probability Theory

27th essays, Barron 3500, Probability Theory

28th SAT scores available, essays, Barron 3500, Probability Theory, make-up examination scores

29th send all materials, Barron 3500, Probability Theory

30th consider whether take SAT again, Barron 3500, OC-01, collect all required essays

31th consider whether take SAT again, OC-02 (680)

……..SAT Test & TOEFL & University Application/ Nov. SAT terrible / TOEFL 110 (R29+L28+S24+W29) / Recording & submit art materials / essays

December

24th Back again / Working on MIT InvenTeam / Reading: Stalin & Hitler Parrellel Lives / Number Theory / Merry Christmas!

25th Reading: Stalin & Hitler Parellel Lives / Mathematical Analysis Problems / essays

26th Reading: Stalin & Hitler Parellel Lives / Mathematical Analysis Problems

…..Work on essays / Stalin & Hitler Parellel Lives / Mathematical Analysis Problems

Categories: Chronicle

Daily Report 2009


2009年

8月

20日:宅家/战usaco-4题

21日:睡觉/训练

22日:走台/音乐厅演出-尚可..

23日:睡觉/宅/建立深中oi资料库-shenzhongoi@gmail.com

24日:战usaco-1题/入problem-solving strategies *40%/ 重温《se7ven》/看 《大内密探灵灵狗》

多说几句,中国的喜剧电影似乎进入浮躁期了。。内涵,内涵阿!

25日:卡于usaco 5.4.3- character recognition

26日:战usaco-2题(5.4.3解决)/省展演第二(虽然我没去,就差0.01分阿,WTF!!!!!WTFFFFFFF!!)

27日:战usaco-2题/入新书:《抽象代数学》《线性代数》《运筹学》《初等数论》

28日:战usaco-1题/usaco爆关/战南航acm月赛:rank-21

29日:整理usaco第一章 题解/收拾东西准备开学/累到飞起

9月

8月30日~9月6日:开学第 一周/整理usaco第二章题解/结识各位新老师/可惜没有美女/开战vijos动态规化题/发布OI宣传海报(人员很庞大)/ 计划转数学班/联系教学处老师受挫/回二中/二中惊现H1N1/演出彩排被忽悠

7日:vijos *3 效率大爆发

8日:vijos*2 转班一事出现转机

9日:vijos*3 转班尘埃落定

10日:颓/补语文暑假作业 /祝各位老师教师节快乐!

11日:战作业

12日:战作业/合唱团带男生 训练

13日:战作业

14日~20日:开学第三周 /OI进度基本停滞/DP专题结束/搜索专题开始/遭遇《智破连环阵》变态题/遭遇九一七追打门事件/9.18七人会谈/9.19同 喇叭帝聚餐/9.20战英语Brochure/启动pku译题计划

21日:pku译题*2/初赛 复习/补周末作业

22日:战OI/准备补考/同 Moyhoo聊天

23日:全职准备补考/pku 译题*1

24日:准备补考/战政治课件

25日:准备补考

26日:战补考

27日:战补考/补作业/物理 RP爆发满分

28日:none

29日:none

30日:none

10月

1日:看阅兵式/女兵不错

2日:战800字英文影评

3日:中秋节/与wp同过

4日~8日:无视作业/水历届 普及组题目

9日:补作业/囧

10日~16日:准备 初赛/英语单元测试挂掉/地理考试RP 爆发/

17日:初赛77.5分 市第4

18日:补作业/vijos*1

19日~22日:补作业/编Orz Braid模拟赛

23日:编Orz Braid模拟赛-finished/Be broken up/阅《罗密欧与朱丽叶》《哈姆雷特》

24日:虫食算-搜索70分 AC不能/阅《奥瑟罗》

25日:虫食算以搜索AC/内牛满面,感情冻结

26日:捶胸中

27日:模拟赛/清北

28日 :订正模拟赛题目

29日:Orz Braid模拟赛举行

30日:舌战政治课

31日:模拟赛/270分

11月

1日:模拟赛/60分/题目有误/写政治论文以及补各种作业

2日:模拟赛/280分

3日:订正模拟赛

4日:vijos 满100题/vijos*1/模拟赛

5日:订正模拟赛/请假申请通过

6日:最后一天/忙于各种杂事

7日:模拟赛/240分

8日:模拟赛/340分/深圳第一

9日:停课第1天/阅《动态规划试题分析》/模拟赛/210分/vijos*1/全天累计AC 5题

10日:停课第2天/阅《动态规划试题分析》/模拟赛/131分/DP题*8/全天累计AC 9题

11日:光棍节/停课第3天/模拟赛/300分/DP题*4/全天累计AC 7题

12日:停课第4天/模拟赛/155分/DP题*1/学习双向广搜/NOIP2002-字串变换/整理USACO的DP题解/全天累计AC 2题

13日:停课第5天/继续整理USACO DP题解/订正前3天模拟赛题目/写Kruskal算法的并查集版本

14日:停课第6天/上午模拟赛:265分深圳第一/下午另一模拟赛(未测评)

15日:停课第7天/模拟赛/120分/修改后230分

16日:停课第8天/模拟赛/DP题/全天累计AC8题

17~20日:停课第9~12天/模拟赛/DP/刷URAL/敲Dijkstra+heap

21 日:NOIP2009/260分/全市第二

22日~30日:none

12月

1日~8日:none

9日:社团汇演/songs*4

10日:decide to go abroad



Categories: Old Blog Posts

DementRock's Back


After abandoning this blog for several months, I finally decide to use it again since its browsing speed is no longer anormal. Apparently you’ve mentioned that this passage is written in English. That’s because I’ve determined to go abroad and English has became more important to me. I’ll force myself to try to write in English as much as I can.

Furthermore, since the code style of this blog is terrible, please accpet my recommendation for the other blog site:

http://www.cnblogs.com/dementrock/

which is the blog I’ve been using these days.

Categories: Old Blog Posts