Intro Seminar

BÀI TẬP VÀ LỜI GIẢI TIN HỌC PHỔ THÔNG NĂM THỨ NHẤT, SỐ 1, 26 - 6 - 2009

Giới thiệu

thuật toán tham khi duyệt các bước đi. Tại mỗi bước đi ở

Những bài tập sau đây được lấy từ tài liệu sưu tầm trên điểm đang đứng ta chọn đến điểm gần nhất. Sử dụng lí thuyết đồ thị triển khai như sau:

mạng bạn cho ý kiến nhé.

Bài toán 1. Đi một vòng

Chương trình 1: travel.c

Bài được dịch từ địa chỉ Nhiều người trong nghề nghiệp khác nhau (người đưa

# include # include # include # include # include

< s t d i o . h> < s t d l i b . h> <math . h> < l i m i t s . h>

2.7

thư, người chuyển hàng đến tận nhà, người buôn bán, ...)

2 3 4 5 6

thường đứng trước bài toán: Họ cần khởi hành từ một điểm (thường là chỗ làm việc cố định: Trạm đưa thư, của hàng,

kho hàng hoặc cơ quan làm việc) đến một số địa điểm khác

của khách hàng và sau đó họ lại trở về điểm ban đầu tạo ra một vòng. Cho các điểm mà họ đi vòng qua kí hiệu là

các số từ 1 đến N, điểm đầu tiên là số 1. Mọi khoảng cách hai điểm mà học đi qua (kể cả điểm bắt đầu) đã biết khoảng

10 typedef s t r u c t P o i n t TPoint ; 11 s t r u c t P o i n t { 12 int x , y ; 13 } ;

15 typedef s t r u c t Vex TVex ; 16 s t r u c t Vex { 17 int v , b ; 18 TEdge ∗ edges ; 19 } ;

Vi eT eX

cách là một số nguyên (nhưng cũng có thể là thời gian đi qua

8 # define MAXN 256

khoảng cách này hoặc giá phải trả nào đó để đi qua khoảng

cách này). Không nghi ngờ gì vòng đi càng ngắn (thời gian ít nhất, giá rẻ nhất) càng tốt. Rất tiếc tìm được đường vòng tốt nhất không phải là việc dễ khi số điểm phải đi qua lớn.

Nhiệm vụ của chúng ta là viết một chương trình travel.exe, mà nó thử tìm đường trong thời gian cho phép với lời giải tốt nhất.

Các dữ liệu được cho trong tệp, chương trình phải đọc

được vào. Hàng đầu tiên của tệp vào là số N (3 < N < 200) là số điểm mà họ cần đi qua kể cả điểm đầu tiên. Mỗi N dòng sau đó chứa tọa độ nguyên của điểm các nhau

bởi kí tự trắng. Khoảng cách giữa hai điểm được tính

theo công thức: Nếu ( x1 , y1 ) và ( x2 , y2 ) thì khoảng cách là

| x1 − x2 | + |y1 − y1 |. Tất cả các tọa độ là số nguyên không âm và không vượt quá 10000.

Tệp ra là tệp văn bản chuẩn. Nó chứa một hàng với hoán

vị của các số từ 1 đến N cách nhau một khoảng trắng là đường đi phải tìm. Ví dụ

travel.in 6 0 40 25 20 40 10

travel.out 1 4 6 5 3 2

0 0 5 10 20 20

Phân tích và chọn thuật toán. Bài toán có một số cách tiếp cận. Đây là bài toán người đưa hàng đã biết. Vậy ta sử dụng 1/4

21 typedef s t r u c t Edge TEdge ; 22 s t r u c t Edge { 23 i n t v , w; 24 TEdge ∗ next ; 25 } ;

27 28 29 30 31 32

int n ; TPoint pt [MAXN] ; TVex vs [MAXN] ; clock_t s ; i n t bp ; i n t path [MAXN] ;

