|
เฉลย IOI2006
BLACK BOX
โจทย์ : //www.ioi2006.com/Day2/blackbox/blackbox.pdf
เฉลย : //www.ioi2006.com/Day2/blackbox/blackbox_sol.pdf
Black box เป็นโจทย์ประเภทส่งแต่เอาต์พุต (output-only task) ดังนั้น นักเรียนจึงไม่ต้องส่งโปรแกรม อย่างไรก็ตาม เอกสารนี้จะอธิบายวิธีแก้ปัญหาด้วยโปรแกรม
ขั้นแรก เราจะหาตัวสะท้อนที่อยู่ซ้ายสุดของแถวแรก ซึ่งหาได้ดังนี้
- โยนลูกบอลไปที่ด้านซ้ายของ แถวที่ 1. ซึ่งจะให้ผลลัพธ์ได้ 3 แบบ- ลูกบอล ไม่ชน: หมายความว่าไม่มีตัวสะท้อนในแถวแรก
- ลูกบอลชน 1 ครั้ง: ค่า holeOut จะบอกคอลัมน์ของตัวสะท้อนซ้ายสุดในแถวแรก ตำแหน่งการวางของมันหาได้จากทิศทางที่ลูกบอลออก
- ลูกบอลชนมากกว่า 1 ครั้ง: หมายความว่าลูกบอลถูกส่งลง และชนกับตัวสะท้อนอื่นอีก จะได้ว่า ตำแหน่งการวางของ ตัวสะท้อนซ้ายสุดในแถวแรก คือ '\' ดังนั้น เราจะต้องกลับทิศทางมัน โดยการใช้คำสั่งต่อไปนี้ "Reset, Invert, โยนไปด้านซ้ายช่อง 1" คราวนี้ ลูกบอลจะชน 1 ครั้งและกระเด็นออกทางด้านบน และค่า holeOut จะบอกคอลัมน์ของตัวสะท้อนซ้ายสุดในแถวแรก
หลังจากที่หาตัวสะท้อนอันแรกได้แล้ว เราจะหาตัวสะท้อนอื่นๆในแถวแรกอีก โดยการใช้วิธี Recursive
ในตอนนี้ เราจะรู้ว่ากล่องของเราจะเขียนได้ในรูปแบบนี้ ....\???? เพื่อที่จะหาตัวสะท้อนต่อไป เราจะต้องโยนบอลเข้าไปทางซ้ายของช่องที่เราไม่รู้ ซึ่งทำได้ดังนี้
- ถ้าตัวสะท้อนขวาสุดที่เรารู้เป็น \ เราจะ reset แล้วโยนบอลเข้าทางด้านบนของตัวสะท้อนนั้น ตัวสะท้อนจะเปลี่ยนทิศทางลูกบอลให้ไปทางขวา จากนั้น เราก็ทำเหมือนกับการหาตัวสะท้อนอันแรก
- ถ้าตัวสะท้อนขวาสุดที่เรารู้เป็น / คุณจะต้องกลับทิศตัวสะท้อนอันนี้เพื่อที่จะได้ส่งลูกบอลเข้าทางซ้ายมือของช่องที่เราไม่รู้ช่องแรกได้ เนื่องจากคุณรู้ตำแหน่งของตัวสะท้อนทั้งหมดทางซ้าย ดังนั้นคุณจึงสามารถจัดตำแหน่งมันได้ตามต้องการ สมมติว่าตอนนี้เป็น .../../../????? ตัวสะท้อนอยู่ในคอลัมน์ที่ 4, 7, 10 คุณต้องกลับทิศตัวสะท้อนในคอลัมน์ที่ 10 เพื่อจะหาช่องที่ยังไม่รู้ ซึ่งทำได้ด้วยการกลับทิศตัวสะท้อนทั้งหมด หรือการชนตัวสะท้อนในคอลัมน์ 10 จากทางซ้าย แต่การกลับทิศตัวสะท้อนทั้งหมดนั้นโปรแกรมจะต้องจดจำการกลับทิศ ซึ่งทำให้ยากต่อการเขียนโปรแกรม ดังนั้นเราจะกลับทิศตัวสะท้อนโดยใช้คำสั่งนี้แทน "throw in left 1, throw in top 4, throw in top 7" หลังจากทำตามคำสั่งนี้แล้ว ตัวสะท้อนในคอลัมน์ที่ 10 ก็จะอยู่ในตำแหน่ง \
จากนั้น ทำเหมือนหาตัวสะท้อนอันแรกสุด
จะหาแถวต่อไปได้อย่างไร?
ในการหาแถวอื่นต่อไป คุณจะต้องจัดตัวสะท้อนที่รู้แล้ว ให้มีคุณสมบัติว่าลูกบอลที่พุ่งเข้ามายังพื้นที่ที่เรารู้จะไม่สะท้อนกลับเข้าไปในพื้นที่ที่ยังไม่รู้ได้อีก
สมมติว่าตอนนี้คุณรู้ตัวสะท้อนทั้งหมดในแถวแรกแล้ว และหน้าตาของกล่องก็เป็นแบบนี้
.\\.././\..
???????????
ในการหาตัวสะท้อนซ้ายสุดในแถวที่สอง คุณจะต้องจัดตำแหน่งการวางของตัวสะท้อนในแถวแรกให้เป็นดังนี้ .//.././/.. เพื่อที่จะให้บอลที่พุ่งขึ้นมาจากแถวที่สองมายังแถวแรก จะออกไปทางด้านบนหรือด้านขวาได้โดยไม่สะท้อนกลับเข้าไปใหม่ ซึ่งจะทำให้คุณรู้คอลัมน์ที่บอลพุ่งออกมาจากแถวที่สอง
วิธีที่จัดตำแหน่งตัวสะท้อนนั้นขึ้นอยู่กับส่วนที่คุณรู้ ตัวอย่างเช่น ถ้าคุณได้ค้นพบตัวสะท้อนดังนี้แล้ว
.\\.././\..
..\????????
การจัดตัวสะท้อนในแถวแรกที่ดีที่สุดก็คือ ให้ตัวสะท้อนที่อยู่ทางซ้ายของคอลัมน์ของช่องแรกที่ไม่รู้ในแถวที่สองอยู่ในตำแหน่ง \ และ ให้ตัวสะท้อนที่อยู่ด้านบน และอยู่ทางขวาของคอลัมน์ของช่องแรกที่ไม่รู้ในแถวที่สองอยู่ในตำแหน่ง /
เรียงตัวสะท้อนเพื่อจะหาแถวที่สองเช่นเดียวกับการหาแถวแรก
การหาแถวใหม่จะต้องใช้จำนวนคำสั่งเพิ่มขึ้นเป็น Exponential เพราะว่าการหาคอลัมน์ใหม่ในแต่ละแถวจะต้องเรียงตัวสะท้อนทั้งหมดที่อยู่ก่อนหน้า ดังนั้น วิธีที่ดีที่สุดที่จะหากล่องคือหาจากทั้งสี่ด้านเข้าไปข้างใน ได้แก่ แถวแรก คอลัมน์แรก แถวสุดท้าย และคอลัมน์สุดท้าย จากนั้น หาแถวสอง คอลัมน์สอง ต่อไปเรื่อยๆ ถ้าคุณมีช่องที่ไม่รู้ในแถวแรก n ช่อง คุณจะมีช่องที่ไม่รู้ในแถวสอง n-2 ช่อง
ระมัดระวังการหาในด้านต่างๆ เพราะความหมายของ / และ \ จะแตกต่างกันในแต่ละด้าน
| Create Date : 09 กันยายน 2549 | | |
| Last Update : 28 ตุลาคม 2549 2:14:27 น. |
| Counter : 1004 Pageviews. |
| |
|
 |
