불쌍한 거인(UVA 10688)

Computer/Problems 2007/04/27 17:19

설명
탁자 위에, n개의 사과가 있다. i번째의 사과는 k+i의 무게를 가진다(1<=i<=n). 딱 하나의 사과만이 맛있고, 그보다 가벼운 사과들은 모두 쓰고, 그보다 무거운 사과들은 모두 시다. 거인은 어떤 사과가 맛있는지 알기 위해, 사과를 먹어보는 수밖에 없다. 그는 쓴 사과와 신 사과를 싫어한다. 그는 어떻게 해야 할까?

예를 들어, n=4, k=0일 때, 사과들의 무게는 각각 1, 2, 3, 4이다. 만약 거인이 사과#2를 먹는다면,
#2가 맛있으면 답은 #2이다.
#2가 시면 답은 #1이다.
#2가 쓰면 답은 #3이나 #4가 될 테고, 그는 #3을 먹어보고 답을 알게 될 것이다.
불쌍한 거인은 맛있는 사과가 무엇인지 알기 위해서 맛없는 사과들을 먹을 각오를 해야 한다. 모든 경우에 거인이 먹어야 되는 총 사과의 무게를 계산해주자.

위의 방법에 의하면,
#1이 맛있을 경우 : 2
#2가 맛있을 경우 : 2
#3이 맛있을 경우 : 2 + 3 = 5
#4가 맛있을 경우 : 2 + 3 = 5
고로 총 무게의 합은 2 + 2 + (2 + 3) + (2 + 3) = 14이다.

하지만 위의 방법은 최적이 아니다. 그가 사과#1을 먼저 먹어본다면, 그는 각 경우에 1, 3, 3, 3의 무게의 사과를 먹어야 하고, 총합은 14보다 작은 13이다.
각 경우에 최적의 방법으로 사과를 먹을 때, 거인이 먹게 되는 총 사과의 무게를 구하여라.

입력 형식
입력의 첫 줄에 정수 테스트 케이스의 개수를 의미하는 t가 들어온다.(1<=t<=100). 이어지는 t줄에는 각 줄에 n과 k가 주어진다.(1<=n+k<=500)

출력 형식
각 테스트 케이스에 대해서 거인이 먹어야 되는 가장 적은 양의 사과의 무게를 예제와 같은 형식으로 출력한다.

입력 예제
5
2 0
3 0
4 0
5 0
10 20

출력 예제
Case 1: 2
Case 2: 6
Case 3: 13
Case 4: 22
Case 5: 605




2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
Posted by Harry
TAG 10688, UVA, 거인, 사과, 프로그래밍
Trackback 0 , Comment 0

정육면체 칠하기(UVA 10733)

Computer/Problems 2007/04/26 08:53

설명
n종류의 페인트가 주어진다. 당신은 이 페인트들을 이용해서 정육면체를 칠해야 한다. 이 때, 서로 다른 방법으로 페인트를 칠하는 방법의 가지수를 구하여야 한다. 두 정육면체가 있을 때 한 정육면체를 돌려서 다른 정육면체와 같은 모양이 되지 못하면 두 정육면체는 다른 방법으로 칠해져 있다고 할 수 있다.

입력 형식
한 줄에 페인트의 종류 수를 나타내는 n(0<n<1000)이 하나씩 주어진다. 입력은 0으로 끝난다.

출력 형식
주어진 페인트의 종류로 정육면체를 칠할 수 있는 방법의 가지수를 출력한다.

입력 예제
1
2
0

출력 예제
1
10




2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
Posted by Harry
TAG 10733, UVA, 정육면체, 페인트, 프로그래밍
Trackback 0 , Comment 0

애너그램과 곱하기(UVA 10825)

Computer/Problems 2007/04/26 01:01

설명
N진수의 M자리 수 중에는 2, 3, ...M을 각각 곱해서 나온 결과가 처음 수의 애너그램인, 놀라운 수가 존재한다. 예를 들어 142857은 6자리의 10진수인데, 2, 3, ...6을 곱할 경우 다음과 같은 결과가 나온다.

2 x 142,857 = 285,714
3 x 142,857 = 428,571
4 x 142,857 = 571,428
5 x 142,857 = 714,285
6 x 142,857 = 857,142

M과 N이 주어졌을 때, 이러한 수를 찾아야 한다. 주어진 M, N에서 꼭 가능한 수가 나온다고 보장할 수 없다. 

입력 형식
입력은 최대 30줄로 이루어져 있다. 각 줄은 두 개의 정수 M(3<=M<=6)과 N(4<=N<=400)으로 되어 있다.
M=N=0일 경우 입력을 종료한다.

출력 형식
입력의 각 줄에 대해서 한 줄씩 출력한다. 각 줄에 M개의 정수를 출력하되, 각 정수는 공백으로 구분한다. 출력되는 모든 정수는 0과 N-1 사이의 수여야 한다. 이 정수들은 문제의 조건을 만족하는 N진수의 각 자리를 의미한다. 가장 왼 쪽에 가장 큰 자리수를 출력하며 오른쪽으로 갈수록 작은 자리의 수를 출력한다. 주어진 N, M에서 만족하는 수가 없을 경우 "Not found"를 출력한다.(따옴표 제외)

입력 예제
6 10
6 100
0 0

출력 예제
1 4 2 8 5 7
Not found.




2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
Posted by Harry
TAG 10825, anagram, mutiplication, UVA
Trackback 0 , Comment 0

Ocean Deep, make it shallow!(UVA 10176)

Computer/Problems 2007/04/26 00:45

설명

Ocean deep
I'm so afraid to show my feelings,
I have sailed a million ceilings
In my solitary room
Ocean deep