34 void r e a d f ( void ) ; 35 void s o l v e ( void ) ; 36 void w r i t e f ( void ) ;

38 i n t main ( void ) { 39 readf ( ) ; 40 solve ( ) ; 41 writef ( ) ; 42 return 0 ; 43 }

45 46 47 48 49 50 51 52 53 54 55 56 57

void r e a d f ( void ) { / ∗ FILE ∗ f i n ; ∗ / int i ; /∗ f i n = fopen (" t r a v e l . in " , "r " ) ; f s c a n f ( f i n , "%d " , &n ) ; f o r ( i = 0 ; i < n ; ++ i ) f s c a n f ( f i n , "%d %d\n " , &p t [ i ] . x , &p t [ i ] . y ) ; fclose ( fin ); ∗/ s c a n f ( "%d " , &n ) ; f o r ( i = 0 ; i < n ; ++ i ) s c a n f ( "%d%d " , &pt [ i ] . x , &pt [ i ] . y ) ; }

BÀI TẬP VÀ LỜI GIẢI TIN HỌC PHỔ THÔNG NĂM THỨ NHẤT, SỐ 1, 26 - 6 - 2009 121 }

72 void w r i t e f ( void ) { 73 int i ; 74 p r i n t f ( "%d " , path [ 0 ] + 1 ) ; 75 f o r ( i = 1 ; i < n ; ++ i ) 76 p r i n t f ( " %d " , path [ i ] + 1 ) ; 77 p r i n t f ( " \n " ) ; 78 }

Bài toán 2. Trò chơi Mặt giấy kẻ ka rô thành các ô vuông giống nhau. Mỗi ô vuông xác định bằng số hàng và số cột. Đánh số theo hàng và theo cột từ 1. Trên một ô vuông đặt quân cờ. Hai người chơi lần lượt thực hiện các bước đi bằng cách dịch chuyển

2.7

59 void s o l v e ( void ) { 60 int i , j ; 61 void add_edge ( i n t a , i n t b ) ; 62 i n t d f s ( i n t v , i n t cp , i n t l e n ) ; 63 s = clock ( ) ; 64 f o r ( i = 0 ; i < n ; ++ i ) 65 f o r ( j = 0 ; j < n ; ++ j ) 66 i f ( i != j ) 67 add_edge ( i , j ) ; 68 bp = INT_MAX; 69 dfs ( 0 , 0 , 1 ) ; 70 }

ở trên cùng một hàng, nhưng số của cột giảm đi một số, mà nó là số chính phương, hoặc là nó ở trên cùng một cột, nhưng số hàng giảm đi một số mà nó là số chính phương. Nghĩa là nếu quân cờ nằm tại hàng i và cột j (hoặc tại vị trí

(i, j)), thì nó có thể dịch chuyển đến tới số nào đó tại vị trí

(i, j − 1), (i, j − 4), (i, j − 9), ... hoặc là tới vị trí nào đó trong (i − 1, j), (i − 4, j), (i − 9, j), ... Nhưng luôn luôn đảm bảo

Vi eT eX

80 void add_edge ( i n t a , i n t b ) { 81 TEdge ∗e , ∗∗ se ; 82 e = ( TEdge∗ ) malloc ( s i z e o f ( TEdge ) ) ; 83 e −>v = b ; 84 e −>w = abs ( pt [ a ] . x − pt [ b ] . x ) 85 + abs ( pt [ a ] . y − pt [ b ] . y ) ; 86 f o r ( se = &vs [ a ] . edges ; 87 ∗ se && ( ∗ se )− >w < e −>w; se = &(∗ se )− >next ) 88 ; 89 e −>next = ∗ se ; 90 ∗ se = e ; 91 }

quân cờ. Đến lượt đi phải di chuyển quân cờ sao cho nó còn

