[잡담] 3/27 제 19회 '대전올림피아드' 결과 (저는 망했군요.)

글쓴이: cppig1995 / 작성시간: 목, 2008/04/03 - 5:37오후

중등부 문제들입니다. 저는 8등으로 세 단계 밀렸군요. 역시 요즘 자주 듣는 컴퓨터수학(전산수학)의 중요성을 뼈저리게 느끼는 중입니다.
그나저나 주최한 대전교육정보원 측에서는 엄청난 크기로 수험실마다 '제19회 대전올림피아드'라고 써진 인쇄물을 붙여놨던데 부끄럽지도 않나.
실제 시험에서는 INPUT.TXT에서 입력, OUTPUT.TXT로 출력하며, VC++ 6 또는 VB 6을 선택 사용합니다.

[문제 1] N!을 B진수로 나타냈을 때 끝에 연속하여 붙는 0의 개수를 구하라.
* N은 10억 이하의 자연수, B는 2 이상 10만 이하의 자연수이다.
[문제 2] 다각형을 이루는 점들과 테스트할 점 5개를 입력받아 안/밖 여부를 구하라.
* 점은 다각형의 변 위에 있을 수 없다, 출력은 한 줄에 IN 또는 OUT.
[문제 3] 여러 경시대회의 시작 시간, 끝 시간, 수상 확률을 입력받아 수상 확률의 총합이 가장 높도록 겹치지 않게 대회를 편성하라.
* 대회는 종료 시간 전에 끝나므로, 15에 끝나는 대회와 15에 시작하는 대회는 동시에 참가 가능함.

-- 여기서부터 해결에 관한 잡담, 진지하게 푸실 분들은 Page Down / 별 상관 없긴 합니다만... --

참고로 저는 각각 17점, 10점, 10점을 받았는데 만점은 잘 모르겠군요.
문제 2번은 전날 한 시간 반 동안 읽은 에 나오는 방법을 그대로 썼는데.
문제 3번은 "15에 끝나는 대회와 15에 시작하는 대회는 동시에 참가 가능함."에 대한 처리를 빼먹은 것 같습니다.
문제 1번은 계속 나눠가면서 구했습니다. 이해하시겠죠?
조금 있다가 시험장에서 푼 것과 똑같은 접근방식의 해를 올려보겠습니다. 질타해 주세요. ^^

* SMPlayer 한국어 번역 작업을 미뤄서 죄송하구요. 0.6.0rc4가 SVN r106x쯤 될 것 같으니 최대한 빨리 끝내서 여기에 올리겠습니다.

Forums:

자유 게시판

1번 N!을 계산하고

글쓴이: 시지프스 / 작성시간: 목, 2008/04/03 - 10:27오후

1번 N!을 계산하고 그걸 다시 B로 계속 나눴다는 말은 아니죠? 그냥 N 가지고 처리한 거죠?

begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}

제한 시간내에 문제

글쓴이: 체스맨 / 작성시간: 목, 2008/04/03 - 10:33오후

제한 시간내에 문제 풀기를 별로 좋아하질 않는 편이지만, 2번 문제 같은 경우는 좀 아는 분야의 문제군요. 그리고, 가장 실용적인 문제처럼 보이네요. :-)

제가 아는 건 크게 두가지 방법이 있는데, 주어진 점과 꼭지점이 이루는 각도들의 합으로 구하는 방법, 또는 임의 방향으로 선을 그었을 때 교차점의 갯수로 판별하는 법이 있고, 두번째 방법은 여러 최적화 방법이 존재합니다. 수학자들은 처음 방법을 좋아하고 엔지니어들은 두번째 방법을 좋아하죠. 특히 두번째 방법은 공간상의 입체에도 적용 가능합니다.

캐드 분야에 자주 사용되는 기본 알고리즘 중 하나죠. 위 두가지 방법 말고, 다른 방법으로 푸셨나요? 제가 만든 솔리드 모델러 ( http://www.megapass.co.kr/~heesc22/orion/ima/h_imaml.htm ) 도 있는데 지겹도록 자주 필요한 알고리즘 중 하나입니다.

Orion Project : http://orionids.org