정올반 9.3 수업 2015 시도예선 중고등부 문제

정올반 2일차- 수업

 

2015 시도예선 중고등부 문제

1. 소인수분해 했을 때 8의 개수가 몇 개인지 세면된다. 10!을 소인수분해하면 2^8이 나오는데 2^8 안에는 2^3(8)이 2개 들어가니까 0은 2개

 

2. 간선이 몇 개던 간선의 합은 짝수여야 함

 

3. ‘1 이상’이기 때문에 각 정수에 +1씩 하고 시작한다. 그래서 실제로 계산하는 것은 10-4=6개. 6개를 3개의 막대기로 나눈다고 하면 9C3이므로 9*8*7/3*2*1 = 84, 84개. 만약 숫자 a, b, c에 a>=3, b>=2, c>=1같은 범위가 있다면 (a-3)+(b-2)+(c-1)=9가 된다.

 

4. n, n+1, n+2, n+3, n+4 연속된 5개를 찾음

 

5. 대입해본다. A가 1일 경우 = 3*7=21(x), 9*9=81(x)

                   A가 2일 경우 = 3*4=12(x), 4*8=32(o) → A(2) B(1) C(7) D(8)

                                                                                                                                   X                             E(4)

                                                                       ---------------------

                                                                        D(8) C(7) B(1) A(2)

 

6. 1 2 3 4 5 6 7 8 9 10 11 12 13

1↔13, 2↔12처럼 짝을 지어야 하기 때문에 뺄 수 있는 수는 맨 끝의 수 1, 13과 중간 수 7밖에 없다.

 

7. 마방진, 모든 수를 다 더하고 3으로 나눔

 

8. 해보면 된다.

 

9. a * b 크기의 맵에서 어떻게 가던 최단 경로로 간다면 → * a개, ↑ * b개 일수 밖에 없다. (어떤 경로로 가도 격자를 지나가는 횟수는 같다) (a+b) C a 콤비네이션 계산을 하거나 직접 세보는 방법이 있다. 중간에 점 C를 지난다면 시작 지점 A부터 C까지 경우의 수 + C부터 목적지 B까지 경우의 수 = 735개.

혹시 어느 부분을 가지 못하는 문제일 경우는 무조건 직접 세야함.

 

10. 한붓그리기 공식

 

11. 주어진 정수 중에 혼자 이상하게 큰 104를 뺀 나머지를 다 더하면 99가 나온다. 이 때문에 1부터 99까지의 정수는 다 만들 수 있다. 또 104가 있으니까 104부터 200까지의 정수를 다 만들 수 있다. 그러면 99부터 104 사이의 수를 못 만드는데, 거기를 메꾸는 수가 정답이다. 103-99=4.

 

12. 해보면 된다.

 

13. 다 해보면 알겠지만 2^k * 2^k면 배구수가 어디에 뚫려도 다 된다.

 

14. 구슬을 교환하면 또 줄 일이 없다. 즉 1번씩만 교환한다. 평균 구슬 15개를 맞추면서 교환하고 있는 줘야하는 구슬이 가지고 있는 구슬보다 커서 –n개가 돼도 상관없이 계산한다. 전부 한 번씩 교환하면 8번인데 평균 구슬 개수를 이미 가지고 있는 사람은 교환 안해도 되니까 분배작업은 총 7번.

 

15. 와인이 1000개기 때문에 처음에 쥐는 무조건 10마리가 있어야한다. (2^10)

그렇게 준비된 10마리의 쥐에 a부터 j까지 번호를 붙이고 1000병의 와인을 이진수로 표현하면 이렇게 된다.

 

          a  b c d e f g h i   j

병1      0 0 0 0 0 0 0 0 0 1

병2      0 0 0 0 0 0 0 0 1 0

병3      0 0 0 0 0 0 0 0 1 1

병4      0 0 0 0 0 0 0 1 0 0

...

병1000 1 1 1 1 1 0 1 0 0 0

 

그리고 a부터 j까지 모든 쥐를 세로로 내려오면서 와인을 먹이는데, 1인 부분만 먹고 0인 부분은 안 먹어도 된다. 병4까지를 예로 들자면 세로로 내려오면서 a는 하나도 마시지 않았고 j는 2번 마셨다. 이렇게 쭉 1000번째 병까지 먹인다. 그리고 30일 후, 저 중에서 몇 마리의 쥐는 죽을 것이다. 죽은 쥐는 1로 표시하고 안 죽은 쥐는 0으로 표시하면 하나의 이진수가 나오는데, 그 이진수에 해당하는 와인에 독이 들은 것이다.

하지만 문제에서는 와인이 아니라 희생되는 쥐의 최댓값을 찾아야 한다. 1이 제일 많이 나오는 999번째도 1111100111로 아무리 많이 죽어봤자 8마리가 최대라는 사실을 알 수 있다.