천상낙원

빛, 더 많은 빛 (Light, More Light)

ACM 퀴즈


우리 학교에는 복도 불을 켜고 끄는 마부라는 사람이 있다. 전구마다 불을 켜고 끄는 스위치가 있다. 불이 꺼져 있을 때 스위치를 누르면 불이 켜지고 다시 스위치를 누르면 불이 꺼진다. 처음에는 모든 전구가 꺼져 있다.

마부라는 사람은 특이한 행동을 한다. 복도에 n개의 전구가 있으면, 복도를 n번 왕복한다. i번째 갈때 그는 i로 나누어 떨어지는 위치에 있는 스위치만 누른다. 처음 위치로 돌아올 때는 아무 스위치도 건드리지 않는다. i번째 왕복은 복도를 한 번 갔다가 오는 것으로 정의된다. 마지막 전구의 최종 상태를 알아내자. 관연 그 전구는 켜져 있을까 아니면 꺼져 있을까?


입력
복도에 있는 n번째 전구를 나타내는 232-1이하의 정수가 입력된다. 0은 입력의 끝을 의미하며 그 값은 처리하지 않는다.

출력
그 전구가 켜져 있으면 "yes"를, 꺼져 있으면 "no"를 출력한다. 테스트 케이스마다 한 줄에 하나씩 출력한다.

입력예
3
6241
8191
0

출력예
no
yes
no

참고사항
1. 약수의 갯수가 홀수이면 전구가 켜지게 됩니다. 그러므로 n이 어떤 정수의 제곱이 되는지만 확인하면 됩니다.
2. 도데체 어떤 문제가 있어서 PE가 나오는지 모르겠습니다.

'ACM 퀴즈' 카테고리의 다른 글

작은 비숍 (Little Bishops)  (0) 2006.02.22
피보나치 수의 개수 (How many Fibs?)  (0) 2006.02.05
자리올림 (Primary Arithmetic)  (0) 2006.01.19

피보나치 수의 개수 (How many Fibs?)

ACM 퀴즈


피보나치 수는 다음과 같은 식으로 정의된다.

f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2) (n≥3)

a와 b라는 수가 주어졌을 때 [a, b] 구간에 있는 피보나치 수의 개수를 계산하라.


입력
입력에는 여러 개의 테스트 케이스가 들어있다. 각 테스트 케이스는 두 개의 음이 아닌 정수 a와 b가 입력될 때 앞부분에 불필요한 0은 전혀 붙지 않는다.

출력
각 테스트 케이스마다 a≤f(i)≤b인 피보나치 수 f(i)의 개수를 한 줄에 하나씩 출력한다.

입력예
10 100
1234567890 9876543210
0 0

출력예
5
4

'ACM 퀴즈' 카테고리의 다른 글

