태터데스크 관리자

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

태터데스크 메시지

저장하였습니다.
블로그 이미지
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. 이거 뭔가 머리속만으로 굴리는건 진짜 한계가 있는데? ㅋㅋㅋㅋ

Sudoku
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5294 Accepted: 1578

Description

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

. 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 .

Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input

The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

Output

For each test case, print a line representing the completed Sudoku puzzle.

Sample Input

.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

Sample Output

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

Source

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

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

댓글을 달아 주세요

흑백 채색
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. 규칙이 분명 있을터인듸

Black and white painting
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2092 Accepted: 1396

Description

You are visiting the Centre Pompidou which contains a lot of modern paintings. In particular you notice one painting which consists solely of black and white squares, arranged in rows and columns like in a chess board (no two adjacent squares have the same colour). By the way, the artist did not use the tool of problem A to create the painting.

Since you are bored, you wonder how many 8 × 8 chess boards are embedded within this painting. The bottom right corner of a chess board must always be white.

Input

The input contains several test cases. Each test case consists of one line with three integers n, m and c. (8 ≤ n, m ≤ 40000), where n is the number of rows of the painting, and m is the number of columns of the painting. c is always 0 or 1, where 0 indicates that the bottom right corner of the painting is black, and 1indicates that this corner is white.

The last test case is followed by a line containing three zeros.

Output

For each test case, print the number of chess boards embedded within the given painting.

Sample Input

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

Sample Output

0
1
2
799700028

Source

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

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

댓글을 달아 주세요

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 비번 까뭇따 ㄱ-

628 - Passwords

Time limit: 3.000 seconds

Having several accounts on several servers one has to remember many passwords. You can imagine a situation when someone forgets one of them. He/she remembers only that it consisted of words x, y and z as well as two digits: one at the very beginning and the other one at the end of the password.


Your task is to write a program which will generate all possible password on the basis of given dictionary and set of rules. For the example given above the dictionary contains three words:
x, y, z, and the rule is given as 0#0 what stands for SPMamp<digit><word_from_the_dictionary><digit>&.

Input 

First line contains a number of words in the dictionary (n). The words themselves are given in n consecutive lines. The next line contains number of rules (m). Similarly consecutive m lines contain rules. Each rule consists of characters `#' and `0' given in arbitrary order. The character `#' stands for word from the dictionary whilst the character `0' stands for a digit.

Input data may contain many sets of dictionaries with rules attached two them.

Output 

For each set `dictionary + rules' you should output two hyphens followed by a linebreak and all matching passwords given in consecutive lines. Passwords should be sorted by rules what means that first all passwords matching the first rule and all words must be given, followed by passwords matching the second rule and all words, etc. Within set of passwords matching a word and a rule an ascending digit order must be preserved.


Assumptions: A number of words in the dictionary is greater than 0 and smaller or equal to 100 ( $0 < n \le 100$). Length of the word is greater than 0 and smaller than 256. A word may contain characters `
A'..`Z',`a'..`z',`0'..`9'.A number of rules is smaller than 1000, and a rule is shorter that 256 characters. A character `0' may occur in the rule no more than 7 times, but it has to occur at least once. The character `#' is not mandatory meaning there can be no such characters in the rule.

Sample Input 

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

Sample Output 

--
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 > Original problem' 카테고리의 다른 글

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

댓글을 달아 주세요

서로 다른 두 소수의 합
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. 하나하나 다 쑤셔넣어서는 가망이 없구먼 ㄱ-

Sum of Different Primes
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 2398 Accepted: 1474

Description

A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integers n and k, you should count the number of ways to express n as a sum of k different primes. Here, two ways are considered to be the same if they sum up the same set of the primes. For example, 8 can be expressed as 3 + 5 and 5 + 3 but the are not distinguished.

When n and k are 24 and 3 respectively, the answer is two because there are two sets {2, 3, 19} and {2, 5, 17} whose sums are equal to 24. There are not other sets of three primes that sum up to 24. For n = 24 and k = 2, the answer is three, because there are three sets {5, 19}, {7, 17} and {11, 13}. For n = 2 and k = 1, the answer is one, because there is only one set {2} whose sum is 2. For n = 1 and k = 1, the answer is zero. As 1 is not a prime, you shouldn’t count {1}. For n = 4 and k = 2, the answer is zero, because there are no sets of two different primes whose sums are 4.

Your job is to write a program that reports the number of such ways for the given n and k.

