Problem 99 : Broken Necklace
http://fitzsimmons.ca/beads.html


파란색과 빨간색의 구슬로 이루어진 목걸이가 있다.
목걸이를 특정 지점에서 끊어서, 끊어진 목걸이의 양쪽 끝에서
다른 색의 구슬을 발견할 때 까지 구슬의 개수를 세어나간다.
그렇게해서 얻을 수 있는 최대의 구슬 개수를 찾는 것이 목표이다.
흰색 구슬이 나올 수도 있는데 이 구슬은 원하는 색으로 칠할 수 있다.

풀이 방식 :
목걸이의 구슬별로 잘라서 Circular Doubly Linked List로 만들고,
For 문을 돌려 각 구슬 별로 돌아가면서 해당 구슬을 기준으로 삼아서 목걸이를 끊고,
모든 경우를 고려하였다.

by Raven the Revenger 2007. 7. 4. 20:10

Problem B : Digit Generator
http://acm.kaist.ac.kr/Problems/2005b.pdf

풀이

입력받은 수의 자리수만큼(216이면 3)
9를 곱한다음 입력수에 뺀다음
그 수부터 입력수까지 순환문을 돌리며 확인한다

각 자리수를 합하는건 대충 이런식?
for (i=ciphers-1; i>0; i--){
   result += (loop / (int)pow(10, i)) ;
   temp = (loop / (int)pow(10, i)) ;
   loop = loop - temp*(int)pow(10, i);
}
이런식의 계산법은 다들 외워두면 좋을듯
더 나은방법 있으면 알려주고!

소스 :

by 잭크 2007. 7. 4. 19:48
Programming Contest Problem Types

Hal Burch conducted an analysis over spring break of 1999 and made an amazing discovery: there are only 16 types of programming contest problems! Furthermore, the top several comprise almost 80% of the problems seen at the IOI. Here they are:

  • Dynamic Programming
  • Greedy
  • Complete Search
  • Flood Fill
  • Shortest Path
  • Recursive Search Techniques
  • Minimum Spanning Tree
  • Knapsack
  • Computational Geometry
  • Network Flow
  • Eulerian Path
  • Two-Dimensional Convex Hull
  • BigNums
  • Heuristic Search
  • Approximate Search
  • Ad Hoc Problems
by 잭크 2007. 7. 2. 16:11

김용혁 교수님께서 알려주신 USACO
첫문제 통과!
문제풀이보다
봇 돌려본데 의의를 둬봤음

by 잭크 2007. 7. 2. 16:09

저희 ACM팀( 장지용(03), 최홍준(07), 김형석(07) ) 스프링노트 주소입니다.

http://temjin4.springnote.com/

딱히 ACM스프링노트 주소만 골라내는 법을 몰라서 제 계정 스프링노트 주소로 적어둡니다.

by 비회원 2007. 7. 2. 10:38

Googling 하다가 찾은 포스트입니다.
평소 궁금했던 부분에 대한 이야기들이 오가네요.
참고해서 패널티 받는 일이 없도록 합시다.

http://acm.kaist.ac.kr/forum/viewtopic.php?p=1413&highlight=&sid=a5d73086c564044fd0adb82ad278caa9#1413

by RyuiSaka 2007. 7. 1. 21:22
  • 잭크 2007.07.02 01:20 신고 ADDR EDIT/DEL REPLY

    패널티나 예외처리에 관한 글이네...
    한번 봇 돌리면서 해봐야지.. 뭔가 명쾌한 답이 나올꺼 같네..
    내일 교수님 찾아뵙고 나서 SoC소스 분석 시간 제외하고 ACM이나 풀까?

ACM ICPC 멤버들과 SoC Robot War 멤버들


첫 모임이 금주 일요일 2007. 7. 1(일) 날 있을 예정입니다.


간단한 스터디 진행방향과 대회준비 계획 등을 상의할 예정이니


14:00시 동아리방으로 모여주시기 바랍니다.



* 진행방법에 대한 각자의 의견도 생각해 오시기 바랍니다.

by 잭크 2007. 6. 29. 14:38
문제링크 : http://acm.kaist.ac.kr/Problems/2003oc.pdf
ACM-ICPC 2003년 온라인예선 C번



-----------------------------------------------------------
뭐 풀이는 테스트 케이스에서는 문제 없이 돌아가지만 어떤 예외상황에선
문제가 있을지도..;;

먼저
BEER와 DRINK를 예로 들자면
어제 고민 했을때처럼 알파벳 순으로 숫자를 표기하고(어짜피 아스키값으로 비교할꺼기 때문에..)

먼저 BEER같은경우 1223, DRINK는 15243로 번호를 매긴다
그리고 뒤에서부터 한자리씩 비교
15243과 15243 비교!
뒷자리가 작으므로 패스
다시 15243과 15243을 비교
뒷자리가 크다!
그러면 이제 여기서 STOP
4의 앞자리인 2와, 4의 뒷자리에 있는 모든 수를 비교한다
지금은 3밖에 없으므로 일단 3과 비교
(만약 뒤로 수가 많다면 2보다 큰 수 중에 가장 작은수랑 바꾸야 한다)
3이 크다 그러면 이제 3과 2의 자리를 바꾼다
그러면15342
하지만 여기서 끝이 아니다
가운데 자리(처음에 2가 있었던 자리 뒷부분) 뒤쪽으로는
오름차순 정렬!(버블소트든 퀵소트든 상관없음)
그러면 15324 <-이런식으로 바꾸면 DRKIN 정답!
그럼 끝 BEER같이 뒷자리 R뒤에 숫자가 없거나 E보다 큰수가 없으면 그냥
R과 E 자리만 바꾸면 된다

소스코드 :


by 잭크 2007. 6. 26. 00:25
| 1 2 |