|
|
|
Quine
Quine คืออะไร? Quine คือโปรแกรมที่ให้ผลลัพธ์ (output) เป็น source code ของตัวเอง
ยกตัวอย่างเช่น สมมติว่าโปรแกรมต่อไปนี้เป็น Quine
#include
int main(){
xxx
}
|
หลังจากที่เราคอมไพล์ และรัน (สมมติว่าโปรแกรมนี้รันได้) เราก็จะได้ผลลัพธ์เป็น source code ของตัวเอง นั่นคือ เราจะได้ผลลัพธ์เป็น
#include
int main(){
xxx
}
Quine จึงเป็นเรื่องท้าทายสำหรับเซียนโปรแกรมมิ่งทั้งหลาย และถือเป็นเกมโปรแกรมมิ่งเกมหนึ่ง เพราะการเขียน Quine นั้นจะยุ่งๆงงๆพอสมควร ถือเป็นการฝึกความคิดสร้างสรรค์ นอกจากนี้ ยังมีการแข่งกันว่า code Quine ของใครจะสั้นกว่ากันด้วย 
(สำหรับใครที่อยากลองคิดเอง อย่าเพิ่งเลื่อนลงไปดูข้างล่างนะครับ)
ขอยกตัวอย่าง Quine ภาษา C
main(){char *c="main(){char *c=%c%s%c;printf(c,34,c,34);}";printf(c,34,c,34);}
|
ลองทดสอบดูครับว่าผลลัพธ์ที่ได้จะเป็นยังไง
ใครอยากดู Quine ของภาษาต่างๆ ก็เข้าไปดูได้ที่ //www.nyx.net/~gthompso/quine.htm
อ้างอิง : //en.wikipedia.org/wiki/Quine
| Create Date : 28 พฤษภาคม 2549 | | |
| Last Update : 28 พฤษภาคม 2549 23:27:05 น. |
| Counter : 415 Pageviews. |
| |
|
| |
|
|
|
code C
int a=10000,b,c=2800,d,e,f[2801],g;
main(){for(;b-c;)f[b++]=a/5;
for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)
for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}
|
ใครเก่งภาษา C ช่วยบอกทีว่า code นี้มันใช้ทำอะไร
ที่มา : //kitty.in.th/index.php?room=article&id=96
| Create Date : 28 พฤษภาคม 2549 | | |
| Last Update : 28 พฤษภาคม 2549 22:53:47 น. |
| Counter : 977 Pageviews. |
| |
|
| |
|
|
|
ตำรา Algorithm
ขอแนะนำตำรา Algorithm ที่ผมมีอยู่ 2 เล่มนะครับ หวังว่าจะเป็นประโยชน์แก่ท่านที่สนใจไม่มากก็น้อยครับ
Introduction to Algorithms, Second Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
เนื้อหาก็ตามชื่อคือจะเป็นการแนะนำให้รู้จัก Algorithms ต่างๆ ซึ่งจะมีคำอธิบายและรูปประกอบชัดเจน มีบทวิเคราะห์ บทพิสูจน์ที่ละเอียดมาก สงสัยเรื่องไหน พอเปิดอ่านก็จะกระจ่างเลยทีเดียว
หนังสือนี้จะใช้สัญลักษณ์ต่างๆอย่างเข้มงวด คือ เขาจะทำรูปแบบไว้ชัดเจนว่าตรงไหนคือตัวแปร สัญลักษณ์นี้คืออะไร ให้นิยามชัดเจนมาก และจะมีอธิบายทุกอย่าง แทบไม่มีข้อผิดพลาดเลย
บทพิสูจน์จะเน้นไปทางคณิตศาสตร์จนอาจงงเอาได้ครับ บางคนก็ว่าบทพิสูจน์บางอย่างก็เยิ่นเย้อเกิน เพราะพิสูจน์ด้วย intuition ได้ แต่ผมกลับชอบแฮะ เพราะรู้สึกว่ามันเป็นระบบ มีที่มาที่ไปดี และแทบไม่ต้องกังวลเรื่องการใช้สัญลักษณ์ผิดเลย เพราะเขามีการตรวจสอบอย่างดี
ในส่วนอธิบาย Algorithms ของเขา จะเขียนด้วย pseudocode ทั้งหมด ซึ่งรูปแบบ pseudocode ของหนังสือเล่มนี้ เป็นที่นิยมใช้กันมากครับ เพราะอ่านได้ง่าย สื่อความหมายได้ดี
เนื้อหาก็มีดังนี้ครับ
Preface
I Foundations
Introduction
1 The Role of Algorithms in Computing
2 Getting Started
3 Growth of Functions
4 Recurrences
5 Probabilistic Analysis and Randomized Algorithms
II Sorting and Order Statistics
Introduction
6 Heapsort
7 Quicksort
8 Sorting in Linear Time
9 Medians and Order Statistics
III Data Structures
Introduction
10 Elementary Data Structures
11 Hash Tables
12 Binary Search Trees
13 Red-Black Trees
14 Augmenting Data Structures
IV Advanced Design and Analysis Techniques
Introduction
15 Dynamic Programming
16 Greedy Algorithms
17 Amortized Analysis
V Advanced Data Structures
Introduction
18 B-Trees
19 Binomial Heaps
20 Fibonacci Heaps
21 Data Structures for Disjoint Sets
VI Graph Algorithms
Introduction
22 Elementary Graph Algorithms
23 Minimum Spanning Trees
24 Single-Source Shortest Paths
25 All-Pairs Shortest Paths
26 Maximum Flow
VII Selected Topics
Introduction
27 Sorting Networks
28 Matrix Operations
29 Linear Programming
30 Polynomials and the FFT
31 Number-Theoretic Algorithms
32 String Matching
33 Computational Geometry
34 NP-Completeness
35 Approximation Algorithms
VIII Appendix: Mathematical Background
Introduction
A Summations
B Sets, Etc.
C Counting and Probability
สำหรับผม ผมชอบเนื้อหาส่วน Graph Algorithms มากเป็นพิเศษครับ
หนังสือเล่มนี้ไม่จำเป็นต้องอ่านตั้งแต่ต้นจนจบครับ เหมาะสำหรับใช้เป็นตำราอ้างอิงมากกว่า แต่จะอ่านเล่นก็ได้ ด้วยความที่มันหนามากๆ จึงมีคนเรียกมันว่า "หมอน" เพราะว่าใช้หนุนหัวเวลาอ่านแล้วง่วงได้อย่างดีเลยครับ
Algorithm Design
by Jon Kleinberg, Éva Tardos
เล่มนี้เหมาะจะเป็นหนังสือเรียนมากครับ เพราะเป็นหนังสือที่ไม่เน้นสัญลักษณ์มากเกินไป เขาจะเน้นภาคบรรยายและมีตัวอย่างประกอบที่น่าสนใจมาก เหมือนกับว่าเรากำลังฟังเล็กเชอร์อยู่แบบนั้นล่ะครับ
ตามความคิดผม ผมว่าเขาพยายามทำให้ผู้อ่านเกิดแรงบันดาลใจอยากเรียน ทำให้เห็นประโยชน์ของเนื้อหา แล้วจึงเข้าสู่บทเรียน ค่อยๆแก้ปัญหาไปด้วยกัน อะไรทำนองนั้นครับ
ตัวอย่างในหนังสือก็หลากหลาย เน้นการแก้ปัญหาที่เกิดขึ้นในชีวิตจริง มีบทพิสูจน์ที่เข้าใจได้ง่าย และจับประเด็นได้ง่าย แต่ผมก็ยังงงๆกับบทพิสูจน์บางอันอยู่ อาจเป็นเพราะภาษาอังกฤษผมไม่แข็งแรง จึงชอบบทพิสูจน์ที่เน้นสัญลักษณ์อย่างเล่มแรกมากกว่า
ผมว่าหนังสือเล่มนี้มีจุดแข็งอยู่ที่แบบฝึกหัดครับ เป็นส่วนที่ผู้เขียนตั้งใจเขียนไม่น้อยไปกว่าเนื้อหาเลย หนังสือเล่มนี้มีแบบฝึกหัดอยู่ 200 กว่าข้อ ซึ่งแต่ละข้อไม่ง่ายเลย คือเน้นการวิเคราะห์ ความคิดสร้างสรรค์เป็นอย่างมาก
เนื้อหามีดังนี้ครับ
Chapter 1: Introduction: Some Representative Problems
1.1 A First Problem: Stable Matching
1.2 Five Representative Problems
1.3 Solved Exercises
1.4 Excercises
1.5 Notes and Further Reading
Chapter 2: Basics of Algorithms Analysis
2.1 Computational Tractability
2.2 Asymptotic Order of Growth Notation
2.3 Implementing the Stable Matching Algorithm using Lists and Arrays
2.4 A Survey of Common Running Times
2.5 A More Complex Data Structure: Priority Queues
2.6 Solved Exercises
2.5 Exercises
2.7 Notes and Further Reading
Chapter 3: Graphs
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal using Queues and Stacks
3.4 Testing Bipartiteness: An Application of Breadth-First Search
3.5 Connectivity in Directed Graphs
3.6 Directed Acyclic Graphs and Topological Ordering
3.7 Solved Exercises
3.8 Exercises
3.9 Notes and Further Reading
Chapter 4: Greedy Algorithms
4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead
4.2 Scheduling to Minimize Lateness: An Exchange Argument
4.3 Optimal Caching: A More Complex Exchange Argument
4.4 Shortest Paths in a Graph
4.5 The Minimum Spanning Tree Problem
4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure
4.7 Clustering
4.8 Huffman Codes and the Problem of Data Compression
4.9 (*) Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm
4.10 Solved Exercises
4.11 Excercises
4.12 Notes and Further Reading
Chapter 5: Divide and Conquer
5.1 A First Recurrence: The Mergesort Algorithm
5.2 Further Recurrence Relations
5.3 Counting Inversions
5.4 Finding the Closest Pair of Points
5.5 Integer Multiplication
5.6 Convolutions and The Fast Fourier Transform
5.7 Solved Exercises
5.8 Exercises
5.9 Notes and Further Reading
Chapter 6: Dynamic Programming
6.1 Weighted Interval Scheduling: A Recursive Procedure
6.2 Weighted Interval Scheduling: Iterating over Sub-Problems
6.3 Segmented Least Squares: Multi-way Choices
6.4 Subset Sums and Knapsacks: Adding a Variable
6.5 RNA Secondary Structure: Dynamic Programming Over Intervals
6.6 Sequence Alignment
6.7 Sequence Alignment in Linear Space
6.8 Shortest Paths in a Graph
6.9 Shortest Paths and Distance Vector Protocols
6.10 (*) Negative Cycles in a Graph
6.11 Solved Exercises
6.12 Exercises
6.13 Notes and Further Reading
Chapter 7: Network Flow
7.1 The Maximum Flow Problem and the Ford-Fulkerson Algorithm
7.2 Maximum Flows and Minimum Cuts in a Network
7.3 Choosing Good Augmenting Paths
7.4 (*) The Preflow-Push Maximum Flow Algorithm
7.5 A First Application: The Bipartite Matching Problem
7.6 Disjoint Paths in Directed and Undirected Graphs
7.7 Extensions to the Maximum Flow Problem
7.8 Survey Design
7.9 Airline Scheduling
7.10 Image Segmentation
7.11 Project Selection
7.12 Baseball Elimination
7.13 (*) A Further Direction: Adding Costs to the Matching Problem
7.14 Solved Exercises
7.15 Exercises
7.16 Notes and Further Reading
Chapter 8: NP and Computational Intractability
8.1 Polynomial-time Reductions
8.2 Efficient Certification and the Definition of NP
8.3 NP-Complete Problems
8.4 Sequencing Problems
8.5 Partitioning Problems
8.6 Graph Coloring
8.7 Numerical Problems
8.8 co-NP and the Asymmetry of NP
8.9 A Partial Taxonomy of Hard Problems
8.10 Solved Exercises
8.11 Exercises
8.12 Notes and Further Reading
Chapter 9: PSPACE: A Class of Problems Beyond NP
9.1 PSPACE
9.2 Some Hard Problems in PSPACE
9.3 Solving Quantified Problems and Games in Polynomial Space
9.4 Solving the Planning Problem in Polynomial Space
9.5 Proving Problems PSPACE-Complete
9.6 Solved Exercises
9.7 Exercises
9.8 For Further Reading
Chapter 10: Extending the Limits of Tractability
10.1 Finding Small Vertex Covers
10.2 Solving NP-hard Problem on Trees
10.3 Coloring a Set of Circular Arcs
10.4 (*) Tree Decompositions of Graphs
10.5 (*) Constructing a Tree Decomposition
10.6 Solved Exercises
10.7 Exercises
10.8 Notes and Further Reading
Chapter 11: Approximation Algorithms
11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem
11.2 The Center Selection Problem
11.3 Set Cover: A General Greedy Heuristic
11.4 The Pricing Method: Vertex Cover
11.5 Maximization via the Pricing method: The Disjoint Paths Problem
11.6 Linear Programming and Rounding: An Application to Vertex Cover
11.7 (*) Load Balancing Revisited: A More Advanced LP Application
11.8 Arbitrarily Good Approximations: the Knapsack Problem
11.9 Solved Exercises
11.10 Exercises
11.11 Notes and Further Reading
Chapter 12: Local Search
12.1 The Landscape of an Optimization Problem
12.2 The Metropolis Algorithm and Simulated Annealing
12.3 An Application of Local Search to Hopfield Neural Networks
12.4 Maximum Cut Approximation via Local Search
12.5 Choosing a Neighbor Relation
12.6 (*) Classification via Local Search
12.7 Best-Response Dynamics and Nash Equilibria
12.8 Solved Exercises
12.9 Exercises
12.10 Notes and Further Reading
Chapter 13: Randomized Algorithms
13.1 A First Application: Contention Resolution
13.2 Finding the Global Minimum Cut
13.3 Random Variables and their Expectations
13.4 A Randomized Approximation Algorithm for MAX-3-SAT
13.5 Randomized Divide-and-Conquer: Median-Finding and Quicksort
13.6 Hashing: A Randomized Implementation of Dictionaries
13.7 Finding the Closest Pair of Points: A Randomized Approach
13.8 Randomized Caching
13.9 Chernoff Bounds
13.10 Load Balancing
13.11 (*) Packet Routing
13.12 Background: Some Basic Probability Definitions
13.13 Solved Exercises
13.14 Exercises
13.15 Notes and Further Reading
Epilogue: Algorithms that Run Forever
หนังสือสองเล่มนี้ ก็เพียงพอที่จะทำให้เข้าใจ Algorithm ในภาพกว้างๆได้ แต่มันก็ยังเจาะลึกในหลายๆเรื่อง แต่ถ้าใครอยาก Algorithm เฉพาะด้านไป ก็คงต้องหาหนังสือเรื่องนั้นมาอ่าน อย่างผมก็มีหนังสือ Computational Geometry ทั้งเล่มว่าด้วย Algorithm ที่ใช้ทำงานด้านเรขาคณิตต่างๆ อ่านแล้วปวดหัวเลยล่ะครับ
สำหรับตำรา Algorithm ในบ้านเรานั้น ยังคงมีน้อยมาก เรายังคงต้องพึ่งตำราจากต่างประเทศอยู่ แต่ผมก็เห็นหนังสือ Algorithm ภาษาไทยออกมาบ้างแล้วครับ ก็เป็นที่น่ายินดี แต่ผมอยากให้ปรับคุณภาพอีกหน่อย ผมอยากให้เน้นเรื่องความถูกต้อง กับความเข้าใจง่าย (ที่ผมแปลกใจคือหนังสือ Algorithm ของโครงการ สอวน. กลับทำมาได้แย่) ผมไม่ชอบสัญลักษณ์ต่างๆที่อยู่ดีๆก็โผล่ขึ้นมา และไม่ชอบโค้ดภาษา C ยาวๆ เลยครับ น่าจะใช้ pseudocode มากกว่า เพราะทำให้ผู้ใช้ทุกภาษาเข้าใจได้ง่าย ตัดเรื่องจุกจิกของภาษาออกไป จนเหลือแต่แก่นของ Algorithm น่าจะดีกว่า
ใครสนใจเล่มไหนก็บอกผมได้นะครับ
| Create Date : 29 มีนาคม 2549 | | |
| Last Update : 29 มีนาคม 2549 1:53:22 น. |
| Counter : 4912 Pageviews. |
| |
|
| |
|
|
|
โจทย์: ไฟถนน
ไฟถนน
บนถนนสายหนึ่งมีเสาสูงหลายต้นวางเรียงกัน คุณต้องการต่อแสงไฟเพื่อให้ความสว่างให้กับถนนเส้นนี้ โดยจะติดหลอดไฟไว้ที่ยอดของเสา อย่างไรก็ตามคุณต้องการติดไฟให้ความสูงของหลอดนั้นลดหลั่นกันไป โดยนับจากต้นถนน กล่าวคือ ถ้าติดหลอดไฟไว้ที่เสาที่สูง x เมตร ถัดไปจากเสานี้จะติดหลอดไฟที่เสาที่สูงมากกว่า x เมตรไม่ได้
คุณต้องการจะติดไฟให้ได้จำนวนหลอดมากที่สุด จงเขียนโปรแกรมเพื่อหาจำนวนหลอดนี้
อินพุต
บรรทัดแรกคือจำนวนเต็ม n (1 ≤ n ≤ 100,000) แทนจำนวนเสา จากนั้นอีก n บรรทัดจะเป็นรายการความสูงของเสา เป็นเลขจำนวนเต็มมีค่าไม่เกิน 1,000,000,000 โดยไล่ไปตั้งแต่เสาแรกที่ต้นถนน จนถึงเสาสุดท้ายที่ปลายถนน กล่าวคือ บรรทัดที่ i+1 จะเป็นความสูงของเสาต้นที่ i
เอาต์พุต
แสดงจำนวนหลอดไฟมากที่สุดที่สามารถติดได้
ตัวอย่าง
Input:
5
5
3
1
4
1
Output:
4
| Create Date : 28 มีนาคม 2549 | | |
| Last Update : 28 มีนาคม 2549 18:21:58 น. |
| Counter : 341 Pageviews. |
| |
|
| |
|
|
|
|
|
|
ฝากข้อความหลังไมค์
Rss Feed
ผู้ติดตามบล็อก : 1 คน [