Input

The input is a sequence of datasets followed by a line containing two zeros separated by a space. A dataset is a line containing two positive integers n and kseparated by a space. You may assume that n ≤ 1120 and k ≤ 14.

Output

The output should be composed of lines, each corresponding to an input dataset. An output line should contain one non-negative integer indicating the number of the ways for n and k specified in the corresponding dataset. You may assume that it is less than 231.

Sample Input

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

Sample Output

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

Source

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

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

댓글을 달아 주세요

썩은 밧줄
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

댓글을 달아 주세요

Rotten Ropes
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4023 Accepted: 2620

Description

Suppose we have n ropes of equal length and we want to use them to lift some heavy object. A tear-off weight t is associated to each rope, that is, if we try to lift an object, heavier than t with that rope, it will tear off. But we can fasten a number of ropes to the heavy object (in parallel), and lift it with all the fastened ropes. When using k ropes to lift a heavy object with weight w, we assume that each of the k ropes, regardless of its tear-off weight, is responsible for lifting a weight of w/k. However, if w/k > t for some rope with tear-off weight of t, that rope will tear off. For example, three ropes with tear-off weights of 1, 10, and 15, when all three are fastened to an object, can not lift an object with weight more than 3, unless the weaker one tears-off. But the second rope, may lift by itself, an object with weight at most 10. Given the tear-off weights of n ropes, your task is to find the weight of the heaviest object that can be lifted by fastening a subset of the given ropes without any of them tearing off.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 1000) which is the number of ropes. Following the first line, there is a single line containing n integers between 1 and 10000 which are the tear-off weights of the ropes, separated by blank characters.

Output

Each line of the output should contain a single number, which is the largest weight that can be lifted in the corresponding test case without tearing off any rope chosen.

Sample Input

2
3
10 1 15
2
10 15

Sample Output

20
20

Source

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

UVa 628. Passwords  (0) 2011.03.23
PKU 3132. Sum of Different Primes  (0) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (0) 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.

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

Jumping Cows
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4560 Accepted: 2761

Description

Farmer John's cows would like to jump over the moon, just like the cows in their favorite nursery rhyme. Unfortunately, cows can not jump. 

The local witch doctor has mixed up P (1 <= P <= 150,000) potions to aid the cows in their quest to jump. These potions must be administered exactly in the order they were created, though some may be skipped. 

Each potion has a 'strength' (1 <= strength <= 500) that enhances the cows' jumping ability. Taking a potion during an odd time step increases the cows' jump; taking a potion during an even time step decreases the jump. Before taking any potions the cows' jumping ability is, of course, 0. 

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. 

Determine which potions to take to get the highest jump.

Input

* Line 1: A single integer, P 

* Lines 2..P+1: Each line contains a single integer that is the strength of a potion. Line 2 gives the strength of the first potion; line 3 gives the strength of the second potion; and so on. 

Output

* Line 1: A single integer that is the maximum possible jump. 

Sample Input

8
7
2
1
8
4
3
5
6

Sample Output

17

Source

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

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

댓글을 달아 주세요

속임수 카드놀이
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

댓글을 달아 주세요

Card Trick
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2541 Accepted: 1854

Description

The magician shuffles a small pack of cards, holds it face down and performs the following procedure:

  1. The top card is moved to the bottom of the pack. The new top card is dealt face up onto the table. It is the Ace of Spades.
  2. Two cards are moved one at a time from the top to the bottom. The next card is dealt face up onto the table. It is the Two of Spades.
  3. Three cards are moved one at a time…
  4. This goes on until the nth and last card turns out to be the n of Spades.

This impressive trick works if the magician knows how to arrange the cards beforehand (and knows how to give a false shuffle). Your program has to determine the initial order of the cards for a given number of cards, 1 ≤ n ≤ 13.

Input

On the first line of the input is a single positive integer, telling the number of test cases to follow. Each case consists of one line containing the integer n.

Output

For each test case, output a line with the correct permutation of the values 1 to n, space separated. The first number showing the top card of the pack, etc…

Sample Input

2
4
5

Sample Output

2 1 4 3
3 1 4 5 2

Source

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

PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (0) 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. 왠지 이거랑 유사한 문제를 전에 풀었던 것 같은데

    기분탓인가? -_-;

Cow Bowling
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7685 Accepted: 5014

Description

The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this: 

          7


3 8

8 1 0

2 7 4 4

