태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          

Notice


스도쿠
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5294 Accepted: 1578

설명

스도쿠에서는 9 × 9 크기의 격자가 3 × 3 크기의 더 작은 격자들로 나뉘어져있습니다. 예를 들면,

. 2 7 3 8 . . 1 .
. 1 . . . 6 7 3 5
. . . . . . . 2 9
3 . 5 6 9 2 . 8 .
. . . . . . . . .
. 6 . 1 7 4 5 . 3
6 4 . . . . . . .
9 5 1 8 . . . 7 .
. 8 . . 6 5 3 4 .

격자 안에 몇몇개의 숫자가 주어졌을 때,  당신은 남은 칸들에 1부터 9까지의 숫자들을 집어넣어야 하는데 이때 1부터 9까지의 각 숫자들은 (1) 9개의 3 × 3 격자 안에 1개씩, (2) 9개의 가로 줄 안에 1개씩, (3) 9개의 세로 줄 안에 1개씩 들어가야 합니다.

입력

테스트 파일의 입력은 복수의 테스트 케이스들로 구성될 수 있습니다. 각 테스트 케이스는 81개의 문자를 한 줄로 나타내는데 이것은 스도쿠 격자의 81개의 칸을 나타내며, 위에서부터 가로 한 줄씩 표기합니다. 각 문자는 1부터 9까지의 숫자 혹은 채워지지 않은 칸을 나타내는 점으로 나타냅니다. 입력된 스도쿠에 대해 단 하나의 정답만이 존재한다는 것을 명심하세요. 파일의 끝을 표기할 때는 한 줄에 “end” 라고 입력하시면 됩니다.

출력

각 테스트 케이스에 대해, 완성된 스도쿠 퍼즐을 한 줄로 출력하시면 됩니다.

입력 예시

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

출력 예시

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3074. Sudoku  (2) 2011.04.18
PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
posted by Sparking

댓글을 달아 주세요

  1. ㅋㅋㅋㅋㅋㅋ 간만에 큰거 하나 물어왔네

  2. 이거 뭔가 머리속만으로 굴리는건 진짜 한계가 있는데? ㅋㅋㅋㅋ

흑백 채색
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2092 Accepted: 1396

설명

당신은 현대 그림이 많이 전시되어 있는 Centre Pompidou 를 방문중입니다. 특히 당신은 마치 체스판처럼 오로지 검은색과 흰색의 사각형들로만 이루어진 한 그림을 주목합니다 (맞닿은 사각형들은 같은 색이 아닙니다). 그런데 이 그림을 그린 화가는 그림을 그릴 때 problem A 의 도구를 사용하지 않았습니다.

너무도 심심했던 당신은, 이 작품 속에 얼마나 많은  8 × 8 크기의 체스판이 들어갈 수 있는지 알고 싶어졌습니다. 체스판의 오른쪽 제일 아래칸은 반드시 흰 색이어야 합니다.

입력

입력은 여러 개의 테스트 케이스들로 이루어집니다. 각 테스트 케이스들은 한 줄에 세 개의 정수  n, m 그리고 c. 를 포함하는데(8 ≤ n, m ≤ 40000), n 은 그림의 가로줄의 수를, m 은 그림의 세로줄의 수를 의미합니다. c 는 언제나 0 또는 1인데, 0은 오른쪽 제일 아래칸이 검은색인걸 의미하고 1은 오른쪽 제일 아래칸이 흰색인걸 의미합니다.

입력의 마지막을 의미하는 테스트 케이스에는 3 개의 0을 입력합니다.

출력

각 테스트 케이스에 대해서 얼마나 많은 체스판이 주어진 그림의 크기에 들어갈 수 있는지를 출력하면 됩니다.

입력 예시

8 8 0
8 8 1
9 9 1
40000 39999 0
0 0 0

출력 예시

0
1
2
799700028

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3074. Sudoku  (2) 2011.04.18
PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
posted by Sparking

댓글을 달아 주세요

  1. 규칙이 분명 있을터인듸

628 - Passwords

Time limit: 3.000 seconds

여러 서버에 여러개의 계정을 둔 사람은 당연히 여러 가지의 비밀번호를 기억해야 합니다. 그리고 어떤 사람이 비밀번호를 잊어버린 상황을 충분히 상상할 수 있을겁니다. 그/그녀 가 기억하고 있는 것은 오직 단어 x, y 그리고 z 와 두 개의 숫자입니다: 하나는 시작하는 숫자이고 다른 하나는 끝나는 숫자입니다.


당신은 이제 주어진 단어와 규칙을 기반으로 하여 비밀번호의 가능성이 있는 모든 것을 찾아내는 프로그램을 작성해야 합니다. 예를 들어 주어진 3 개의 단어:
x, y, z 와 주어진 규칙이 0#0 라면, 이 규칙은 <숫자><사전식 단어><숫자> 의 형태로 나타나야 합니다.

입력 

첫 번째 줄은 사전에 있는 단어들의 숫자를 나타냅니다(n). 각 단어들은 n 개의 연속적인 줄로 나타냅니다. 그 다음 줄은 규칙의 개수를 나타냅니다(m). 비슷하게, 각 규칙 역시 m 개의 연속적인 줄로 나타냅니다. 각 규칙에는 특수문자 `#' 와 `0' 가 임의로 나오게 됩니다. 특수문자 `#' 는 사전상의 단어를 나타내며 특수문자 `0' 는 숫자를 나타냅니다.

입력할 데이터는 여러 개의 사전식 단어들과 거기에 따른 규칙들을 포함합니다.

출력 

각 경우의 '사전 + 규칙' 에 따라 2개의 하이픈으로 구분되도록 선을 긋고, 그 뒤에 가능성이 있는 모든 비밀번호들을 연속적인 줄 형식으로 나타나도록 출력합니다. 이 때, 규칙이 여러개 있는 경우엔 첫번째 규칙에 대해 분류된 비밀번호들을 전부 나열한 후 두번째 규칙에 대해 분류된 비밀번호들을 전부 나열하는, 규칙의 순서에 따라 정렬시켜야 합니다. 또한 단어과 규칙에 따라 정렬할 때 숫자가 포함된다면, 반드시 오름차순으로 정렬시켜야 합니다.


가정: 사전에 있는 단어의 수는 0 보다 크고 100보단 작거나 같습니다 ( $0 < n \le 100$). 단어의 길이는 0 보다 크고 256 보단 작습니다. 단어들은 `
A'..`Z',`a'..`z',`0'..`9' 과 같은 문자들을 모두 포함할 수 있습니다. 규칙의 개수는 1000 보다 작으며, 규칙은 256 개의 문자보다 짧습니다. 문자 `0' 는 규칙에 있어서 7번 이상 나오지 않지만, 최소한 1번은 나와야만 합니다. 문자 `#' 는 필수적이지 않기 때문에 규칙에 꼭 나와야 할 필요는 없습니다.

입력 예시 

2
root
2super
1
#0
1
admin
1
#0#

출력 예시 

--
root0
root1
root2
root3
root4
root5
root6
root7
root8
root9
2super0
2super1
2super2
2super3
2super4
2super5
2super6
2super7
2super8
2super9
--
admin0admin
admin1admin
admin2admin
admin3admin
admin4admin
admin5admin
admin6admin
admin7admin
admin8admin
admin9admin

 


Miguel A. Revilla
2000-01-10

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3074. Sudoku  (2) 2011.04.18
PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
posted by Sparking

댓글을 달아 주세요

  1. 뭔가 쉬우면서도 구현하기 어렵다? -_-;; 내 대가리가 굳어서 그런가

  2. 아니여. 문제 풀이 과정이 묘해서 그래. 쉽긴 쉬운데 구현하기 뭔가 더러운 느낌?

  3. UVA 비번 까뭇따 ㄱ-

서로 다른 두 소수의 합
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 2398 Accepted: 1474

설명

어떤 양정수는 한 가지 이상의 서로 다른 소수들의 합으로 나타낼 수 있습니다. 주어진 두 개의 양정수 n 과 k 를 놓고 볼 때, 당신은 n 이라는 양정수를 k 개의 서로 다른 소수들의 합으로 나타내는 방법을 찾아내야 합니다. 다음에 나오는 예시를 보면 확실하겠지만, 같은 소수 집합으로 합의 순서만 바꾸는 것은 같은 방법을 썼다고 간주합니다. 예를 들어 8 은 3 + 5 와 5 + 3 으로 표현 될 수 있지만 이 두 방법은 구별할 수 없기 때문에 하나의 방법입니다.

만약 n 과 k 가 각각 24 와 3 이라면 답은 2가 되는데 그 이유는 {2, 3, 19} 라는 소수집합과 {2, 5, 17} 라는 소수집합, 이 두 집합의 원소들의 합이 24로 같기 때문입니다. 그리고 이 두 집합의 원소들을 제외한 다른 세 개의 소수들의 합으론 24를 만들 수 없습니다. 예를 들어 n = 24 와 k = 2,가 주어졌다면 답은 3개가 되는데 그 이유는 세 개의 집합 {5, 19}, {7, 17} 그리고 {11, 13} 이 있기 때문입니다. 또 n = 2 와 k = 1,이 주어졌다면 답은 1이 되는데 그 이유는 단 하나의 집합{2} 만 이 합이 가능하기 때문입니다. 한편 n = 1 이고 k = 1,이면 답은 0 이 됩니다. 1 은 소수가 아니기 때문에 이런 방식으로 셀 수 없기 때문이지요. 그리고 n = 4 이고 k = 2,라면 그 역시 답이 0이 되는데, 그 이유는 서로 다른 두 개의 소수의 합으로 4를 나타낼 수 없기 때문에 그렇습니다.

주어진 n 과 k 에 대해서 위와 같은 방식으로 답을 찾는 프로그램을 작성하는 것이 당신이 해야 할 일입니다.

입력

입력할 때 데이터셋은 하나의 줄에 두 개의 양정수 n 과 k 를 포함하는데, 이 두 수 사이에는 공백을 두어 입력합니다. 이 때  n ≤ 1120 까지, 그리고 k ≤ 14 까지 가능합니다. 입력을 종료할 때는 두 양정수의 위치에 0 을 각각 넣어서 종료합니다.

출력