93 i n t d f s ( i n t v , i n t cp , i n t l e n ) { 94 TEdge ∗ e ; 95 int i , u; 96 clock_t c ; 97 i f ( cp < bp ) { 98 vs [ v ] . v = 1 ; 99 f o r ( e = vs [ v ] . edges ; e ; e = e−>next ) 100 i f ( e−>v == 0 && l e n == n ) { 101 i f ( cp + e−>w < bp ) { 102 bp = cp + e −>w; 103 u = v; 104 f o r ( i = n − 1; i >= 0 ; −− i ) { 105 path [ i ] = u ; 106 u = vs [ u ] . b ; 107 } 108 } 109 } 110 e l s e i f ( vs [ e−>v ] . v == 0 ) { 111 c = clock ( ) ; 112 i f ( ( c − s ) / 1000.0 > 4 . 9 ) 113 return 1 ; 114 vs [ e−>v ] . b = v ; 115 i f ( d f s ( e−>v , cp + e−>w, l e n + 1 ) ) 116 return 1 ; 117 } 118 vs [ v ] . v = 0 ; 119 } 120 return 0 ;

trong khung của sân chơi. Trò chơi kết thúc khi một trong người chơi đặt quân cờ vào vị trí (1, 1). Người chơi bước đi sau cùng là chiến thắng. Cũng có thẻ Một vị trí (i, j) gọi là chiến thắng, nếu khi đặt quân cờ vào

đó, người chơi bắt đầu chơi có thể tổ chức thực hiện sao cho dành chiến thắng, không phụ thuộc vào cách chơi của đối thủ của nó. Hãy viết chương trình game.exe, mà nó nhập vào bốn số i1 , j1 , i2 , j2 , mỗi số thuộc tập hợp {0, 1, 2, ..., 500}

và i1 < j1 , j1 < j2 và nó tính số lượng vị trí chiến thắng (i, j), mà chúng thỏa mãn i1 < i < i2 và j1 < j < j2 . Giữ liệu

nhập vào là tệp chứa một hàng bốn số nguyên i1 , j1 , i2 , j2

cách nhau dấu trắng. Kết quả phải đưa ra tệp chuẩn chứa một số nguyên.

Ví dụ game.in 0 0 2 2

game.out 0

Lời giải. Trò chơi này thuộc lớp trò chơi mà với chúng số lượng các tình thế đủ nhỏ để ta có thể ghi được trong bộ nhớ các thông tin về mỗi trạng thái. Với trò chơi này một tình thế hoặc một vị trí là cặp số ( x, y) xác định một ô trên bàn chơi. Mỗi vị trí có hai giá trị thắng và thua. Vì mỗi giá trị chỉ ra người chơi đến lượt rơi vào vị trí đã cho có thể thắng cuộc chơi không phụ thuộc vào cách chới của đối thủ và phải chăng sẽ bị thua nếu đối thủ đi bước tối ưu. Một đặc trưng quan trọng khác của trò chơi là không chu trình (vòng tròn lặp lại) và kết thúc.Nghĩa là, nếu từ một vị trí có thể đến một vị trí khác, thì không thể từ vị trí thứ hai này

2/4

BÀI TẬP VÀ LỜI GIẢI TIN HỌC PHỔ THÔNG NĂM THỨ NHẤT, SỐ 1, 26 - 6 - 2009 trở lại vị trí ban đầu. Ngoài ra trò chơi sẽ kết sau hữu hạn

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

bước không phụ thuộc vào các người chơi. Khi đó dễ thấy rằng phải chăng một vị trí là thắng hoặc thua phụ thuộc vào các vị trí như thế nào mà có thể từ một vị trí đến nó. Thật vậy, nếu từ một bước đi đạt đến vị trí thua, thì vị trí đang đến là thắng. Nếu không có vị trí thua, đến nó có thể từ một bước đi (tất cả vị trí cho phép là thắng), thì vị trí là thua. Ta

2.7

chú ý rằng một vị trí chỉ phụ thuộc vào vị trí có các số x và y nhỏ hơn. Suy ra để tính giá trị của một vị trí chỉ cần tính

vị trí có chỉ số x và y nhỏ hơn là đủ. Điều này chỉ ra rằng một cách tính các vị trí là theo hàng tăng của các chỉ số. Chỉ còn xác định vị trí cơ sở, từ nó lần lượt tính các điểm còn lại.

Triển khai mô tả trên bằng trực tiếp. Trước tiên ta tính giá

Vi eT eX

Điều này thực hiện bằng ba vòng lặp. Một vòng cho x, một 1, 2, 3, .... Sau đó sẽ duyệt bảng trong khoảng [1, i2 ) × [1, j2 )

1 2 3 4 5 6 7

# include < s t d i o . h> # undef max # define MAXN 512 # define MAXS 32 int i1 , j1 , i2 , j 2 ; i n t sq [MAXS] , a [MAXN] [MAXN] ; i n t ans ;

9 void r e a d f ( void ) ; 10 void s o l v e ( void ) ; 11 void w r i t e f ( void ) ; 13 14 15 16 17 18

i n t main ( void ) { readf ( ) ; solve ( ) ; writef ( ) ; return 0 ; }

20 void r e a d f ( void ) { 21 s c a n f ( "%d%d%d%d " , &i 1 , &j 1 , &i 2 , &j 2 ) ; 22 }

Được lấy từ http://nhdien.wordpress.com

points.exe tìm số lượng các điểm có tọa độ nguyên nằm trong hoặc nằm trên các cạnh của đa giác đã cho. Định dạng tệp vào

32 f o r ( i = 1 ;

i < i 2 ; ++ i )

Dữ liệu đầu vào theo tệp tiêu chuẩn: Dòng đầu tiên là

số n. n dòng tiếp theo, mỗi dòng lần lượt chứa cặp tọa độ xi , yi , i = 1, 2, ..., n là những số nguyên, phân biệt nhau bởi

dấu cách. Định dạng tệp ra Số lượng tìm được đưa ra tệp chuẩn. Giới hạn bài toán: 3 ≤ n ≤ 1000, xi và yi là các số nguyên

trong khoảng [−104 , 104 ]. Ví dụ point.in 5 0 5 5 3 1

int b ) ;