4 5 2 6 5
Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame. 

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input

Line 1: A single integer, N 

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output

Line 1: The largest sum achievable using the traversal rules

Sample Input

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

Sample Output

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 > Original problem' 카테고리의 다른 글

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

댓글을 달아 주세요

재빠른 거스름돈 주기
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

댓글을 달아 주세요

Quick Change
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3979 Accepted: 2914

Description

J.P. Flathead’s Grocery Store hires cheap labor to man the checkout stations. The people he hires (usually high school kids) often make mistakes making change for the customers. Flathead, who’s a bit of a tightwad, figures he loses more money from these mistakes than he makes; that is, the employees tend to give more change to the customers than they should get.

Flathead wants you to write a program that calculates the number of quarters ($0.25), dimes ($0.10), nickels ($0.05) and pennies ($0.01) that the customer should get back. Flathead always wants to give the customer’s change in coins if the amount due back is $5.00 or under. He also wants to give the customers back the smallest total number of coins. For example, if the change due back is $1.24, the customer should receive 4 quarters, 2 dimes, 0 nickels, and 4 pennies.

Input

The first line of input contains an integer N which is the number of datasets that follow. Each dataset consists of a single line containing a single integer which is the change due in cents, C, (1 ≤ C ≤ 500).

Output

For each dataset, print out the dataset number, a space, and the string:

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

Where Q is he number of quarters, D is the number of dimes, n is the number of nickels and P is the number of pennies.

Sample Input

3
124
25
194

Sample Output

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 > Original problem' 카테고리의 다른 글

PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (0) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (0) 2010.07.24
PKU 1050. To the Max  (0) 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

댓글을 달아 주세요

Error Correction
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3990 Accepted: 2641

Description

A boolean matrix has the parity property when each row and each column has an even sum, i.e. contains an even number of bits which are set. Here's a 4 x 4 matrix which has the parity property: 
1 0 1 0

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

The sums of the rows are 2, 0, 4 and 2. The sums of the columns are 2, 2, 2 and 2. 
Your job is to write a program that reads in a matrix and checks if it has the parity property. If not, your program should check if the parity property can be established by changing only one bit. If this is not possible either, the matrix should be classified as corrupt. 

Input

The input will contain one or more test cases. The first line of each test case contains one integer n (n<100), representing the size of the matrix. On the next n lines, there will be n integers per line. No other integers than 0 and 1 will occur in the matrix. Input will be terminated by a value of 0 for n.

Output

For each matrix in the input file, print one line. If the matrix already has the parity property, print "OK". If the parity property can be established by changing one bit, print "Change bit (i,j)" where i is the row and j the column of the bit to be changed. Otherwise, print "Corrupt".

Sample Input

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

Sample Output

OK
Change bit (2,3)
Corrupt

Source

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

PKU 3176. Cow Bowling  (0) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (0) 2010.07.24
PKU 1050. To the Max  (0) 2010.05.29
PKU 1422. Air Raid  (0) 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. 이건 컴파일 안하고는 못풀겠다.... 일단 쥐쥐

341 - Non-Stop Travel

Time limit: 3.000 seconds

 Non-Stop Travel 

David hates to wait at stop signs, yield signs and traffic signals while driving. To minimize this aggravation, he has prepared maps of the various regions in which he frequently drives, and measured the average delay (in seconds) at each of the various intersections in these regions. He wants to find the routes between specified points in these regions which minimize his delay at intersections (regardless of the total distance he has to drive to avoid delays), and has enlisted your assistance in this effort.

Input

For each region, David provides you with a map. The map data first identifies some number of intersections, NI. The regions never include more than 10 intersections. The intersections in each region are numbered sequentially, starting with the number one (1). For each intersection, in turn, the input then specifies the number of streets leading away from the intersection, and for each such street, the number of the intersection to which the street leads, and the average delay, in seconds, that David encounters at that intersection. Following the data for the last intersection in a region there appear the numbers associated with the intersections where David wants to start and end his drive. The entire input consists of a sequence of maps, followed by the single integer zero (0).

Output

For each region, in order, print a single line of output which contains the region number (they, too, are sequentially numbered, starting with 1), a list of the intersection numbers David will encounter in the route with minimum average delay, and the average number of seconds he will be delayed while travelling this route. A suitable format is shown in the example below.