입력된 각 데이터셋에 대해서 연관된 한 줄로 출력합니다. 출력할때는 하나의 음이 아닌 정수를 내보내는데, 이 정수는 입력에서 주어진 두 양정수 n 과 k 를 놓고 표현 가능한 방법의 가지수를 나타냅니다. 출력하는 값은 231 보다 작습니다.

입력 예시

24 3 
24 2 
2 1 
1 1 
4 2 
18 3 
17 1 
17 3 
17 4 
100 5 
1000 10 
1120 14 
0 0

출력 예시

2 
3 
1 
0 
0 
2 
1 
0 
1 
55 
200102899 
2079324314

Source

Japan 2006

p.s: 입력 부분 해석이 저만 이상한가요? 일단 문제에 맞게 해석해서 올려봅니다.. Lonewolf dlbo의 조언을 통해 의문을 해결하였습니다.(-)

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
posted by Sparking

댓글을 달아 주세요

  1. 시망 문제 난이도 좆망인데

  2. 하나하나 다 쑤셔넣어서는 가망이 없구먼 ㄱ-

썩은 밧줄
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4023 Accepted: 2620

설명

어떤 무거운 물체를 들어올리기 위해서 같은 길이인 n 개의 밧줄이 있다고 생각해봅시다. 이 때 각 밧줄들과 연결시켜 물체를 들어올리기 때문에 각 밧줄이 버틸수 있는 무게인 t 를 넘는 물건을 들어올리려고 하면 밧줄은 끊어집니다. 그러나 우리는 무거운 물체를 여러 개의 밧줄로 평행하게 묶어서 모든 밧줄을 끌어올리는 방법을 쓰면 무거운 물체도 들어올릴 수 있습니다. w 의 무게를 가진 무거운 물건을 들어올리기 위해 k 개의 밧줄을 사용한다면, 각 밧줄에 w/k 만큼의 무게가 주어진다고 가정합니다. 하지만 밧줄이 버틸수 있는 무게인 t 를 놓고 볼 때, w/k > t 가 된다면 밧줄은 끊어지게 됩니다. 예를 들어 3 개의 밧줄이 각각 버틸수 있는 무게가 1, 10, 15 라고 치면, 3 보다 무거운 무게를 가진 물건을 이 3 개의 밧줄을 묶어서 들어올리려 할 경우 가장 약한 밧줄이 끊어지기 때문에 3개의 밧줄을 전부 묶어서 들어올릴 수 없습니다. 그러나 두번째 밧줄은 그 자체만으로 10의 무게까지 들어올릴 수 있습니다. 각 밧줄이 버틸 수 있는 무게를 알려주면 당신은 주어진 밧줄들의 부분집합을 하나 골라서, 부분집합에 속한 밧줄들이 하나도 끊어지지 않고 물건을 들어올릴 수 있는 가장 무거운 무게를 알아내는 것입니다.

입력

입력의 첫 번째 줄은 하나의 정수 t (1 <= t <= 10) 를 쓰는데 뒤에 나올 테스트 케이스들의 개수를 나타냅니다. 각 테스트 케이스들의 첫 번째 줄은 하나의 정수 n (1 <= n <= 1000) 을 입력하는데, 이 n 은 밧줄의 개수를 나타냅니다. 그 다음으로 나오는 줄에는 1부터 10000까지의 범위 안에 있는 n 개의 정수들이 나오는데 각각은 밧줄이 끊어지지 않는 최대한의 무게를 나타내고, 각 무게들은 사이에 공백으로 띄어서 나타냅니다.

출력

테스트 케이스에서 주어진 밧줄들이 하나도 끊어지지 않는 최대한의 무게를 한 줄로 출력합니다.

입력 예시

2
3
10 1 15
2
10 15

출력 예시

20
20

Source

Tehran 2003

p.s: 일부분 수정했습니다.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (1) 2010.11.01
posted by Sparking

댓글을 달아 주세요

점프하는 소들
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4560 Accepted: 2761

설명

농부 John의 소들은 동요에 나오는 것 처럼 달을 뛰어넘고 싶어합니다. 그러나 불행하게도 소들은 뛸 수 없습니다.

그 지역에 사는 주술사가 달을 뛰어넘고 싶어하는 소들의 부탁을 들어주기 위해 P (1 <= P <= 150,000) 개의 물약을 만들었습니다. 이 물약들은 조제된 순서대로 투약되는데 개중에 투약되지 않고 다음 물약으로 넘어가는 경우도 있습니다.

각 물약은 소들이 점프할 수 있는 'strength'  (1 <= strength <= 500)를 증가시켜줍니다. 각 소들이 물약을 마시는 순서를 놓고 볼 때, 홀수번째로 먹는 물약은 소의 점프능력을 증가시켜주고; 짝수번째로 먹는 물약은 소의 점프능력을 감소시킵니다. 물약을 먹기 전의 소의 점프능력은 당연히 0입니다.

모든 소는 자신에게 주어진 물약들 중 한 개 이상은 마셔야 합니다. 이 때, 물약의 성능에 따라 마실지 마시지 않을지를 판단하여 다음 물약으로 넘길 수 있고, 한 번 마셨거나 넘긴 물약은 다시 마실 수 없습니다.

어떤 물약을 투여했을 때 가장 높게 점프할 수 있는지를 알아내세요.

입력

* 첫번째 줄: 하나의 양정수 P 

* 두번째 줄부터 P+1번째 줄: 각 줄은 하나의 양정수가 들어가는데, 물약의 strengh 를 의미합니다. 2번째 줄은 첫번째 로 주어진 물약의 strength 이고; 3번째 줄은 두번째로 주어진 물약의 strength 이고; 이하 동일합니다.

출력

* 첫번째 줄: 최대로 점프할 수 있는 하나의 양정수. 

입력 예시

8
7
2
1
8
4
3
5
6

출력 예시

17

Source

USACO 2003 U S Open Orange


p.s: 미친소도 아니고 왜 동요에서 소들이 달로 뛰는거람 도대체..
p.s2: Lonewolf dlbo의 의견을 수렴하여 일부분 수정합니다.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (1) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
posted by Sparking

댓글을 달아 주세요

  1. 어떤 물약도 두번 투여되지 않고, 소는 물약이 투여된 뒤에는 1부터 시작하는 자신의 매 차례마다 물약을 섭취해야 합니다. 매 순서마다 하나 이상의 물약은 다음 물약으로 넘겨질 수 있습니다.

    이건 도대체 뭔 소리여

  2. No potion can be taken twice, and once the cow has begun taking potions, one potion must be taken during each time step, starting at time 1. One or more potions may be skipped in each turn.

    어떤 물약도 반복해서 섭취할수 없고, 한번 물약을 마신 소는 처음부터 매 턴마다 물약을 쳐마셔야 한다. 중간에 한개, 혹은 여러개의 물약을 그냥 안마시고 제낄 수 있다.

속임수 카드놀이
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2541 Accepted: 1854

설명

마술사가 카드 뭉치를 잘 섞고서 전부 뒤집은 채로 잡은 뒤 다음 단계를 수행합니다:

  1. 맨 위에 있는 카드를 가장 아래로 옮깁니다. 새로이 맨 위에 있는 카드를 테이블 위로 꺼냅니다. 그 카드는 스페이드 에이스입니다.
  2. 맨 위에 있는 두 장의 카드를 맨 밑으로 옮깁니다. 그 다음 맨 위에 있는 카드를 테이블 위로 꺼냅니다. 그 카드는 스페이드 2 입니다.
  3. 맨 위에 있는 세 장의 카드를 맨 밑으로 옮기고…
  4. 이렇게 맨 위에 있는 n장의 카드를 맨 밑으로 옮기고 맨 위에 있는 카드를 테이블 위로 꺼내면 그 카드는 스페이드의 n번째 카드입니다.

이 트릭은 마술사가 어떻게 카드를 섞을지 미리 알고 있을때 가능합니다(그리고 어떻게 섞는것처럼 보이게 할 지를 알고 있어야 하지요). 당신의 프로그램은 1부터 13중 카드의 순서를 정해서 어떤걸 먼저 할 지 결정하는 것입니다.

입력

입력의 첫째 줄에는 테스트 케이스의 수를 나타내는 하나의 양정수가 들어갑니다. 각 테스트 케이스는 하나의 정수 n이 들어갑니다.

출력

각 테스트 케이스에 대해서 1 부터 n까지의 값 중 올바른 순열로 한 줄에 표기하는데, 이때 각 숫자들 사이엔 공백을 둡니다 . 첫 번째 숫자는 카드뭉치의 맨 위에 있는 카드를 나타내고 그 뒤는 같은 원리로…

입력 예시

2
4
5

출력 예시

2 1 4 3
3 1 4 5 2

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (1) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
posted by Sparking

댓글을 달아 주세요

볼링치는 소
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7685 Accepted: 5014

설명

소들은 진짜 볼링공을 굴려서 볼링을 치진 않습니다. 대신 각자 번호를 맡아서(번호의 범위는 0부터 99까지입니다) 자리를 잡고 볼링핀처럼 삼각형 모양으로 서있지요: 

          7


3 8

8 1 0

2 7 4 4

4 5 2 6 5
그러면 다른 소들이 삼각형의 맨 윗부분에서 시작해서, 아래쪽에 있는 가까운 두 마리 소 중 한 마리에게 움직입니다. 이러한 움직임을 가장 아래쪽에 내려갈 때까지 계속해서, 각 소의 점수는 지나온 경로의 소들의 번호들을 합한 값이 됩니다. (당연하지만) 합한 값이 제일 큰 소가 그 프레임의 우승자가 됩니다.

삼각형 대형의 줄 수는 N 개(1 <= N <= 350) 일 때, 가능한 경로중에서 숫자의 합이 가장 큰 값을 찾는것이 목표입니다.

입력

첫번째 줄: 하나의 정수 N 

두번째 줄부터 N+1 번째 줄 : i+1 번째 줄은  i 개의, 각 숫자 사이엔 공백으로 떨어져있는 정수들을 포함하는데,  삼각형 대형의 i 번째 줄을 나타냅니다.

출력

하나의 줄: 정해진 규칙을 따라 나올 수 있는 합의 최대값

입력 예시

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

출력 예시

30

Hint

Explanation of the sample: 

          7

*
3 8
*
8 1 0
*
2 7 4 4
*
4 5 2 6 5
The highest score is achievable by traversing the cows as shown above.

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (1) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (5) 2010.07.24
posted by Sparking