29 f o r ( i = 0 ; i < MAXS; ++ i ) 30 sq [ i ] = ( i + 1 ) ∗ ( i + 1 ) ;

Trong mặt phẳng cho n điểm Ai ( xi , yi ), i = 1, 2, ..., n là

các đỉnh của đa giác A1 A2 ...An . Hãy viết chương trình

24 void s o l v e ( void ) { 25 i n t i , j , k ; 27 i n t max ( i n t a ,

++ i ) ++ j )

Bài toán 3. Đếm điểm

và đếm vị trí thắng.

Chương trình 2: game.c

1 && a [ i ] [ j −sq [ k ] ] ; ++k )

54 i n t max ( i n t a , i n t b ) { 55 r e t u r n ( ( a > b ) ? a : b ) ; 56 }

trị của tất cả các vị trí với x và y trong khoảng [1, i2 ) × [1, j2 ). vòng cho y và vòng thứ ba duyệt các ô vuông của các số

{ 1 && a [ i −sq [ k ] ] [ j ] ; ++k )

50 void w r i t e f ( void ) { 51 p r i n t f ( "%d\n " , ans ) ; 52 }

Hiển nhiên vị trí cơ sở là (1, 1) và hơn thế, nó là điểm thua vì người chơi rơi vào điểm này coi như thua trận.