Notes

  1. There will always be a unique route with the minimum average delay in each region.
  2. A street from intersection I to intersection J is one-way. To represent a two-way street from I to J, the map must also include a route from intersection J to intersection I.
  3. There will never be more than one route directly from intersection I to intersection J.

Example

Suppose David wants to travel from intersection 2 to intersection 4 in the region shown in the following map:

                +---------------+                   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

The input and output for this example is shown as the first case in the Sample Input and Sample Output shown on the next page.

Sample Input

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

Sample Output

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 > Original problem' 카테고리의 다른 글

PKU 3085. Quick Change  (0) 2010.10.05
PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (0) 2010.07.24
PKU 1050. To the Max  (0) 2010.05.29
PKU 1422. Air Raid  (0) 2010.04.30
PKU 2844. Sum and Product. 스풰샬 스퉤이지~  (0) 2010.04.29
posted by Sparking

댓글을 달아 주세요

제일 크게
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. 슈봐 새 문제 이거였어?;; 합과곱 먼저 풀고 한다는게;

To the Max
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 20504 Accepted: 10588

Description

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. 
As an example, the maximal sub-rectangle of the array: 

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 
is in the lower left corner: 

9 2 
-4 1 
-1 8 
and has a sum of 15. 

Input

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

Output

Output the sum of the maximal sub-rectangle.

Sample Input

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

8  0 -2

Sample Output

15

Source

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

PKU 2260. Error Correction  (0) 2010.09.06
UVa 341. Non-Stop Travel  (0) 2010.07.24
PKU 1050. To the Max  (0) 2010.05.29
PKU 1422. Air Raid  (0) 2010.04.30
PKU 2844. Sum and Product. 스풰샬 스퉤이지~  (0) 2010.04.29
PKU 2245. Lotto  (0) 2010.03.16
posted by Sparking

댓글을 달아 주세요

공습
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

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

Air Raid
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 2879 Accepted: 1701

Description

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles. 

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper. 

Input

Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format: 

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

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections. 

There are no blank lines between consecutive sets of data. Input data are correct. 

Output

The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town. 

Sample Input

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

Sample Output

2
1

Source

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

UVa 341. Non-Stop Travel  (0) 2010.07.24
PKU 1050. To the Max  (0) 2010.05.29
PKU 1422. Air Raid  (0) 2010.04.30
PKU 2844. Sum and Product. 스풰샬 스퉤이지~  (0) 2010.04.29
PKU 2245. Lotto  (0) 2010.03.16
PKU 2390. Bank Interest  (0) 2010.03.02
posted by Sparking

댓글을 달아 주세요

복권
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

댓글을 달아 주세요

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

Description

In the German Lotto you have to select 6 numbers from the set {1,2,...,49}. A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S = {1,2,3,5,8,13,21,34} there are 28 possible games: [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]. 

Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S. 

Input

The input will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending order. Input will be terminated by a value of zero (0) for k.

Output

For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.

Sample Input

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

Sample Output

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 > Original problem' 카테고리의 다른 글

PKU 1422. Air Raid  (0) 2010.04.30
PKU 2844. Sum and Product. 스풰샬 스퉤이지~  (0) 2010.04.29
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

댓글을 달아 주세요

Bank Interest
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 8868 Accepted: 5327

Description

Farmer John made a profit last year! He would like to invest it well but wonders how much money he will make. He knows the interest rate R (an integer between 0 and 20) that is compounded annually at his bank. He has an integer amount of money M in the range 100..1,000,000. He knows how many years Y (range: 0..400) he intends to invest the money in the bank. Help him learn how much money he will have in the future by compounding the interest for each year he saves. Print an integer answer without rounding. Answers for the test data are guaranteed to fit into a signed 32 bit integer.

Input

* Line 1: Three space-separated integers: R, M, and Y

Output

* Line 1: A single integer that is the number of dollars FJ will have after Y years.

Sample Input

5 5000 4

Sample Output

6077

Hint

INPUT DETAILS: 

5% annual interest, 5000 money, 4 years 

OUTPUT DETAILS: 

Year 1: 1.05 * 5000 = 5250 
Year 2: 1.05 * 5250 = 5512.5 
Year 3: 1.05 * 5512.50 = 5788.125 
Year 4: 1.05 * 5788.125 = 6077.53125 
The integer part of 6077.53125 is 6077.

Source

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

PKU 2844. Sum and Product. 스풰샬 스퉤이지~  (0) 2010.04.29
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  (0) 2009.12.12
posted by Sparking

댓글을 달아 주세요