댓글을 달아 주세요

  1. 왠지 이거랑 유사한 문제를 전에 풀었던 것 같은데

    기분탓인가? -_-;

재빠른 거스름돈 주기
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3979 Accepted: 2914

설명

J.P. Flathead의 가게에서 계산을 할 싼 인력을 고용했습니다. 보통 고등학생들을 고용하는데, 이 알바들은 손님들에게 거스름돈을 줄 때 실수가 많습니다. Flathead는 자기가 직접 계산을 해서 거스름돈을 줄 때 실수하는 금액보다, 알바들이 손님들에게 거스름돈을 줄 때 실수하는 금액이 더 많다는 것을 알게 되었습니다.

Flathead는 당신이 손님들에게 줄 거스름돈에 들어가는 quarter($0.25), dime($0.10), nickel($0.05), penny($0.01) 4개의 동전들이 각각 몇개씩인지를 계산하는 프로그램을 만들었으면 합니다. Flathead는 거스름돈으로 줄 금액이 $5.00 를 넘지 않고 최소한의 동전들로 거스름돈을 주기를 바랍니다. 예를 들어 거스름돈이 $1.24 라면, 손님에게 줄 거스름돈은 4개의 quarter, 2개의 dime, 니켈은 없고 4개의 penny가 되어야 합니다.

입력

첫번째 줄에 입력할 것은 정수 N인데 이 숫자는 계산할 데이터셋의 개수를 의미합니다. 각 데이터셋에는 거스름돈으로 계산할 하나의 정수 C(1 ≤ C ≤ 500)를 입력합니다.

출력

각 데이터셋에 대해서 알맞은 숫자와 공백, 그리고 동전의 단위를 나타내는 문자열을 출력합니다:

Q QUARTER(S), D DIME(S), n NICKEL(S), P PENNY(S)

Q는 quarter의 수량을, D는 dime의 수량을, n은 nickel의 수량을, 그리고 P는 penny의 수량을 나타냅니다.

입력 예시

3
124
25
194

출력 예시

1 4 QUARTER(S), 2 DIME(S), 0 NICKEL(S), 4 PENNY(S)
2 1 QUARTER(S), 0 DIME(S), 0 NICKEL(S), 0 PENNY(S)
3 7 QUARTER(S), 1 DIME(S), 1 NICKEL(S), 4 PENNY(S)

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (1) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (5) 2010.07.24
PKU 1050. To the Max  (4) 2010.05.29
posted by Sparking

댓글을 달아 주세요

오류 수정
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3990 Accepted: 2641

설명

0과 1로만 이루어진 어떤 행렬의 각 행과 각 열의 합이 짝수만 나올 때 이 행렬을 같은 특성을 지닌 행렬이라고 말합니다. 즉 모든 행과 열이 짝수 비트로 이루어졌을때를 말합니다. 4 x 4 행렬중에 이러한 예를 들어보면: 
1 0 1 0

0 0 0 0
1 1 1 1
0 1 0 1

행의 합들은 각각 2, 0, 4, 2입니다. 열의 합들은 각각 2, 2, 2, 2입니다. 
당신이 해야 할 일은 주어진 집합이 같은 특성을 지녔는지를 확인하는 프로그램을 작성하는 것입니다. 만약 같은 특성을 지닌 행렬이 아니라면, 단 하나의 비트를 바꿈으로써 그 행렬이 같은 특성을 지닐 수 있는지를 확인해야 합니다. 만약 이 두 가지가 전부 불가능하다면 그 행렬은 특성이 변한 집합으로 분류합니다.

입력

입력은 하나 이상의 테스트 케이스들을 해야 합니다. 각 테스트 케이스의 첫 줄은 100보다 작은 하나의 정수 n으로 시작하는데, 이 n은 행렬의 크기를 나타냅니다. 그러고 난 뒤의 n줄에는 각 줄마다 n개의 정수를 입력합니다. 행렬에는 오직 0과 1 두 정수만 사용해야 합니다. n을 입력하는 자리에 0을 입력하는 것으로 입력을 종료합니다.

출력

입력된 각 행렬에 대해서 한 줄로 출력합니다. 입력된 행렬이 이미 같은 특성을 지녔을 경우 "OK"를, 하나의 비트를 바꾸는 것으로 같은 특성을 지닌 행렬이 될 경우 "Change bit (i,j)"를 출력하는데 i와 j는 각각 바꾸어야 할 행과 열을 의미합니다. 그렇지 못한 경우 "Corrupt"를 출력합니다.

입력 예시

4
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 0 1 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 1 1 0
1 1 1 1
0 1 0 1
0

출력 예시

OK
Change bit (2,3)
Corrupt

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3176. Cow Bowling  (1) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (5) 2010.07.24
PKU 1050. To the Max  (4) 2010.05.29
PKU 1422. Air Raid  (2) 2010.04.30
posted by Sparking

댓글을 달아 주세요

341 - Non-Stop Travel

Time limit: 3.000 seconds

 안멈추는 여행 

David는 운전할 때 정지 신호와 양보신호, 그리고 신호등의 삼색 신호에 따라 기다리는 것을 싫어합니다. 이러한 짜증을 줄이기 위해서 평소에 자주 가는 곳들의 지도를 준비한 뒤 각 지역들의 교차로마다 평균적으로 얼마나 멈추게 되는지를 초단위로 잽니다. David는 이제 당신의 도움을 받아서, 각 지역의 특정한 두 지점을 놓고, 그가 한 지점에서 다른 한 지점으로 갈 때까지 걸리는 지연시간을 최소로 할 수 있는 방법을 찾고 싶어합니다. 이 때, 지연시간을 최소로 하기 위하여 총 운전거리가 늘어나는 것은 상관하지 않습니다.

입력

각 지역에서 David는 당신에게 지도를 줄겁니다. 지도에 나와있는 데이터의 첫번째 숫자는 교차로의 개수를 의미하는 N이고 각 지역마다 교차로는 10개가 넘지 않습니다. 각 지역의 교차로는 순서대로 (1)부터 숫자를 매깁니다. 각 교차로에는 대해 입력할 값은 순서대로 다른 교차로로 가는 길이 총 몇 개나 있는지를 나타내는 숫자와 각 길이 몇 번 교차로로 가는 길인지를 나타내는 숫자와, 각 교차로에서 David가 지연될 초를 나타내는 숫자를 입력합니다. 데이터에 따라 각 지역의 마지막 교차로 다음 줄에는 David가 운전을 시작하길 원하는 지점과 끝내길 원하는 지점에 대한 숫자가 적혀있습니다. 모든 지도의 입력은, 하나의 정수 (0)을 입력하는 것으로 끝냅니다.

출력

각 지역에 대해 한 줄로 출력하는데 1부터 시작하는 지역을 나타내는 숫자와, David가 지연되는것을 최소화한 이동경로를 지나갈 때 만나게 될 교차로들의 각 번호와, 그 경로로 이동할 시 걸리게 될 지연시간을 나타냅니다. 아래 예시에 나올 출력 방법을 참고하세요.

알림

  1. 각 지역은 지연시간을 최소화하는 유일한 경로가 존재합니다.
  2. 교차로 I 에서 교차로 J로 가는 길은 일방통행입니다. 교차로 I에서 교차로 J로 가는 양방향 길을 나타내려면 지도에는 교차로 J에서 교차로 I로 가는 길을 보여줘야 합니다.
  3. 교차로 I에서 교차로 J로 한번에 가는 방법은 단 하나 뿐입니다.

예시

다음 지도에서 David가 2번 교차로에서 4번 교차로로 가기를 원한다고 가정해보면:

                +---------------+                   From To Delay
                |               V                     1   3   3
                1<------2------>3------>4<------5     1   4   6
                |       |               ^       ^     2   1   2
                |       +---------------|-------+     2   3   7
                |                       |             2   5   6
                +-----------------------+             3   4   5
                                                      5   4   7

밑에 나올 예시의 1번 케이스대로 입력 및 출력하면 됩니다.

입력 예시

5
2  3 3   4 6
3  1 2   3 7   5 6
1  4 5
0
1  4 7
2 4

2
1   2 5
1   1 6
1 2

7
4   2 5   3 13   4 8   5 18
2   3 7   6 14
1   6 6
2   3 5   5 9
3   6 2   7 9    4 6
1   7 2
0
1 7

0

출력 예시

Case 1: Path = 2 1 4; 8 second delay
Case 2: Path = 1 2; 5 second delay
Case 3: Path = 1 2 3 6 7; 20 second delay







'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (5) 2010.07.24
PKU 1050. To the Max  (4) 2010.05.29
PKU 1422. Air Raid  (2) 2010.04.30
PKU 2844. 합과 곱. 스풰샬 스퉤이지~  (1) 2010.04.30
posted by Sparking

댓글을 달아 주세요

  1. 문제가 이해안감 ㄷㄷㄷ

  2. 뭔가 묘하다 했더니 UVa였구나;;;;

  3. 느긋하게 풀어볼란다

  4. 이건 컴파일 안하고는 못풀겠다.... 일단 쥐쥐

제일 크게
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 20504 Accepted: 10588

설명

부호에 상관없는 2차원 평면상의 정수집합체를 주고, 그 안에서 전체 크기 안에 들어가는 1*1 또는 그보다 조금 더 큰 직사각형 모양의 부분집합체를 잡습니다. 직사각형의 합은 직사각형 안에 들어가는 모든 원소의 합을 의미합니다. 가장 합이 큰 직사각형이라는 것은, 직사각형으로 이루어지는 모든 부분집합체들 중 원소들의 합이 가장 큰 직사각형을 의미합니다.  
예를 들어 다음 집합체에서 가장 합이 큰 직사각형은

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 
왼쪽 아래 부분에 있고

9 2 
-4 1 
-1 8 
그 합은 15입니다. 

입력

입력할 때 정수집합체는 N * N 의 형태를 갖습니다. 입력은 첫 줄에 하나의 양정수 N으로 시작하는데, 이 N 은 정사각형 형태의 정수집합체의 한 변의 크기를 나타냅니다. 그러므로 이 뒤에는 N^2 개의 정수들이 나오는데, 각각 공백 또는 줄바꿈 등으로 분리해서 입력합니다. 이 N^2 개의 정수들은 행렬로 나타내었을 때 1행부터, 같은 행에 있는 숫자들은 1열에 있는 수부터 기재합니다. N 은 최대 100 까지의 값까지 허용됩니다. 모든 정수들은 폐구간 [-127,127] 안의 숫자들로 이루어져야 합니다.