f o r ( j = 1 ; j < j 2 ; ++ j ) f o r ( k = 0 ; i − sq [ k ] >= ; i f ( i − sq [ k ] >= 1 ) a[ i ][ j ] = 1; else { f o r ( k = 0 ; j − sq [ k ] >= ; i f ( j − sq [ k ] >= 1 ) a[ i ][ j ] = 1; } } for ( i = i1 + 1; i < i2 ; for ( j = j1 + 1; j < j2 ; ans += a [ i ] [ j ] ; }

point.out 20

0 0 3 2 4

Phân tích. Kí hiệu diện tích của đa giác là S. số lượng các điểm tọa độ nguyên trên các cạnh của tứ giác là B, số điểm 3/4

BÀI TẬP VÀ LỜI GIẢI TIN HỌC PHỔ THÔNG NĂM THỨ NHẤT, SỐ 1, 26 - 6 - 2009 tọa độ nguyên bên trong tứ giác là I. Trong hình học tổ hợp có công thức phụ thuộc sau: S=

1 B + I − 1. 2

Có những thuật toán dễ dàng tìm được các điểm tọa độ nguyên trên biên của đa giác và cũng như diện tích của đa trong đa giác và bài toán như vậy được giải.

Diện tích của đa giác được tìm bằng công thức tính tổng

của tích: ( x j − x j+1 ) ∗ (y j + y j+1 ) với j = 1, 2, ..., N (N + 1 trùng với 1). Thuật toán này có độ phức tạp O( N ). Kết quả

tính tổng trên lấy giá trị tuyệt đối cho ta hai lần diện tích của đa giác.

Tìm các điểm nguyên trên các cạnh đa giác ta thực hiện

tìm chúng trong mọi cạnh và cộng thêm N (các điểm đỉnh

đoạn thẳng bằng ước số chung lớn nhất của hai hiệu tọa độ x và y ở hai đầu đoạn thẳng trừ đi 1. Nghĩa là ta sẽ có tổng gcd(| x j − x j+1 |, y j − y j+1 ) − 1 với j = 1, 2, ..., N (N + 1 tương

đương với 1), ở đây kí hiệu gcd là hàm ước số chung lớn Phương án cài đặt.

Chương trình 3: demdiem.c

1 2 3 4 5 6 7 8 9 10 11

43 i n t gcd ( i n t a , 44 { 45 int t ; 46 while ( b ) 47 { 48 t = b; 49 b = a % b; 50 a = t; 51 } 52 return a ; 53 }

Vi eT eX

của tứ giác). Ta biết rằng số lương các điểm nguyên trên một

nhất.

34 i n t a r e a 2 ( ) 35 { 36 int i , a ; 37 f o r ( i = a = 0 ; i < n ; i ++) 38 a += ( ps [ i ] . x − ps [ i + 1 ] . x ) ∗ ( ps [ i ] . y 39 + ps [ i + 1 ] . y ) ; 40 r e t u r n abs ( a ) ; 41 }

2.7

giác. Nhờ công thức trên ta tính được số điểm có tọa độ bên

30 i = ( a2 − b + 2 ) / 2 ; 31 p r i n t f ( "%d\n " , b + i ) ; 32 }

# include < c s t d i o > # include using namespace s t d ; c o n s t i n t maxn = 1 0 0 1 ; s t r u c t Point { int x , y ; }; int n ; P o i n t ps [ maxn ] ; void s o l v e ( ) ;

13 i n t main ( ) 14 { 15 solve ( ) ; 16 return 0 ; 17 }

19 void s o l v e ( ) 20 { 21 i n t i , a2 , b ; 22 i n t area2 ( ) ; 23 i n t bor der ( ) ; 24 s c a n f ( "%d " , &n ) ; 25 f o r ( i = 0 ; i < n ; i ++) 26 s c a n f ( "%d%d " , &ps [ i ] . x , &ps [ i ] . y ) ; 27 ps [ n ] = ps [ 0 ] ; 28 a2 = a r e a 2 ( ) ; 29 b = bor der ( ) ;

4/4

int b)

55 i n t bor der ( ) 56 { 57 int i , b ; 58 f o r ( i = b = 0 ; i < n ; i ++) 59 b += gcd ( abs ( ps [ i ] . x − ps [ i + 1 ] . x ) , 60 abs ( ps [ i ] . y − ps [ i + 1 ] . y ) ) ; 61 return b ; 62 }