| [ QuizWit ] in KIDS 글 쓴 이(By): Sue (eXponent) 날 짜 (Date): 2002년 9월 2일 월요일 오후 02시 39분 27초 제 목(Title): Re: Postage Stamp 문제 1. 7센트짜리와 11센트짜리 우표만 있는데 몇센트 이상이 되면 그 두가지 종류의 우표만으로 다 붙일 수 있을까하는 문제. 2. 일반화 시키면 모든 gcd(m,n) = 1인 m, n>= 1 에 대하여, 최소한 k센트 이상은 m 센트와 n 센트짜리 우표만으로 붙일 수 있는 k가 존재함하는가? prove or disprove. -------------- 1. 7 * 8 - 11 * 5 = 1 7 * (16 mod 11) - 11 * ( 10 mod 7) = 2 7 * (24 mod 11) - 11 * ( 15 mod 7) = 3 7 * (32 mod 11) - 11 * ( 20 mod 7) = 4 7 * (40 mod 11) - 11 * ( 25 mod 7) = 5 7 * (48 mod 11) - 11 * ( 30 mod 7) = 6 7 * (56 mod 11) - 11 * ( 35 mod 7) = 7 7 * (64 mod 11) - 11 * ( 40 mod 7) = 8 7 * (72 mod 11) - 11 * ( 45 mod 7) = 9 7 * (80 mod 11) - 11 * ( 50 mod 7) = 10 7 * (88 mod 11) - 11 * ( 55 mod 7) = -66 (+ 77 = 11) 7 * ( 8 mod 11) - 11 * ( 60 mod 7) = 12 7 * (16 mod 11) - 11 * ( 65 mod 7) = 13 7 * (24 mod 11) - 11 * ( 70 mod 7) = 14 7 * (32 mod 11) - 11 * ( 5 mod 7) = 15 7 * (40 mod 11) - 11 * ( 10 mod 7) = 16 7 * (48 mod 11) - 11 * ( 15 mod 7) = 17 7 * (56 mod 11) - 11 * ( 20 mod 7) = -59 (+ 77 = 18 = 7 + 11) .... 이하 생략 .... 59는 두가지 종류의 우표만으로 표현할 수 없다... (59+77*k (k>=1)의 형태는 표현할 수 있음) 7*x + 11*y , (|x| < 11 , |y| < 7) 으로 0~76까지 표현이 가능하므로, 기본적으로 77이상이 표현가능하고 위의 식들에서 60이상은 다 표현할수 있다는 것을 추론 할 수 있으므로 답: 60 ------------ ------------ 2, gcd(m, n) = 1 에서 mx + ny = 1 이되는 x,y 가 존재한다. (|x| < n , |y| < m ) 즉 0 <= k < m*n에서 mx + ny = k 를 만족하는 x,y 쌍이 존재하므로 (|x| < n , |y| < m ) m*n이상은 모두 표현 할 수 있다. k = m*n - m - n 인 경우에는 x, y 둘중의 하나는 음수가 되어야 하므로 표현하지 못한다. maybe k = m*n - m - n + 1 = (m-1)(n-1) 이상이면 표현가능 할 듯.. 답: 존재한다. ------------ cf) {m * a + n * b} mod m*n = 1, => {m * k * a + n * b * k } mod m*n = k mod m*n , => [m *{(k*a) mod n} + n * {(k*b) mod m}] mod m*n = k mod m*n ------------ ** sort_int proc mov cx,(ARRAY_COUNT - 1) mov si,offset integer_array L0: push cx mov bx,0 L1: mov ax, [si + bx] add bx,2 cmp ax,[si + bx] jle L2 mSwap [si+bx-2],[si+bx] L2: loop L1 pop cx loop L0 ret sort_int endp ** |