위는 클리프 리차드의 유명한 노래의 가사이다. 이 문제에서 당신은 비슷한 사람을 보게 된다. 그의 이름은 Rampell-Stilt-Skin이고, 중요한 것은 그는 죽었다는 것이다. 누군가가 며칠 전에 그를 죽였고, 당신은 그 미스테리를 풀어야 한다. 문제는 그는 그에 관한 모든 정보와 감정을 숨기려고 했다는 것이다. 그는 일기를 썼는데, 거기에는 몇 문장과 함께 엄청나게 큰 이진수가 있다. 만약 이 이진수가 큰 소수인 131071로 나누어진다면 같이 쓰여 있던 문장은 참인 문장이며, 그렇지 않으면 거짓이다. 이 문제에서 당신에게는 큰 이진수가 주어질 것이며 당신은 이 수가 131071로 나누어지는지 판별해야 한다. 알고리즘이 효율적이어야 문제를 해결할 수 있다.

입력 형식
입력은 1개 이상의 이진수로 이루어져 있다. 각각의 이진수는 한 줄씩을 차지하지만 길어지면 몇 줄을 차지할 수도 있다. 때문에 각 이진수끼리의 구별은 '#' 문자로 한다. 각각의 이진수는 100자리를 넘지 않는다.

출력 형식
각각의 이진수에 대해서 131071로 나누어지면 YES를, 나누어지지 않으면 NO를 출력한다.

입력 예제
0#
1010101#

출력 예제
YES
NO




2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
Posted by Harry
TAG 10176, Ocean Deep, UVA, 프로그래밍
Trackback 0 , Comment 0

피보나치 소수(UVA 10236)

Computer/Problems 2007/04/26 00:30

설명
피보나치 수열은 1, 1, 2, 3, 5, 8, 13... 과 같다. 수열에서, 맨 앞의 두 수를 제외한 모든 수는 그 이전에 있는 두 수를 더한 것과 같다. 피보나치 소수는 피보나치 수 중 약수에 자신을 제외한 피보나치 수가 없는 수를 의미한다. 첫 번째 피보나치 소수는 2이고, 두 번째는 3, 세 번째는 5, 네 번째는 13이다. N이 주어질 때, N번째 피보나치 소수를 출력하는 프로그램을 작성하여라. 단, 결과가 9자리를 넘을 경우 처음의 9자리만 출력한다.

입력 형식
입력은 여러 줄로 되어 있으며 EOF로 종료된다. 각 줄에는 N(0<N<=22000)이 주어진다.

출력 형식
문제에 맞는 결과값을 첫 9자리만 출력한다.

입력 예제
1
2
3

출력 예제
2
3
5




2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
Posted by Harry
TAG 10236, UVA, 소수, 프로그래밍, 피보나치
Trackback 0 , Comment 0

Test(UVA 10731)

Computer/Problems 2007/04/22 18:25
직업 선호도 테스트는 성격 테스트와는 다르게, 테스트를 받는 사람이 만족할 만한 직업을 찾는 것을 도와준다. 무의미해 보이는 5지선다형 질문으로 이루어진 이 테스트는, 그 사람의 성격에 가장 잘 맞는 직업을 골라준다. 질문은 다음과 같다.

Q. 다음 중 오후에 하고 싶은 일은 ?

(a) 닭에게 모이를 준다.
(b) 레이싱 카를 몬다.
(c) TV에서 심슨을 본다.
(d) 선탠을 한다.
(e) 개 집을 만든다.


각 질문은 참가자에게 다섯 가지 보기 중 가장 좋아하는 것을 고르도록 한다. 또한, 각 보기는 여러 질문에서 나타날 수 있다.

만약 참가자가 A, B, C, D, E의 보 기 중 A를 선택했다면, 이는 참가자가 각 B, C, D, E의 활동보다 A 를 좋아한다는 것을 의미한다. 또한 만약 참가자가 X를 Y보다 좋아하고, Y를 Z보다 좋아한다면 X를 Z 보다 좋아하는 것이 된다.

참가자는 모순되게 답을 할 수도 있다. 즉, 어떤 질문에서는 X가 Y 보다 좋다고 했다가, 다른 질문에 서는 Y가 X보다 좋다고 하는 것이 다. 이렇게 모순된 답을 제공하는 참가자는 정치가나 자동차 판매원 정도가 어울린다.(-_-)

직업 선호도 테스트에서 사용자가 쓴 답이 주어질 때, 당신은 이를 가장 적은 개수의 집합으로 나누어야 한다. 각 집합 안의 답들은 서로 모순되어야 한다.

입력은 0을 포함하는 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 질문의 개수를 나타내는 n으로 시작한다. 그 뒤에는 n줄이 오는데, 각 줄에는 다섯 개의 서로 다른 질문과 참가자가 쓴 답이 공백을 두고 주어진다.

각 보기와 답은 하나의 알파벳 대문자로 주어진다. 각 테스트 케이스에 대해서, 한 줄에 하나씩 나누어진 집합을 출력한 다. 하나의 집합 내에서는 원소들을 알파벳 순으로 정렬하고, 집합끼리는 각 집합에서의 가장 작은 원소를 기준으로 알파벳 순 정렬한 다. 각 테스트 케이스 사이에는 빈 줄을 출력한다.

입력 예제
4
A B C D E C
F C H I J J
K B H I F I
K C E B J K
0

출력 예제
A
B
C
D
E
F
H
I J K




2008년 1월 19일 이후 작성된 모든 글에 대해서 퍼가는 것을 금지합니다.
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
Posted by Harry
TAG ACM, UVA
Trackback 0 , Comment 0