출력

가장 합이 큰 직사각형의 합 을 출력합니다.

입력 예시

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

출력 예시

15

Source

Greater New York 2001

p.s: row-major order 라는게 행 우선 순서 라고 할 수 있을것 같기도 한데 완전히 처음 들어보는 정렬방식이군요 전.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (5) 2010.07.24
PKU 1050. To the Max  (4) 2010.05.29
PKU 1422. Air Raid  (2) 2010.04.30
PKU 2844. 합과 곱. 스풰샬 스퉤이지~  (1) 2010.04.30
PKU 2245. Lotto.  (0) 2010.03.16
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://cm4st.tistory.com BlogIcon Mr.K 2010.05.31 21:45  Addr Edit/Del Reply

    대충 읽어보니까

    row-major order라는게 우리가 흔히 쓰는 방식을 얘기한 것 같네


    이 문제를 예로 들었을 때

    1행 1열 원소를 입력받고 1행 2열 원소를 입력받게 하잖아? 이게 row-major인 것 같고,

    만약 1행 1열 원소를 입력받고 2행 1열 원소를 입력받게 한다면 column-major가 되는거인듯 '-';

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2010.06.01 15:39  Addr Edit/Del

      아니 그걸 이해 못한건 아닌데
      그런 방식을 row-major order 라고 부른다는걸 처음 들었다구 ㅋ
      보통 저렇게 쓰지 -_-ㅋㅋㅋㅋㅋㅋㅋㅋ

  2. 슈봐 새 문제 이거였어?;; 합과곱 먼저 풀고 한다는게;

공습
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 2879 Accepted: 1701

설명

어떤 도시가 있는데, 이 도시의 모든 도로는 일방통행이고 각 도로는 서로 다른 교차로와 연결되어있습니다. 또한 이 길들은 아무리 길을 따라 걸어도 한 번 출발했던 교차로로 다시 돌아올 수 없는, 순환하지 않는 길들입니다.

이러한 가정 하에 당신은 프로그램을 작성하여 만약 낙하부대가 이 도시에 작전을 펼쳤을 때 모든 낙하부대원은 하나 이상의 교차로를 지나야만 하고, 모든 교차로를 한 명 이상의 낙하부대원이 지나가도록 하는 최소한의 낙하부대원 수를 구해야 합니다. 모든 낙하부대원들은 교차로에 착지한 후 도시의 길을 따라 다른 교차로를 찾아갈 수 있습니다. 각 낙하부대원들의 시작지점이 될 교차로에는 제한이 없습니다.

입력

당신의 프로그램은 데이터의 셋들을 읽어야 합니다. 입력의 첫 줄은 데이터 셋의 총 개수를 나타냅니다. 각 데이터 셋은 도시의 구조를 나타냅니다:

no_of_intersections 
no_of_streets 
S1 E1 
S2 E2 
...... 
Sno_of_streets Eno_of_streets 

각 데이터 셋의 첫번째 줄은 양정수 no_of_intersections ( 0보다 크고 120보다 작거나 같습니다.)로 교차로의 개수를 나타냅니다. 두번째 줄은 양정수 no_of_streets 로 도시에 있는 길의 개수를 나타냅니다. 그 다음에 오는건 no_of_streets 개수의 줄로 각 줄은 무작위 순서로 도시의 길이 어떻게 이어져있는지를 나타냅니다. 길의 수 k (k <= no_of_street) 에 따라 정해진 줄들은 두 개의 양정수로 이루어져있는데, 두 양정수 사이엔 공백을 둡니다: Sk(1 <= Sk <= no_of_intersections) - 길의 시작지점에 있는 교차로의 번호  와 Ek(1 <= Ek <= no_of_intersections) - 길의 종착지점에 있는 교차로의 번호 가 두 양정수입니다. 교차로들은 1부터 no_of_intersections 까지의 정수로 나타냅니다.

연속된 데이터 셋들 사이에는 공란은 없습니다. 입력 데이터는 정확합니다.(??)

출력

프로그램의 결과는 정해진 출력방식을 따라야 합니다. 각 입력 데이터 셋에 대해 하나의 줄로 결과를 출력하는데, 출력값은 하나의 정수로 나타나며, 도시의 모든 교차로를 가기 위해 필요한 최소한의 낙하부대원 수를 나타냅니다.

입력 예시

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

출력 예시

2
1

Source

Dhaka 2002


p.s: Input data are correct. 이부분은 뭘로 해석할까요?..왜 저기 들어가있는거지..OTL
p.s2: Mr.K 의 지적을 받아 수정하였습니다.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

UVa 341. Non-Stop Travel  (5) 2010.07.24
PKU 1050. To the Max  (4) 2010.05.29
PKU 1422. Air Raid  (2) 2010.04.30
PKU 2844. 합과 곱. 스풰샬 스퉤이지~  (1) 2010.04.30
PKU 2245. Lotto.  (0) 2010.03.16
PKU 2390. Bank Interest  (0) 2010.03.02
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://cm4st.tistory.com BlogIcon Mr.K 2010.05.01 10:44  Addr Edit/Del Reply

    오타 : 두 양정수 "아이엔"



N개짜리 정수 수열 A1, A2, ... , AN가 있습니다. 우리는 이를 이용해 이들의 합 S와 곱 P를 쉽게 구할 수 있지요(.... 웃기고 있네;;;). 주어진 N과 S, P를 이용해 수열 A1, A2, ... , AN를 구할 수 있을까요?

입력

한 줄에 N, S, P 세개만 입력됩니다. N은 1000000을 넘지 않으며, S와 P는 150000000을 넘지 않습니다.

출력

해답이 존재하지 않는다면 "No Solution"을, 존재한다면 해당 수열을 출력하여 주세요.

입력 예시

sample input#1
2 4 3
sample input#2
4 4 2

출력 예시

sample output#1
1 3
sample output#2
No solution

출처

POJ Monthly--2006.06.25, Yang Yi



스풰샬 스퉤이지~ 아무래도 곽만 풀수 있는 거 아닐까 싶기도 합니다. ㅋㅋㅋㅋ

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 1050. To the Max  (4) 2010.05.29
PKU 1422. Air Raid  (2) 2010.04.30
PKU 2844. 합과 곱. 스풰샬 스퉤이지~  (1) 2010.04.30
PKU 2245. Lotto.  (0) 2010.03.16
PKU 2390. Bank Interest  (0) 2010.03.02
PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. 전 곽이 달리라고 해서 달렸을 뿐이에요. ㅡ,.ㅡ....

복권
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3799 Accepted: 2458

설명

독일식 복권은 {1,2,...,49} 중 6개의 숫자를 고릅니다. 비록 당첨확률을 높여주는 방법은 아니지만, 대중적인 선택방법에는, 49개의 숫자들 중 어떤 수 k (k > 6)를 포함하는 부분집합 S를 선택하여 그 안에서 숫자들을 고르는 것입니다. 예를 들어 k=8 이고 S = {1,2,3,5,8,13,21,34} 라면 [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34] 등 가능한 선택하는 방법은 28개가 되겠습니다.

당신은 이제 k 와 집합 S를 받으면, S 안에서 가능한 모든 선택방법의 수를 고르는 프로그램을 작성하세요.

입력

입력은 하나 또는 그 이상의 테스트 케이스들로 이루어집니다. 각 테스트 케이스는 여러 정수들로 이루어져있는데, 각 정수 사이에는 공백을 둡니다. 각 줄의 첫번째 정수는 k (6 < k < 13) 이고, k개의 정수가 뒤이어 나오는데, 오름차순으로 S의 원소를 전부 나타냅니다. 입력은 k 위치에 0 을 넣으면 종료되도록 합니다.

출력

각 테스트 케이스에 대해, 가능한 모든 방법의 수를 한 줄에 나타냅니다. 각 방법에 쓰일 수들은 오름차순으로 정리되어야 하고, 각 숫자 사이엔 공백을 둡니다. 각 방법들은 사전식으로, 다시 말하면 가장 작은 숫자로 시작하는 방법이 처음에 나오고, 그 다음으로 작은 숫자로 시작하는 방법 순으로 가서, 밑에 나오는 출력 예시처럼 나오게 합니다. 각 테스트 케이스들은 비어있는 하나의 줄로 분리시켜둡니다. 마지막 테스트 케이스 뒤에는 빈 줄을 넣지 마세요.

입력 예시

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

출력 예시

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 1422. Air Raid  (2) 2010.04.30
PKU 2844. 합과 곱. 스풰샬 스퉤이지~  (1) 2010.04.30
PKU 2245. Lotto.  (0) 2010.03.16
PKU 2390. Bank Interest  (0) 2010.03.02
PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
PKU 3589. Number-guessing Game  (0) 2010.02.01
posted by Sparking

댓글을 달아 주세요

은행 이자
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 8868 Accepted: 5327

설명

Farmer John은 작년에 돈을 좀 벌었습니다. 그래서 그 돈을 어딘가에 투자하고 싶은데, 투자해서 얼마의 이익이 나올지 알고 싶어합니다. 그는 그가 이용하는 은행에서 매년 적립되는 이율 R (0부터 20 사이의 정수)을 알고 있습니다. 지금 그가 가진 돈은 100부터 1,000,000 사이의 정수 M 입니다. 근데, 그는 총 Y (0부터 400까지) 년에 걸쳐서 돈을 투자하려고 합니다. 그가 저축한 돈이 미래에 총 얼마가 되서 돌아올지를 알려주세요. 반올림 없이 정수 부분만 나타내세요. 부호가 있는 32비트형 정수로 테스트 데이터에 대한 답이 나오게 하세요.

입력

* 한 줄 : 공백으로 분리된 세 정수 R, M, Y

출력

* 한 줄 : Y 년 후 FJ가 받게 될 총 금액을 나타내는 정수

입력 예시

5 5000 4

출력 예시

6077

힌트

세부 입력:

5% 이율, 돈 5000 , 4 년 

세부 출력: 

1년째: 1.05 * 5000 = 5250 
2년째: 1.05 * 5250 = 5512.5 
3년째: 1.05 * 5512.50 = 5788.125 
4년째: 1.05 * 5788.125 = 6077.53125 
6077.53125 의 정수부분은 6077.

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2844. 합과 곱. 스풰샬 스퉤이지~  (1) 2010.04.30
PKU 2245. Lotto.  (0) 2010.03.16
PKU 2390. Bank Interest  (0) 2010.03.02
PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
PKU 3589. Number-guessing Game  (0) 2010.02.01
UVa 562. Dividing Coins.  (7) 2009.12.12
posted by Sparking