빛, 더 많은 빛 (Light, More Light)  (0) 2006.02.05
자리올림 (Primary Arithmetic)  (0) 2006.01.19
비토와 친척들 (Vito's family)  (0) 2006.01.14

배차 관리 시스템 (Marshalling of Cars)

DoItMyself
작년에 만들었던 배차관리 시스템입니다.
솔직히 맘에 들지도 않을뿐더러 버그 투성이라 사용할 수도 없습니다-_-;;
또한 IE에서만 정상적으로 작동합니다-_-;;
최근 버젼을 어디에 둔건지.. 사라져버렸습니다. OTL..
시간을 두고 서서히 발로 짠 소스를 곱씹어 보며 고쳐봐야 겠습니다.
아래는 개발 전에 제출했던 계획서입니다.


1. Marshalling of Cars 개발 계획

아이템 명 Marshalling of Cars

아이템 개요
복잡한 화물 업무를 손쉽게 전산화시킬 수 있는 프로그램입니다. 한 번의 배차일보 등록으로 다양한 기능을 통해 많은 자료를 한꺼번에 관리할 수 있습니다. 또한 간단한 회계 입력으로 차량별 경비내역과 급여 지급 내역 등의 각종 회계 자료를 담당자가 없이도 손쉽게 관리할 수 있습니다. Marshalling of Cars는 고객 관리, 일정 관리, 견적서 관리, 등 화물 업무에 필요한 각 기능들을 포함합니다.

사업 전망
기존의 프로그램은 단일 컴퓨터에서의 작동으로 인해 다수의 사용자가 사용하기에는 어려움이 많고 데이터의 효율적인 관리가 힘들었으나, 인터넷을 통한 관리로 편리하고 효율적인 관리가 가능하게 되었습니다.
본사는 물론 지사에서 입력된 데이터를 데이터베이스화하여 본사에서 신속하고 효율적으로 운영할 수 있도록 설계되었습니다. 또한 사무실은 물론 퇴근 후 가정에서도 24시간 업무를 볼 수 있습니다. 원가 절감, 생산성 향상, 납기일 준수, 관리 시스템의 표준화 등의 이점을 갖게 됩니다.

개발 목표
ㆍ프로그램을 설치하지 않고 사용이 가능한 실시간 네트워크(웹) 프로그램
ㆍ본사, 자사의 구분 없이 같은 자료를 같은 시간대에 접속, 관리
ㆍ인터넷 환경만 갖추어져 있으면 사용가능

2. Marshalling of Cars 주요 기능

배차 관리
ㆍ운송 일보 등록
- 각 항목별로 쉬운 입력 폼
- 운송차량 선택에 따른 기사이름, 차종 자동입력
ㆍ운송 일보 조회
- 각 항목별로 배차내역 조회
- 원하는 항목만으로 조회 가능운송 현황ㆍ거래처별

운송 현황
ㆍ거래처별 운송 현황
- 모든 거래처, 각 거래처별 운송 현황 조회
- 중량, 매입금액, 매출금액, 손익 계산
ㆍ차량별 운송 현황
- 모든 차량, 각 차량별 운송 현황 조회
- 중량, 매입금액, 매출금액, 손익 계산
ㆍ착지별 운송 현황
- 모든 하차지, 각 하차지별 운송 현황 조회
- 중량, 매입금액, 매출금액, 손익 계산

통계 분석
ㆍ거래처별 통계 분석
- 거래처별 매입금액, 매출금액, 중량의 최고값, 최처값, 총합, 평균값을 계산
ㆍ차량별 통계 분석
- 차량별 매입금액, 매출금액, 중량의 최고값, 최처값, 총합, 평균값을 계산
ㆍ착지별 통계 분석
- 거래처별 매입금액, 매출금액, 중량의 최고값, 최처값, 총합, 평균값을 계산

거래처 관리
ㆍ거래처(화주) 관리
- 거래처 정보 입력, 수정, 삭제
ㆍ기사 관리
- 기사 정보 입력, 수정, 삭제

청구 관리
ㆍ거래처별 청구 관리
- 각 거래처별로 청구서 확인 / 조회
- 청구서 인쇄 지원

3. 필요한 기자재 및 장비

데이터베이스
ㆍMySQL

사용 언어
ㆍPHP
ㆍHTML
ㆍJava Script

사용 도구
ㆍEdit Plus
ㆍDreamweaver




'DoItMyself' 카테고리의 다른 글

영상처리를 이용한 악보 인식  (6) 2007.02.12
GML을 이용한 지도 서비스  (3) 2006.08.16
모의 수강신청  (0) 2006.02.14

자리올림 (Primary Arithmetic)

ACM 퀴즈


초등학생들이 여러 자리 수의 덧셈을 배울 때는 한번에 한 자리씩 오른쪽에서 왼쪽으로 계산하도록 배운다. 그런데 그 자리 숫자의 합이 10을 넘어갈 때 윗자리 숫자에 1을 더해주는 것을 배울 때 많은 학생들이 힘들어한다. 일련의 덧셈 문제가 주어졌을 때 자리를 올리는 횟수를 세어서 선생님들이 학생을 가르치는데 도움을 줄 수 있는 프로그램을 만들어야 한다.


입력
각 행에는 열자리 미만의 부호가 없는 정수가 두개씩 입력된다. 마지막 줄에는 '0 0' 이 입력된다.

출력
마지막 줄을 제외한 각 줄에 대해 주어진 두 수를 더할 때 자리를 올려야 하는 횟수를 계산한 다음 아래에 주어진 형식대로 결과를 출력한다.

입력 예
123 456
555 555
123 594
0 0

출력 예
No carry operation.
3 carry operations.
1 carry operation.

참고사항
1. 각 자리수의 합에서 carry가 발생하는지 확인한다.
2. 자리수의 합을 구할 때 carry 또한 더해준다.
3. 둘중에 큰 수의 자리수까지 반복한다. (carry가 더해지므로 계속하여 carry가 발생할 수도 있다.)
4. 두개 이상이면 s를 뒤에 붙여줘야 함에 주의한다.

'ACM 퀴즈' 카테고리의 다른 글

피보나치 수의 개수 (How many Fibs?)  (0) 2006.02.05
비토와 친척들 (Vito's family)  (0) 2006.01.14
WERTYU  (0) 2006.01.13

비토와 친척들 (Vito's family)

ACM 퀴즈


유명한 갱스터인 비토 데드스톤이 뉴욕으로 이사를 간다. 뉴욕에는 그의 가족들이 매우 많이 살고 있는데 그들은 모두 라마피아 거리에 살고 있다. 그는 친척들을 자주 만나러 갈 계획이기 때문에 친척들과 가까운 곳에 집을 구하기로 했다.

비토는 모든 친척집과의 거리 총합이 가장 작은 곳에 집을 구하고 싶어하는데, 하필이면 당신에게 그 문제를 해결하기 위한 프로그램을 만들어내라는 협박 편지를 보내왔다.


입력
입력은 여러 개의 테스트 케이스로 구성된다. 첫번째 줄에는 테스트 케이스의 개수가 들어있다. 각 테스트 케이스마다 친척집의 수를 나타내는 정수 r(0 < r < 500)과 각 친척집의 번지수를 나타내는 정수 s1, s2, ..., si, ... sr(0 < si < 30,000)이 입력된다. 친척 중에는 같은 번지에 살고 있는 사람들도 있다는 점에 주의하자.

출력
각 테스트 케이스에 대해 비토가 원하는 위치에 집을 구했을 경우에 그 집으로부터 각 친척집까지의 거리의 총합을 출력해야 한다. 번지 수가 si와 sj인 두 집 사이의 거리는 dij = | si - sj |로 구한다.

입력 예
2
2 2 4
3 2 4 6

출력 예
2
4

참고사항
1. 두 친척집 사이에 비토의 집이 있다면 거리의 총합은 동일하다. 또한 최소값을 갖는다.
2. 같은 번지에 살고 있는 사람들도 각각 거리를 구해 더해주어야한다.

'ACM 퀴즈' 카테고리의 다른 글

자리올림 (Primary Arithmetic)  (0) 2006.01.19
WERTYU  (0) 2006.01.13
유쾌한 점퍼 (Jolly jumpers)  (2) 2006.01.12

WERTYU

ACM 퀴즈



타이핑을 하다보면 키보드에서 양손을 모두 원래 위치보다 오른쪽으로 한 칸 이동한 상태에서 키를 눌러서 오타가 나오는 경우가 종종 있다. 그러면 'Q'는 'W', 'J'는 'K' 같은 식으로 오른쪽에 있는 키가 입력된다. 이런 식으로 입력된 메시지가 주어졌을 때 원래 메시지로 복구시켜야 하는 임무가 주어졌다.


입력
입력은 여러 줄의 텍스트로 구성된다. 각 줄에는 숫자, 스페이스, 대문자('Q', 'A', 'Z' 제외), 위에 나와있는 구두 기호(역따옴표(`)제외)가 들어갈 수 있다. 단어가 붙어있는 키(Tab, BackSp, Control 등)는 입력에 들어있지 않다.

출력
위에 나와있는 QWERTY 키보드를 기준으로 하여 각 글자나 기호를 바로 왼쪽에 있는 키에 해당하는 글자나 기호로 바꿔야 한다. 입력에 있는 스페이스는 그대로 둔다.

입력예
O S, GOMR YPFSU/

출력예
I AM FINE TODAY.

참고사항
1. 시간초과에 유의한다.

'ACM 퀴즈' 카테고리의 다른 글

비토와 친척들 (Vito's family)  (0) 2006.01.14
유쾌한 점퍼 (Jolly jumpers)  (2) 2006.01.12
The 3n + 1 problem  (7) 2006.01.12

유쾌한 점퍼 (Jolly jumpers)

ACM 퀴즈


n>0인 정수의 수열에서 앞, 뒤 수의 차이의 절대값들이 1에서 n-1까지의 가능한 모든 값을 가진다면 jolly jumper라 한다. 다음의 예를 보자.

1 4 2 3
위 예는 차의 절대값이 3, 2, 1을 가지기 때문에 jolly jumper이다. 정수 하나일 경우도 jolly jumper라 정한다. 수열이 jolly jumper인지 확인하는 프로그램을 작성하라.


입력
각 라인은 맨 앞에 3000 미만의 정수 n이 적혀있고, 그 뒤로 n개의 정수가 나온다.

출력
각 input에 따라 'Jolly' 또는 'Not jolly'를 출력한다.

입력 예
4 1 4 2 3
5 1 4 2 -1 6

출력 예
Jolly
Not jolly

참고사항
1. 입력 수열에서 첫 수는 몇개의 정수를 입력받을지를 의미한다.
2. 차의 절대값은 반드시 정렬되어 있어야한다?!?
4 1 4 2 3의 경우 차의 절대값은 3, 2, 1이 된다.
4 1 3 6 5의 경우 차의 절대값은 2, 3, 1이 된다.
사이트에서는 두 경우 모두 solved를 보여준다. 어찌 된 것인가?

'ACM 퀴즈' 카테고리의 다른 글

WERTYU  (0) 2006.01.13
The 3n + 1 problem  (7) 2006.01.12
프로그래밍 문제 풀이 (Programming Challenges)  (0) 2006.01.12

The 3n + 1 problem

ACM 퀴즈


다음과 같은 수열을 생성하는 알고리즘을 생각해보자. 정수 n부터 시작한다. n이 짝수이면 1을 곱하고, 홀수이면 3을 곱하고 1을 더한다. 이 과정을 n=1이 될때까지 반복한다. 예를 들어, n=22이면 다음과 같은 수열을 생성한다.

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

이 알고리즘은 모든 정수에서 n=1이 되어 종료될 것으로 추측된다.(아직 증명되지는 않았다.)

입력 n에 대해서 n의 cycle-length는 1을 포함하여 생성된 수의 개수이다. 위의 예에서 22의 cycle-length는 16이다. 두 수 i와 j가 주어지면 i와 j사이의 모든 수의 cycle-length 중 가장 큰 값을 구한다.


입력
한 줄에 i와 j가 연속하여 입력된다. i와 j는 1,000,000보다 작고 0보다 크다.

출력
입력된 정수쌍 i, j (입력된 순서대로) 그리고 가장 큰 cycle-length를 출력한다. 이 세 숫자는 스페이스 한칸으로 구분한다.

Sample Input
1 10
100 200
201 210
900 1000

Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

참고사항 (제가 어려움을 겪었던 사항입니다)

1. 입력은 한번만 받고 끝나는 것이 아니라 계속 입력 받도록 합니다.

2. 계속 입력을 받을 때 최대 cycle length를 초기화 해줘야 함에 주의합니다.

3. 큰 수가 먼저 입력되는 경우를 고려해야 합니다. 작은 수 먼저 입력으로 들어오리란 보장은 없습니다. 입력 예에 한정해서 생각하면 안되죠.

4. 마지막으로 수열은 int형의 범위를 넘어설 수 있다는 것을 고려해야 합니다. 수열을 int형 범위로 제한하면 1 999999 결과로 1 999999 476 출력됩니다. 그러나 unsigned int형 범위로 제한하면 1 999999 결과로 1 999999 525 출력됩니다. 이러한 현상은 원인은 다음과 같습니다. 최대 값이 나오는 수는 837799인데 int형으로 하면 59가 나옵니다. 어느 순간 값이 2974984576이 되는데 이것이 int형(32비트)의 경우 범위를 넘어서서 -1319982720 이 되버리는 결과를 초래합니다. 그래서 반드시 unsigned int로 해주어야 제대로 된 값이 나옵니다. 어이 없는건 submit에는 문제가 없다는 겁니다-_-;;

'ACM 퀴즈' 카테고리의 다른 글

WERTYU  (0) 2006.01.13
유쾌한 점퍼 (Jolly jumpers)  (2) 2006.01.12
프로그래밍 문제 풀이 (Programming Challenges)  (0) 2006.01.12