ผลต่างระหว่างรุ่นของ "Algo lab/running times"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย ': ''This is part of ske algo lab'' == Task 1: Closest pairs == == Task 2: Sorting == == Test data ==')
 
 
(ไม่แสดง 10 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 
: ''This is part of [[ske algo lab]]''
 
: ''This is part of [[ske algo lab]]''
 +
 +
== Lab descriptions ==
 +
 +
* Work on this [https://theory.cpe.ku.ac.th/wiki/images/Algo-lab-running-time.pdf lab sheet].
 +
* Write quadratic-time solutions to the following two problems.
 +
* Download fast solutions.
 +
* Measure their running times using provided test data and compare them.
  
 
== Task 1: Closest pairs ==
 
== Task 1: Closest pairs ==
 +
 +
{{กล่องสี|#e7e7e7|
 +
'''Task statement'''
 +
 +
You are given a list of '''n''' integers.  You want to find the minimum difference between pairs of these integers.
 +
 +
'''Input'''
 +
 +
* First line: integer '''n'''  ('''n''' is at most 100,000)
 +
* Next '''n''' lines: each line contains one integer (ranging from 1 to 1,000,000,000)
 +
 +
'''Output'''
 +
 +
* One line: the minimum difference between pairs of these integers.
 +
 +
'''Example'''
 +
 +
Input:
 +
<pre>
 +
5
 +
1
 +
50
 +
4
 +
13
 +
25
 +
</pre>
 +
 +
Output:
 +
<pre>
 +
3
 +
</pre>
 +
}}
 +
 +
=== Your job ===
 +
* Template for quadratic solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/closest-slow-template.cpp closest-slow-template.cpp]
 +
* Fast solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/closest-fast.cpp closest-fast.cpp]
 +
* Test data: ''see below''
  
 
== Task 2: Sorting ==
 
== Task 2: Sorting ==
 +
 +
{{กล่องสี|#e7e7e7|
 +
'''Task statement'''
 +
 +
You are given a list of '''n''' integers.  You want to sort them in an increasing order.
 +
 +
'''Input'''
 +
 +
* First line: integer '''n''' ('''n''' is at most 100,000)
 +
* Next '''n''' lines: each line contains one integer (ranging from 1 to 1,000,000,000)
 +
 +
'''Output'''
 +
 +
* '''n''' lines: the sorted list of integers
 +
 +
'''Example'''
 +
 +
Input:
 +
<pre>
 +
5
 +
1
 +
50
 +
4
 +
13
 +
25
 +
</pre>
 +
 +
Output:
 +
<pre>
 +
1
 +
4
 +
13
 +
25
 +
50
 +
</pre>
 +
}}
 +
 +
=== Your job ===
 +
* Template for quadratic solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/sort-slow-template.cpp sort-slow-template.cpp]
 +
* Fast solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/sort-fast.cpp sort-fast.cpp]
 +
* Test data: ''see below''
  
 
== Test data ==
 
== Test data ==
 +
* Download [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/testdata/ here]

รุ่นแก้ไขปัจจุบันเมื่อ 00:56, 3 กันยายน 2561

This is part of ske algo lab

Lab descriptions

  • Work on this lab sheet.
  • Write quadratic-time solutions to the following two problems.
  • Download fast solutions.
  • Measure their running times using provided test data and compare them.

Task 1: Closest pairs

Task statement

You are given a list of n integers. You want to find the minimum difference between pairs of these integers.

Input

  • First line: integer n (n is at most 100,000)
  • Next n lines: each line contains one integer (ranging from 1 to 1,000,000,000)

Output

  • One line: the minimum difference between pairs of these integers.

Example

Input: 

5
1
50
4
13
25

Output: 

3

Your job

Task 2: Sorting

Task statement

You are given a list of n integers. You want to sort them in an increasing order.

Input

  • First line: integer n (n is at most 100,000)
  • Next n lines: each line contains one integer (ranging from 1 to 1,000,000,000)

Output

  • n lines: the sorted list of integers

Example

Input: 

5
1
50
4
13
25

Output: 

1
4
13
25
50

Your job

Test data

ดึงข้อมูลจาก "https://theory.cpe.ku.ac.th/wiki/index.php?title=Algo_lab/running_times&oldid=58061"