댓글을 달아 주세요

간단한 화학문제
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4199 Accepted: 2809

설명

당신은 연구실에서 매우 열정적인 대학원생이지만, 대학교 학부생 시절의 101 화학연구실이 어땠는지를 잊어버린 선배 밑에서 화학을 연구중입니다. 그 선배가 획기적인 아이디어를 하나 떠올렸는데, 당신이 연구실에서 하루종일 혼합물의 온도를 관찰하는 것입니다. 그렇게 하면 어떤 변화가 있는지 전부 기록하는 것이지요.

컴퓨터 과학자가 될 거기 때문에, 당신은 그 과정을 자동으로 하는 방법을 알고 있으므로 프로그램을 작성하여 연구실에서 랩톱으로 작동하게 할 것입니다. (랩톱은 가끔 연구실의 화학물질로 인해 녹습니다.) 당신은 연구실에 들어온 뒤에 당신이 관찰한것처럼 온도를 기록해주는 프로그램을 작성해서, 그 프로그램이 기존에 기록된 온도와 새로이 기록한 온도의 차이를 계산하도록 합니다. 그러면 그 결과를 그래프 형태로 입력하여 연구실을 나가기 전에 당신의 할 일을 다 하면 됩니다.

입력

입력은 한 줄에 하나의 온도를 넣는데, 각 온도는 -10 에서 200 사이에 있습니다.  온도는 소수로 입력될 수 있습니다.  마지막 관찰 뒤에는 999를 입력하여 입력을 종료합니다. 모든 데이터 세트는 최소한 두 개의 온도 관찰값을 가져야 합니다.

출력

당신의 프로그램은 기존의 온도와 새로 관찰된 온도의 차이를 출력해야 합니다. 제일 작은 온도차이는 그 전 온도와 똑같을 때입니다. 온도차이는 항상 소수로 출력되고, 맨 앞에 0이나 공백이 오지 않습니다.(단, 두 온도의 차이가 1보다 작을 경우엔 허용됩니다.) 출력을 마무리지을땐, "End of Output"을 출력합니다.

입력 예시

10.0
12.05
30.25
20
999

출력 예시

2.05
18.20
-10.25
End of Output

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2245. Lotto.  (0) 2010.03.16
PKU 2390. Bank Interest  (0) 2010.03.02
PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
PKU 3589. Number-guessing Game  (0) 2010.02.01
UVa 562. Dividing Coins.  (7) 2009.12.12
PKU 3372. Candy Distribution  (6) 2009.11.25
posted by Sparking

댓글을 달아 주세요

숫자맞추기 게임
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3240 Accepted: 2406

설명

Larry는 숫자맞추기 게임을 좋아합니다.

이 게임은 두 명이 있어야 시작할 수 있는데, 각각을 X와 Y라고 하고 X는 Y가 맞출 숫자를 준비합니다. 이 숫자는 4자리여야 하고, Y에겐 말하지 않은 상태로 Y가 생각하기 시작합니다. Y가 말하면 X는 *A*B의 형태로 대답하여야 하는데, 이 대답은 Y가 생각한 숫자가 X가 생각하고 있던 숫자와 얼마나 근접하였는지를 알려줍니다. A앞에 나오는 숫자는 위치와 숫자가 모두 맞는 것의 개수이고, B앞에 나오는 숫자는 위치는 틀렸지만 숫자가 맞은 것의 개수입니다.

예를 들어, X가 5204 를 생각하였고 Y가 4902를 추측했다면, 0은 위치와 숫자가 모두 맞았고, 4와 2는 숫자는 맞았지만 위치는 틀렸기에 X는 1A2B 라고 대답해야 합니다. Y는 이 1A2B라는 결과를 생각하며 정답인 5204가 될 때까지( 이 경우 X는 4A0B라고 말할 것입니다.) 계속 추측할 것입니다.

자 이제 두 숫자를 받으면 당신은 그 두 숫자가 얼마나 근접하였는지를 말해주면 됩니다.

입력

첫번째 줄의 입력은 테스트 케이스의 개수를 나타내는 정수 T가 들어가고, 각 테스트 케이스에는 2개의 숫자들이 있습니다. 각 숫자들은 서로 다른 4자리의 수로 이루어져 있습니다.

출력

각 테스트 케이스에 대해 *A*B의 형식으로 얼마나 두 수가 근접해있는지를 출력하세요.
 

입력 예시

2
5204 4902
0123 3210

출력 예시

1A2B
0A4B

Source

South Central China 2008 hosted by NUDT


p.s: 야구게임이었구나..
p.s2: dlbo군, Mr.K군. 설 오기전에 얼굴좀 보자.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2390. Bank Interest  (0) 2010.03.02
PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
PKU 3589. Number-guessing Game  (0) 2010.02.01
UVa 562. Dividing Coins.  (7) 2009.12.12
PKU 3372. Candy Distribution  (6) 2009.11.25
PKU 3224. Go for Lab Cup!  (3) 2009.11.09
posted by Sparking

댓글을 달아 주세요

  동전 나누기

일반적으로 구리선은 네덜란드인이 발명한 것으로 알려져 있습니다. 두 네덜란드 사람이 구리로 만들어진 동전을 두고 싸우고 있었습니다. 그들은 동전을 매우 가지고 싶었기 때문에 싸움은 꽤나 난폭하게 벌어졌고 결국 동전을 매우 세게 양쪽에서 잡아당기는 바람에 구리선이 만들어지게 되었다고 합니다.


그러나 싸운 뒤의 일은 잘 알려져 있지 않은데요, 그 뒤에 두 사람은 동전으로 차있는 가방을 둘 중 한 명에게 주려고 했습니다. 가방 안의 들어있는 동전들은 똑같이 나눌순 없었습니다. 첫 번째 사람은 그 둘 모두가 아주 사소한 것까지 똑같이 나누고 싶어한다는 점에서 분배량이 똑같지 않다는 것을 참을 수 없었습니다. 요즘 들어서 동전 하나때문에 싸운다는것은 찾아보기 어려운 일이지만,  가능한한 최대한 공평하도록 똑같이 분배하는 것은 영원히 불가능한 일로 남을 것 같습니다.


이것이 이 문제의 전부입니다.두 사람에게 가방의 동전을 어떻게 나누는게 가장 공평할지를 모든 사람이 한 번에 알 수는 없습니다. 당신은 이 문제를 어떻게 풀지 이제 요청을 받았습니다.


최대 100개의 동전이 있는 가방을 가지고 시작하는데, 가장 두 사람에게 공평하게 분배하는 방법을 결정하면 됩니다. 이 말은, 각자에게 다른 양의 동전을 주는 것은 최소한으로 되어야 한다는 것입니다. 동전은 1센트부터 500센트까지의 가치를 지니고 있습니다. 단, 동전을 쪼개는 것은 안됩니다.

입력

n개의 문제를 나타내고, 그 밑에 문제가 n번 나옵니다:
  • 양정수 m(m ≤ 100)개로 이루어진 줄은 가방 안의 동전의 개수를 나타냅니다.                        
  • m개의 숫자들이 한 칸씩 사이에 두고 적히고, 각 숫자들은 동전의 가치를 나타냅니다.                                               

출력

n개의 줄로 출력합니다. 각 줄은 각각의 가방에 대해서 두 사람이 동전을 나눠가질때 발생하는 최소한의 차이를 양수로 나타냅니다.

입력 예시

2
3
2 3 5
4
1 2 4 6

출력 예시

0
1



Miguel A. Revilla 
1998-03-10

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
PKU 3589. Number-guessing Game  (0) 2010.02.01
UVa 562. Dividing Coins.  (7) 2009.12.12
PKU 3372. Candy Distribution  (6) 2009.11.25
PKU 3224. Go for Lab Cup!  (3) 2009.11.09
PKU 1989. The Cow Lineup  (2) 2009.10.27
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.12.12 01:42  Addr Edit/Del Reply

    ㅋㅋ 적당히 어려운걸 가져온듯

  2. 힘 죨랭 좋군. 구리동전을 당겨서 구리선을 만들어?;;

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2010.01.15 01:48  Addr Edit/Del

      힘은 둘째고

      손에서 몇백~몇천℃의 열이라도 나오나봄 ㅋㅋㅋ

  3. 씨바 크롬 안깔았다;;

  4. Favicon of http://klone.tistory.com BlogIcon Mr.K 2010.02.02 01:42  Addr Edit/Del Reply

    아 이거, 입력부분에 대해서 약간 수정이 필요할듯;

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2010.02.02 15:01  Addr Edit/Del

      의미가 애매하게 받아들여지긴 하겠다..수정하겠음.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2010.02.02 19:45  Addr Edit/Del

      ㅇㅇ

      입력부분 2번째 줄을

      "양정수 m(m ≤ 100)이 적힙니다. 이것은 가방 안의 동전의 개수를 나타냅니다."

      정도로 바꾸면 좋을 듯

      개인적으로 "(m ≤ 100)"은 따로 맨 뒤로 뺐으면 좋겠지만 그냥 놔둬도 괜찮겠다

      원문하고 비교했을 때 문장 형태가 좀 바뀌긴 하지만 의미전달이 잘 되는게 우선일 것 같음


      3번째 줄은

      개인적으로 "한 칸씩 사이에"를 "한 칸의 공백을" 정도로 바꾸면 좋겠지만, 이것도 그냥 놔둬도 괜찮겠음 ㅋ

사탕 나누기
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3678 Accepted: 1902

설명

N 명의 아이들이 원을 이루고 서있고, 1번부터 N번까지 시계방향으로 번호를 매기고서 자신들의 사탕을 받기를 기다리고 있습니다. 담당하는 선생님은 다음의 방법을 따라서 사탕을 나누어주려고 합니다:

우선 선생님이 1번 학생과 2번 학생에게 사탕을 하나씩 줍니다. 그다음 시계방향으로 원을 따라 걸어서 3번 학생은 넘어가고 4번 학생에게 사탕을 줍니다. 그다음 두 명의 학생을 넘어가고 7번 학생에게 사탕을 줍니다. 이러한 방식을 통하여 사탕을 나누어 주려고 합니다.

이제 당신은 모든 학생이 최소한 하나 이상의 사탕을 받을 수 있는지에 대해 선생님에게 알려줘야 합니다.

입력

입력은 여러개의 데이터 셋으로 구성되어있는데, 각 데이터 셋은 하나의 양정수 N(2 ≤ N ≤ 1,000,000,000)으로 이루어집니다.

출력

각 데이터 셋에 대하여 "YES" 또는 "NO"를 출력합니다.

입력 예시

2
3 
4

출력 예시

YES
NO
YES

Source

POJ Monthly--2007.09.09, ailyanlu@zsu

p.s: 왜 전 크롬에서 UVa가 안열릴까요.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3589. Number-guessing Game  (0) 2010.02.01
UVa 562. Dividing Coins.  (7) 2009.12.12
PKU 3372. Candy Distribution  (6) 2009.11.25
PKU 3224. Go for Lab Cup!  (3) 2009.11.09
PKU 1989. The Cow Lineup  (2) 2009.10.27
PKU 1547. Clay Bully  (0) 2009.09.24
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.11.26 00:17  Addr Edit/Del Reply

    우리집 크롬에서는 잘 열림요 ㅇㅇ;

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.11.26 14:32  Addr Edit/Del

      너희집 가서 문제 하나 올리고 갈까 -_-ㅋㅋㅋㅋㅋ

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.11.27 00:28  Addr Edit/Del

      ㅋㅋ

      전산실에 몰래 크롬을 설치하는건 어떰?
      걸리면 그닥 좋지 않을지도 모르지만 -_-;

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.11.29 13:37  Addr Edit/Del

      그보다 너네집 가는게 훨 우월함 ㅋ

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.11.30 01:08  Addr Edit/Del

      ㅋㅋㅋ 안됔ㅋㅋㅋ
      차라리 나한테 문제 본문을 보내달라고 그러든짘ㅋㅋㅋ

      내가 번역하자니 공부를 손에서 놓은지 오래돼서 -_-;

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.12.01 15:06  Addr Edit/Del

      -_-? 복붙해야 하니까 그렇지(?) 문제 본문은 나도 익스플로러에선 읽을 수 있어 ㅇㅇ

연구실 대회!
Time Limit: 1000MS Memory Limit: 131072K
Total Submissions: 5062 Accepted: 2672

설명

연구실 탁구 대회가 PKU 연구실중 한 곳에서 개최될 예정입니다. AI 연구실의 학생들은 모두 탁구에 열광하며, 이 대회에서 자신들의 연구실에 대해 알려줄 용의가 충만합니다. 그러나 quota에 의하여 단 한 팀만이 대회에 출전할 수 있도록 제한되었습니다.

공정한 선정을 위하여, 참가자들은  5판 3선승의 경기로 결정되는 리그전을 하기로 하였습니다. 가장 많이 이긴 사람이 연구실을 대표할 자격을 얻는 것이지요. 이제 연구실의 대표인 Ava 씨가, 모든 경기의 점수표를 가지고 있습니다. 과연 누가 대회에 나가는 행운을 얻게 될까요?

입력

입력은 하나의 테스트 케이스로 이루어져 있습니다. 테스트 케이스는 정수 n (2 ≤ n ≤ 100)으로 시작하는데, 연구실의 총 학생수를 나타냅니다. 그 뒤로는 n × n행렬 A가 나옵니다. 행렬의 각 원소는  0, 1, 2 그리고 3 중 하나가 되어야 합니다. i 번째 행과 j번째 열의 각 원소 aiji 번째 학생이 j번째 학생에게 이긴 게임의 수를 나타냅니다. 두 원소 aij 와 aji (i  j)중 하나는 3이고 다른 하나는 3보다 작습니다. 행렬 안의 모든 대각 원소는 0입니다.

출력

누가 가장 많이 이겼는지 그 학생의 번호를 출력하세요. 동점자가 있는 경우엔 가장 작은 번호를 고르세요.

입력 예시

4
0 0 3 2
3 0 3 1
2 2 0 2
3 3 3 0

출력 예시

4

Source

PKU Local 2007 (POJ Monthly--2007.04.28), ideas from ava, text and test cases by frkstyc


p.s: 행렬의 대각 원소 = aij (i = j)
p.s: Mr.K의 지적을 보고 수정하였습니다. OTL

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

UVa 562. Dividing Coins.  (7) 2009.12.12
PKU 3372. Candy Distribution  (6) 2009.11.25
PKU 3224. Go for Lab Cup!  (3) 2009.11.09
PKU 1989. The Cow Lineup  (2) 2009.10.27
PKU 1547. Clay Bully  (0) 2009.09.24
PKU 2000. Gold Coins.  (2) 2009.09.07
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.11.14 21:44  Addr Edit/Del Reply

    중간에

    [i번째 열과 j번째 행]이 아니고 [i번째 행과 j번째 열] 아님?

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.11.20 01:03  Addr Edit/Del Reply

    [출력]에서
    누가 가장 많이 [이겼는지]에 대한 표현이 좀 모호한듯

    원문을 보면 most matches를 세도록 하니까
    누가 가장 많은 [경기를 이겼는지] 정도로 바꾸면 좋지 않을까? =ㄴ=


    아니면 [경기]라는 표현 자체도 다른 시각에서 보면 헷갈릴 수 있으니까 아예 다른 표현을 사용하거나;

소 정렬
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 3397 Accepted: 2028

설명


농부 John이 N마리의 젖소(1 <= N <= 100,000)를 한 줄로 세우려고 합니다.  각 소에는 1...K(1 <= K <=10,000)의 표식이 있는데, 이 표식으로 그 젖소의 품종을 확인할 수 있습니다. 예를 들면 14마리의 소들의 품종은 각각 다음과 같을 수 있습니다.
1 5 3 2 5 1 3 4 4 2 5 1 2 3
농부 John은 위의 수열처럼, 모든 숫자들로 이루어질 수 있는 수학적 가능성을 염두에 두었습니다. 예를 들면, 위에 있는 수열들에서 (굳이 연속적일 필요는 없는) 3 4 1 3 이라는 부분수열을 찾을 수 있다는 것입니다. 농부 John은, 그가 가진 소들의 품종들로 만드는 수열의 부분수열이 아닌, 1부터 K까지의  한 숫자로 얼마나 짧은 수열을 만들 수 있을지를 알고 싶습니다. 그가 이 궁금증을 해결할 수 있도록 도와주세요.

입력

* 1번째 줄 : 두 개의 정수 N과 K

* 2번째 줄부터 N+1번째 줄 : 2번째 줄은 1번째 소의 품종을; 3번째 줄은 2번째 소의 품종을; 그리고 계속 그렇게 나열합니다.

출력

* 1번째 줄 : 입력한 수열의 부분수열이 아닌, 가장 짧은 수열의 길이를 나타냅니다.

입력 예시

14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3

출력 예시

3

Hint

All the single digit 'sequences' appear. Each of the 25 two digit sequences also appears. Of the three digit sequences, the sequence 2, 2, 4 does not appear. 

Source

USACO 2004 U S Open




p.s: 오래간만에 하니 영 어색하고 안풀리네요. 대체 어디서 해석이 잘못된건지 손봐주실 분? (..) 원래대로면 제가 최대한 말이 되게 만들고 나서 올려야 하지만 너무 늦어서 일단 문제 먼저 올리는 뻔뻔함을 가져보렵니다 (-)

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3372. Candy Distribution  (6) 2009.11.25
PKU 3224. Go for Lab Cup!  (3) 2009.11.09
PKU 1989. The Cow Lineup  (2) 2009.10.27
PKU 1547. Clay Bully  (0) 2009.09.24
PKU 2000. Gold Coins.  (2) 2009.09.07
PKU 2853. Sequence Sum Possibilities  (2) 2009.08.20
posted by Sparking

댓글을 달아 주세요

  1. ㅅㅂ 뭔 문젠지 모르겠어 -_-

찰흙 강탈자(?)
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 4783 Accepted: 2896

설명

Terry 씨는 맡은 원생들에게 찰흙을 가지고 놀게 시키기를 좋아하는 어린이집 교사입니다. 그녀가 아이들에게 내주는 과제중의 하나는, 찰흙 덩어리를 가지고 적당한 모양의 덩어리를 만들어서 그 크기를 재보는 것입니다. 그러나 어떤 반에 가던지, 다른 아이의 찰흙을 뺏어서 자신의 덩어리의 크기를 더 크게 만드려고 하는 나쁜 아이들이 있게 마련입니다. 그래서 Terry 씨는 모든 아이들에게 같은 양의 찰흙 덩어리를 줍니다. 이제 당신은, Terry 씨가 과제물의 크기를 재본 뒤에 어떤 나쁜 아이가 어떤 아이의 찰흙을 뺏어서 자신의 덩어리를 크게 만들었는지를 확인하는 프로그램을 작성하면 됩니다.

입력

반은 1개 이상 있고, 맨 마지막 줄에는 -1을 넣어야 합니다. 각 반은 그 반에 있는 아이들의 인원수를 나타내는 정수 n 으로 시작하는데, 그 밑으로는 n 개의 줄에 각각 아이들에 대한 정보를 나타냅니다. 각 아이들을 나타내는 줄에는 3개의 양정수가 들어가는데 이것들은 나누어준 찰흙 덩어리의 개수를 나타내고 그 뒤에는 아이들의 이름이 나옵니다. 각 반에는 2명에서 9명까지 아이들이 있습니다. 각 아이들의 이름은 최대 8글자입니다. Terry 씨는 항상 모든 아이들에게 각각 최대 250개의 찰흙 덩어리를 나누어줍니다. 또한, 모든 반에는 한 명의 강탈자와 한 명의 피해자가 반드시 있습니다.

출력

출력 예시에서 나온 것과 같게 출력하도록 만드세요,

입력 예시

3
10 10 2 Jill
5 3 10 Will
5 5 10 Bill
4
2 4 10 Cam
4 3 7 Sam
8 11 1 Graham
6 2 7 Pam
-1

출력 예시

Bill took clay from Will.
Graham took clay from Cam.

Source

Mid-Central USA 2003


p.s: 예시를 보고 설명을 봐서 이해가 안되는건 저뿐인가요 OTL

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3224. Go for Lab Cup!  (3) 2009.11.09
PKU 1989. The Cow Lineup  (2) 2009.10.27
PKU 1547. Clay Bully  (0) 2009.09.24
PKU 2000. Gold Coins.  (2) 2009.09.07
PKU 2853. Sequence Sum Possibilities  (2) 2009.08.20
PKU 2665. Trees  (2) 2009.08.04
posted by Sparking

댓글을 달아 주세요

금화
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 11700 Accepted: 7242

설명

어떤 왕이 근위기사에게 봉급을 금화로 주었습니다. 첫 근무날에는 1 개의 금화를, 그 다음 2일에 걸쳐서 하루에 2 개씩의 금화를, 그 다음 3일에 걸쳐서 하루에 3 개씩의 금화를, 그 다음 4일에 걸쳐서 하루에 4 개씩의 금화를 주는 방식으로 말이지요.  이런 패턴으로 쭉 봉급을 줍니다. 즉 어떤 양정수 N에 대해서, N 일씩 묶어서 N 개씩의 금화를 주고 나면, 근위기사는 그 다음 N + 1 일의 날들 동안 N + 1 개씩의 금화를 받게 되는 거지요.

당신이 작성할 프로그램은 시작하는 날을 첫 번째 근무하는 날로 계산하고, 주어진 날짜동안 근위기사가 받게 될 총 금화의 수를 판별해야 합니다.

입력

입력은 최소한 한 개의 줄로, 그러나 21개의 줄 이상은 안됩니다. 맨 마지막줄을 제외한 모든 줄은 하나의 테스트 케이스로 입력할 데이터를 넣습니다. 각 줄은 정확히 한 개의 정수(1이상 10000이하)로 이루어지는데, 근위기사가 봉급을 받는 총 날짜를 나타냅니다. 맨 마지막 줄은 입력의 종료를 의미하는 숫자로 0을 넣습니다.

출력

각 테스트 케이스에는 한 줄로 결과가 출력됩니다. 출력되는 형식은, 입력에서 받은, 봉급을 받게 될 날들을 우선 적고, 한 칸의 공백을 둔 뒤, 근무를 시작하는 날을 1번째 날로 치고 최종적으로 받게 될 금화의 수를 나타내면 됩니다.

입력 예시

10
6
7
11
15
16
100
10000
1000
21
22
0

출력 예시

10 30
6 14
7 18
11 35
15 55
16 61
100 945
10000 942820
1000 29820
21 91
22 98

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 1989. The Cow Lineup  (2) 2009.10.27
PKU 1547. Clay Bully  (0) 2009.09.24
PKU 2000. Gold Coins.  (2) 2009.09.07
PKU 2853. Sequence Sum Possibilities  (2) 2009.08.20
PKU 2665. Trees  (2) 2009.08.04
PKU 3210. Coins  (8) 2009.07.28
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.09.08 01:12  Addr Edit/Del Reply

    문제 번호가 심플하군 ㅋ

연속된 수들의 합으로 나타낼 수 있는 경우의 수(?)
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3213 Accepted: 2159

설명

대부분의 양정수들은 최소 2개의 연속된 양정수들의 합으로 나타낼 수 있습니다. 예를 들어,

6 = 1 + 2 + 3
9 = 5 + 4 = 2 + 3 + 4
그러나 8은 이러한 표현이 불가능합니다.

이렇게, 입력된 숫자에 대해서 최소 2개 이상의 연속된 수들의 합으로 나타내는 방법이 얼마나 많이 있는지를 계산하는 프로그램을 작성하세요.

입력

첫 번째 줄은 계산할 숫자의 개수를 나타내는 N (1  N  1000)을 적습니다. 그 뒤로 나오는 N 개의 줄에는 각 줄에 계산해야 할 숫자가 하나씩 들어가는데, 각 줄에는 문제의 번호를 나타내는 숫자를 우선 넣고, 한 칸의 공백을 둔 뒤에 계산할 숫자를 넣습니다. 계산해야 할 숫자는 2의 31승보다는 작아야 합니다.

출력

각 문제를 출력할 때에는, 각 줄에 문제 번호를 쓰고 한 칸의 공백을 둔 뒤에 입력한 문제의 수를 연속된 양정수의 합으로 나타내는 방법의 수가 얼마나 있는지를 나타내면 됩니다.

입력 예시

7
1 6
2 9
3 8
4 1800
5 987654321
6 987654323
7 987654325

출력 예시

1 1
2 2
3 0
4 8
5 17
6 1
7 23

Source

Greater New York 2005


p.s: Mr.K의 의견을 수렴, 수정하였습니다.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 1547. Clay Bully  (0) 2009.09.24
PKU 2000. Gold Coins.  (2) 2009.09.07
PKU 2853. Sequence Sum Possibilities  (2) 2009.08.20
PKU 2665. Trees  (2) 2009.08.04
PKU 3210. Coins  (8) 2009.07.28
PKU 3673. Cow Multiplication  (0) 2009.07.16
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.08.21 07:27  Addr Edit/Del Reply

    sequence 자체가 "잇따라 일어남, 연속, 계속" 같은 뜻을 가지고 있어서

    "수열"이라고 번역하기는 좀 적당하지 않은듯? =ㄴ=

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.08.23 06:53  Addr Edit/Del

      생각 수정, 의견 수렴, 수정 완료 (-)/
      지적 언제나 고마우이.

나무들
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5383 Accepted: 3713

설명

Peking 대학의 동쪽 문에서 조금 떨어진 곳에 있는 길에는 많은 나무들이 있었습니다. 그러나 지하철이 그 근방으로 다니게 되면서 많은 나무들이 잘리거나 다른 곳에 심어지는 일이 발생하였습니다. 이제 나무가 얼마나 남았는지를 세어주세요.

길의 한쪽 방향만 세어야 합니다. 시작지점으로 1미터 간격으로 나무가 심어져 있다는 것을 알아두세요.  이러한 길의 몇몇 부분은 전철역이나 선로나 다른 건물로 인하여 나무들이 잘리거나 다른 곳에 심게 됩니다.  당신이 해야 할 일은 나무가 얼마나 남아있는지를 알아내는 거지요.

예를 들면, 300미터의 길이라면 길의 시작지점부터 나무가 심어져 있으므로 나무는 301그루가 심어져 있는겁니다. 여기서, 길의 시작지점으로부터 100미터부터 200미터 까지 의 길이에 전철역이 들어선다면, 101그루의 나무가 길에서 사라지므로 200그루의 나무가 남아있게 되는 겁니다.

입력

입력에는 여러 테스트 케이스들이 있습니다. 각 케이스들은 길의 길이를 나타내는 정수 L (1 <= L < 2000000000)과 전철역 공사로 인해 본래의 길에서 사용될 구간이 총 몇 구간인지를 나타내는 정수 M (1 <= M <= 5000)으로 시작합니다.

그 뒤에는 M개의 줄이 나오는데, 각 줄은 공사에 사용될 구간을 구체적으로 나타냅니다. 다음과 같은 형식으로 말이지요:

시작 끝

이 시작과 끝 (0 <= Start <= End <= L)은 둘 다 음이 아닌 정수로, 공사 구간의 시작 지점과 끝 지점을 나타냅니다. 이 공사하는 구간들끼리 겹치면 안되는 것은 당연하겠지요.

L = 0 과 M = 0 을 입력하면 입력을 종료합니다.

출력

각 테스트 케이스에 따라 나무가 몇 그루나 남게 되는지 출력하세요.

입력 예시

300 1
100 200
500 2
100 200
201 300
0 0

출력 예시

200
300

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2000. Gold Coins.  (2) 2009.09.07
PKU 2853. Sequence Sum Possibilities  (2) 2009.08.20
PKU 2665. Trees  (2) 2009.08.04
PKU 3210. Coins  (8) 2009.07.28
PKU 3673. Cow Multiplication  (0) 2009.07.16
UVa 300. Maya Calendar  (0) 2009.07.01
posted by Sparking

댓글을 달아 주세요

  1. 내가 이탈해서 그렁가 =ㅁ= 내가 푼 문제들이 종종 보임

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.08.04 23:53  Addr Edit/Del

      요새 정신적으로 피곤해서 문제를 별 생각없이 고르는 것도 한 몫 할거다.

동전들
Time Limit: 1000MS Memory Limit: 131072K
Total Submissions: 4206 Accepted: 2615

설명


Snoopy가 3개의 동전을 가지고 있습니다. 그러다 어느날 그는 테이블 위에 동전을 던진 후에 그것들중 몇 개를 다시 던져서 전부 앞면 또는 뒷면이 나오게 하는 것을 연습해보았습니다. 여러번의 시도 끝에, 그는 처음에 동전들이 어떤 상태로 놓여지건간에, 한 번에 한 동전을 던지는 조건이 만족되면 두 번만에 원하는 모양으로 동전의 방향을 맞출 수 있고, 모든 동전은 한 번 이상 튕겨질 수 있습니다. 또한, 한 번 이하로 던져서는 목표를 달성할 수 없다는 것도 알게 되었습니다.

Snoopy는, 만약 n개의 동전을 가지고 있다면 그것들을 전부 같은 모양으로 맞출때 최소한 몇 번을 던져야 하는지를 알고 싶어합니다.

입력


입력할 것은 여러 테스트 케이스들로 이루어집니다. 각 테스트 케이스는 10000 미만의 양정수 n을 여러 줄에 입력합니다. 모든 입력이 끝나면 0을 넣고, 이 0에 대한 값은 계산하지 않습니다.

출력


각 테스트 케이스의 결과는 공백 없이 각각 하나의 줄에 나타납니다. 만약 입력에 대한 값이 존재하지 않는다면, “No Solution!”을 출력합니다.

입력 예시

2
3
0

출력 예시

No Solution!
2

Source

POJ Monthly--2007.04.01, Snoopy

p.s: 중대한 오류를 발견, 수정하긴 했습니다만, 그래도 좀 애매하군요. 여러분들의 지식이 필요합니다 OTL.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2853. Sequence Sum Possibilities  (2) 2009.08.20
PKU 2665. Trees  (2) 2009.08.04
PKU 3210. Coins  (8) 2009.07.28
PKU 3673. Cow Multiplication  (0) 2009.07.16
UVa 300. Maya Calendar  (0) 2009.07.01
PKU 1218. THE DRUNK JAILER  (3) 2009.06.22
posted by Sparking

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.07.29 01:15  Addr Edit/Del Reply

    흠 =_= 문제를 알수가 없네

    이 문제의 논리라면 동전이 2개일때도 "최대" 2번이면 되어야하지 않나 -_-;

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.07.29 02:52  Addr Edit/Del

      처음 조건에, 3개를 던지면 모두가 한 번에 같은 방향이 나오지 않는다는 전제 때문에, 반대로 말하면 둘은 같은 방향이 나오는거잖아? 설마 앞 뒤 옆 이겠냐 (-)
      그것때문에, 계산이 불가능한건 아닐까 하는 추측만 하고 있다.

  2. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.07.29 14:31  Addr Edit/Del Reply

    이런 식이라면 모든 케이스에 대해서 2번만에 다 성공할 수 있잖아 -_-;

    어떻게든 최초에 + - - - 꼴이 뜨고, 1차 시기에 + 가 뒤집히지 않으면 2차 시기엔 반드시 + 가 - 로
    뒤집히겠구만 -_-;

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.07.29 18:25  Addr Edit/Del

      그치..?
      조건이 3개씩 던진다거나 하는게 없는 이상에야..

      그래서 그러니, 해석이 틀린게 있는지 좀 봐줄 수 있겠는가 -_-?;;

  3. 이거 문제 자체가 그지임. 답은 알지만 공개는 안하고 -_-;

    판치기 변형임. 다만 1번 테이블 후려칠때마다 동전 1개만 뒤집히는거고,

    2개일때 안되는 이유는 "모두 업, 모두 다운" 두가지 스테이트를 같은 회수로 성립시킬 수 없기 때문임.

    2개일때 보는 관점이 그지같은 관계로 3개, 4개, 5개 또한 전부 답이 영 개판임.

    • Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.07.29 20:52  Addr Edit/Del

      그럴수도 있겠구나 -_-;

      근데 내가 진짜 궁금한 건, 이런 문제 정답률이 왜 50%가 넘냐는 거지.
      미국인, 중국인들만 알아들을 수 있는게야? ㄱ-

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2009.07.29 22:17  Addr Edit/Del

      안타깝게도 갸네들도 못알아먹어.

      구글서 열심히 해설 뒤지다 보니 답도 알아내고 어떻게 된

      사연인지 알게 됐는데, 문제 자체가 그지였다는군;

      푸는분들 풀다 영 안되겠다 싶으면 답 알려드립니다.

      힌트 드리자면 알고리즘이니 뭐니 전혀 쓰잘데기 없습니다 -_-;

      답 보고 어이없어서 아예 submit 자체를 시도를 안했습니다.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.07.30 02:20  Addr Edit/Del

      -_-;

      나도 어제 문제가 뭔소린가해서 구글에서 검색좀 하다가

      솔루션으로 추정되는걸 발견하긴 했는데

      이유를 알수없는 솔루션이었음 ㅋㅋㅋ

어떤 여자의 곱셈(..)
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4984 Accepted: 3304

설명

Bessie 는 평범한 방법으로 쌍을 이룬 수들을 곱하는 것에 대해 지쳐서 그녀 자신만의 곱셈 방법을 발명해냈습니다. 그녀의 방법대로라면,  A*B 는 A 와 B의 각 자리수를 뽑아서 한 쌍씩 곱한 값을 전부 더한 값이 됩니다. 예를 들어 123*45의 결과는 1*4+1*5+2*4+2*5+3*4+3*5 = 54 가 됩니다. 두 정수 A와 B(1 ≤ A, B ≤ 1,000,000,000)를 받으면 Bessie의 방법으로 곱셈을 계산하세요.

입력


칸을 두고 떨어져있는 두 개의 정수 A와 B를 입력하는 하나의 줄

출력


Bessie의 방법으로 곱셈연산을 한 A*B의 값을 표현하는 하나의 줄

입력 예시

123 45

출력 예시

54

Source

USACO 2008 February Bronze

p.s: Cow, 미국 '속어'로 여자 의 뜻이 있습니다. 처음에 소 로 하다가 암만 봐도 이상하여 찾아봤더니..ㄷㄷ  아름다운 언어를 아름답고 곱고 올바르게 사용하시는 분들이라면 저런 단어는 쓰지 맙시다 OTL..

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2665. Trees  (2) 2009.08.04
PKU 3210. Coins  (8) 2009.07.28
PKU 3673. Cow Multiplication  (0) 2009.07.16
UVa 300. Maya Calendar  (0) 2009.07.01
PKU 1218. THE DRUNK JAILER  (3) 2009.06.22
PKU 2234. Matches Game  (6) 2009.06.02
posted by Sparking

댓글을 달아 주세요

300 - Maya Calendar

Time limit: 3.000 seconds

 마야 달력 


M. A. Ya 교수는 저번 휴일에 낡은 마야 달력에 대한 놀라운 발견을 했습니다. 오래된 어려운 메시지에서, 교수는 마야 문명에서 Haab 이라고 부르는, 19달과 365일로 이루어진 역법을 사용했다는것을 알아냈습니다. 처음부터 18번째 달까지는 각각 20일로 이루어져 있는데, 그 달들의 이름은 pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu 였습니다. 각 달의 날들은 이름이 있지 않고 0부터 19까지의 숫자로 표기되었습니다. Haab의 마지막 달은 uayet 이라는 이름이었는데, 0, 1, 2, 3, 4 의 5개의 날로 이루어져 있습니다. 마야인들은 이 마지막 달이 불길하다고 생각하여, 재판도 열리지 않고 물건을 매매하지도 않았으며 청소조차도 하지 않았습니다.


이러한 풍습때문에, 마야인들은 Tzolkin 이라는, 성스러운 해 라고 부르는 또다른 달력을 사용했습니다. 이 역법에 따르면 한 해는 20일로 이루어진 13개의 구간으로 나뉘는데 각 날들은 imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau 이라는 이름을 가지고 있었고, 13번 돌아오게 하였는데, 이 두 가지 가 하나의 주기를 이루었습니다.

각 날들은 확실한 설명이 되어 있다는 것을 유념해두세요. 예를 들면 각 해의 시작을 나타내는 날들은 다음과 같이 설명되어 있습니다.:

1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau,  그리고 다음 기간엔 다시  8 imix, 9 ik, 10 akbal...


Haab과 Tzolkin , 두 개의 역법은 모두 0, 1, ... 의 숫자들로 표현하고, 0은 세상의 시작을 나타냅니다. 따라서 세상의 개벽일은 다음과 같이 표기합니다:

Haab: 0. pop 0

Tzolkin: 1 imix 0

M. A. Ya 교수를 도와서, Haab 역법으로 센 날과 Tzolkin 역법으로 센 날을 변환해서 표기할 수 있는 프로그램을 작성하세요.

입력

Haab의 날들은 다음 형식으로 나타냅니다:

날의 숫자. 달 해

입력의 첫 번째 줄은 입력할 날들의 총 수를 나타냅니다. 그 뒤로 오는 n 개의 줄엔 Haab 역법의 형식에 따른 n번째 날들이 오는데 각각은 다른 줄로 나타내고, 연도는 5000보단 작아야 합니다.

출력

Tzolkin의 날들은 다음 형식으로 나타냅니다:

숫자 날의 이름 해

출력의 첫 번째 줄은 출력할 날들의 총 수를 나타냅니다. 그 뒤로 오는 n 개의 줄엔 Tzolkin 역법의 형식에 따른, 입력한 Haab의 날들과 순서대로 대응하는 n번째 날들을 출력합니다.

입력 예시

3
10. zac 0
0. pop 0
10. zac 1995

출력 예시

3
3 chuen 0
1 imix 0
9 cimi 2801

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3210. Coins  (8) 2009.07.28
PKU 3673. Cow Multiplication  (0) 2009.07.16
UVa 300. Maya Calendar  (0) 2009.07.01
PKU 1218. THE DRUNK JAILER  (3) 2009.06.22
PKU 2234. Matches Game  (6) 2009.06.02
PKU 2243. Knight Moves  (2) 2009.05.12
posted by Sparking

댓글을 달아 주세요

술 취한 간수
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10751 Accepted: 6990

설명


 n 개의 감옥방이 긴 복도에 한없이 붙어있는 감옥이 있습니다. 각 감방에는 죄수들이 있고 문은 잠겨있습니다.
 어느날, 간수가 너무 지루해져서 게임을 하나 하기로 했습니다. 1라운드에는 간수가 위스키를 마시고 모든 감방의 문을 엽니다. 2라운드에는 간수가 위스키를 마시고, 2의 배수번호의 감방 문을 잠급니다. 3라운드에는 위스키를 마시고 3의 배수인 감방들에 가서 잠겨있다면 열고, 열려있다면 잠급니다.
 이러한 작업을 n라운드까지 반복한 뒤에 마지막 위스키를 마시면 간수는 술에 취해 잠이 듭니다.
 죄수들중 일부는 자신들의 감방이 열린 것을 깨닫고 간수가 간수로서의 자격미달임을 알게 될 것입니다. 그들은 즉시 탈출합니다.
 감방의 수를 넣고, 몇 명의 죄수가 감옥에서 탈출할 지를 알아내세요.

입력


첫 번째 줄에는 하나의 양정수를 넣습니다. 이 양정수는 밑에 올 줄의 수를 나타냅니다. 나머지 각 줄에는 5부터 100까지의 양정수를 입력하는데, 감옥방의 수를 나타냅니다.

출력

각 줄에, n개의 감옥방이 있을 때 탈출하는 죄수의 총 수를 나타냅니다.

입력 예시

2
5
100

출력 예시

2
10

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3673. Cow Multiplication  (0) 2009.07.16
UVa 300. Maya Calendar  (0) 2009.07.01
PKU 1218. THE DRUNK JAILER  (3) 2009.06.22
PKU 2234. Matches Game  (6) 2009.06.02
PKU 2243. Knight Moves  (2) 2009.05.12
PKU 2840. Big Clock  (0) 2009.05.11
posted by Sparking

댓글을 달아 주세요

  1. .... 이거 숏코딩 공부할때 푼거로군 -_-;

  2. 현실적으로는 모두 탈출할 수 있을 것 같습니다만... 근데 저거 제곱수의 수 아닌가요?

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.06.25 18:59  Addr Edit/Del

      여기다 댓글을 달아야되나 말아야되나 고민했지만 -_-;

      맞습니다 =_=ㅋ

prev 1 2 3 next