태터데스크 관리자

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

태터데스크 메시지

저장하였습니다.
블로그 이미지
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 31      

Notice

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

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

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

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

  동전 나누기

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


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


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


최대 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

  Dividing coins 

It's commonly known that the Dutch have invented copper-wire. Two Dutch men were fighting over a nickel, which was made of copper. They were both so eager to get it and the fighting was so fierce, they stretched the coin to great length and thus created copper-wire.


Not commonly known is that the fighting started, after the two Dutch tried to divide a bag with coins between the two of them. The contents of the bag appeared not to be equally divisible. The Dutch of the past couldn't stand the fact that a division should favour one of them and they always wanted a fair share to the very last cent. Nowadays fighting over a single cent will not be seen anymore, but being capable of making an equal division as fair as possible is something that will remain important forever...


That's what this whole problem is about. Not everyone is capable of seeing instantly what's the most fair division of a bag of coins between two persons. Your help is asked to solve this problem.


Given a bag with a maximum of 100 coins, determine the most fair division between two persons. This means that the difference between the amount each person obtains should be minimised. The value of a coin varies from 1 cent to 500 cents. It's not allowed to split a single coin.

Input 

A line with the number of problems n, followed by n times:
  • a line with a non negative integer m (m ≤ 100) indicating the number of coins in the bag
  • a line with m numbers separated by one space, each number indicates the value of a coin.

Output 

The output consists of n lines. Each line contains the minimal positive difference between the amount the two persons obtain when they divide the coins from the corresponding bag.

Sample Input  

2
3
2 3 5
4
1 2 4 6

Sample Output 

0
1



Miguel A. Revilla 
1998-03-10

'PKU & UVa problems > Original 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  (0) 2009.12.12
PKU 3372. Candy Distribution  (0) 2009.11.25
PKU 3224. Go for Lab Cup!  (0) 2009.11.09
PKU 1989. The Cow Lineup  (3) 2009.10.27
posted by Sparking
2009.10.18 21:41 Solutions/Dlbo's Solution


아흠.

간만에 솔루션 올립니다만,

안푼 문제들 다 이미 풀어본 문제인듯;

별거 없고 배열을 이용해서 서로 매치시켜 더해버리면 됩니다 -_-;
posted by Lonewolf dlbo
TAG pku, UVA
2009.07.26 18:48 Solutions/Fanta's Solution
# Problem Verdict Language Run Time Submission Date
7273761 300 Maya Calendar Accepted ANSI C 0.008 2009-07-26 09:43:44

haab력을 일수로 계산해서 다시 tzolkin으로 변환합니다.

'Solutions > Fanta's Solution' 카테고리의 다른 글

PKU 2853. Sequence Sum Possibili. AC  (0) 2009.12.19
PKU 2000. Gold Coins. AC  (0) 2009.11.01
UVa 300. Maya Calendar. AC  (0) 2009.07.26
PKU 3673. Cow Multiplication. AC  (2) 2009.07.19
PKU 2243. Knight Moves. AC  (0) 2009.05.31
PKU 1454, UVa 324. Factorial Frequencies. AC  (3) 2009.05.23
posted by 지환태
TAG UVA

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

300 - Maya Calendar

Time limit: 3.000 seconds

 Maya Calendar 

During his last sabbatical, professor M. A. Ya made a surprising discovery about the old Maya calendar. From an old knotted message, professor discovered that the Maya civilization used a 365 day long year, called Haab, which had 19 months. Each of the first 18 months was 20 days long, and the names of the months were pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu. Instead of having names, the days of the months were denoted by numbers starting from 0 to 19. The last month of Haab was called uayet and had 5 days denoted by numbers 0, 1, 2, 3, 4. The Maya believed that this month was unlucky, the court of justice was not in session, the trade stopped, people did not even sweep the floor.

For religious purposes, the Maya used another calendar in which the year was called Tzolkin (holly year). The year was divided into thirteen periods, each 20 days long. Each day was denoted by a pair consisting of a number and the name of the day. They used 20 names: imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau and 13 numbers; both in cycles.

Notice that each day has an unambiguous description. For example, at the beginning of the year the days were described as follows:

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, and again in the next period 8 imix, 9 ik, 10 akbal...

Years (both Haab and Tzolkin) were denoted by numbers 0, 1, ..., where the number 0 was the beginning of the world. Thus, the first day was:

Haab: 0. pop 0

Tzolkin: 1 imix 0

Help professor M. A. Ya and write a program for him to convert the dates from the Haab calendar to the Tzolkin calendar.

Input

The date in Haab is given in the following format:

NumberOfTheDay. Month Year

The first line of the input file contains the number of the input dates in the file. The next n lines contain n dates in the Haab calendar format, each in separate line. The year is smaller then 5000.

Output

The date in Tzolkin should be in the following format:

Number NameOfTheDay Year

The first line of the output file contains the number of the output dates. In the next n lines, there are dates in the Tzolkin calendar format, in the order corresponding to the input dates.

Sample Input

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

Sample Output

3
3 chuen 0
1 imix 0
9 cimi 2801

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

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

324 - Factorial Frequencies

Time limit: 3.000 seconds

Factorial Frequencies 

불 보듯 뻔히 보이는 사업의 하락세를 보강하기 위하여, Madam Pheonix는 그녀의 고객들에게 여러 종류의, 수를 이용한 점 서비스를 하기로 했습니다. 그녀는 십진수로 표현되는 팩토리얼의 각 자리에 있는 숫자들의 개수의 합이, 그들이 겪게 될 미래의 일들의 가짓수를 표현할 수 있다고 믿도록 만들었습니다.그러나 단순한 손금보기와는 다르게, 그녀는 이 수열들을 단숨에 계산하여 알려줄 능력이 되지 못했기에 당신을 고용하여 각 값들을 결정하려 합니다.

n!(n 팩토리얼)의 정의가 1*2*3*...*n임을 잊지 마세요. 그녀가 한 주의 , 한 달의, 혹은 한 해 중의 하루의 숫자를 n으로 놓고 계산하려 하면 당신은 그 숫자의 팩토리얼의 자리수를 계산하여야 하는데, 최대치는 781자리 수인 366! 입니다.

입력과 출력

프로그램에 입력할 데이터는  아주 간단하게, 정수들의 목록인데 이것은 자리수를 계산하기 위해서 필요합니다. 모든 입력값은 0보다 크고 366보다 작거나 같지만, 마지막 정수는 0을 입력해야 합니다. 이 0 의 값을 계산하기 위해 고민하지 마세요. 왜냐하면 이 0은 계산하기 위한 것이 아니라 프로그램이 계산을 멈출 곳을 지정하는 0이니까요. 출력 형식은 꼭 필요하진 않지만, 아래에 주어진 것과 비슷해 보이도록 프로그램을 만드셔야 합니다.

Madam Phoenix는 당신의 노고에 대해 영원히, 혹은 꽤 오랫동안 고마워 할 것이고 어쩌면 일을 잘 했을 때 감사의 의미로 여행을 보내줄 지도 모릅니다!

입력 예시

3
8
100
0

출력 예시

3! --
   (0)    0    (1)    0    (2)    0    (3)    0    (4)    0
   (5)    0    (6)    1    (7)    0    (8)    0    (9)    0
8! --
   (0)    2    (1)    0    (2)    1    (3)    1    (4)    1
   (5)    0    (6)    0    (7)    0    (8)    0    (9)    0
100! --
   (0)   30    (1)   15    (2)   19    (3)   10    (4)   10
   (5)   14    (6)   19    (7)    7    (8)   14

p.s: Lonewolf dlbo 의 의견을 반영, 해석을 수정하였습니다.

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

PKU 1163. The Triangle  (1) 2009.04.04
PKU 2039. To and Fro  (3) 2009.03.25
UVa 324. Factorial Frequencies  (6) 2009.03.17
PKU 1455. Crazy Tea Party  (12) 2009.02.25
PKU 2719. Faulty Odometer  (0) 2009.02.16
UVa 200. Rare Order  (9) 2009.02.07
posted by Sparking

324 - Factorial Frequencies

Time limit: 3.000 seconds

Factorial Frequencies 

In an attempt to bolster her sagging palm-reading business, Madam Phoenix has decided to offer several numerological treats to her customers. She has been able to convince them that the frequency of occurrence of the digits in the decimal representation of factorials bear witness to their futures. Unlike palm-reading, however, she can't just conjure up these frequencies, so she has employed you to determine these values.

Recall that the definition of n! (that is, n factorial) is just 1*2*3*...*n . As she expects to use either the day of the week, the day of the month, or the day of the year as the value of n, you must be able to determine the number of occurrences of each decimal digit in numbers as large as 366 factorial (366!), which has 781 digits.

Input and Output

The input data for the program is simply a list of integers for which the digit counts are desired. All of these input values will be less than or equal to 366 and greater than 0, except for the last integer, which will be zero. Don't bother to process this zero value; just stop your program at that point. The output format isn't too critical, but you should make your program produce results that look similar to those shown below.

Madam Phoenix will be forever (or longer) in your debt; she might even give you a trip if you do your job well!

Sample Input

3
8
100
0

Sample Output

3! --
   (0)    0    (1)    0    (2)    0    (3)    0    (4)    0
   (5)    0    (6)    1    (7)    0    (8)    0    (9)    0
8! --
   (0)    2    (1)    0    (2)    1    (3)    1    (4)    1
   (5)    0    (6)    0    (7)    0    (8)    0    (9)    0
100! --
   (0)   30    (1)   15    (2)   19    (3)   10    (4)   10
   (5)   14    (6)   19    (7)    7    (8)   14    (9)   20

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

PKU 1163. The Triangle  (0) 2009.04.04
PKU 2039. To and Fro  (0) 2009.03.25
UVa 324. Factorial Frequencies  (0) 2009.03.17
PKU 1455. Crazy Tea Party  (2) 2009.02.25
PKU 2719. Faulty Odometer  (0) 2009.02.16
UVa 200. Rare Order  (0) 2009.02.07
posted by Sparking
2009.02.07 22:55 Solutions/Dlbo's Solution


스'뽜'킹님아

살살해염

나 손가락 아파 ㄱ-

----------------------------------------------------------------------------------------------

모니터가 죱내 넓어진 탓에

#define으로 잡은 FUCKYOUSPARKING처럼 긴 이름을 마음놓고 쓰게 됐습니다 -_-

문제 번역 부분에 댓글 단 것 처럼, 유향그래프를 이용해 탐색합니다.

그 부분이 이디냐 하면...

바로 fuckingJAVA 함수입니다.

-_-...

죄송해요.

자바로 UVa 문제 풀다 보니 승질 뻗치더라구요;;;

여서 제가 메인함수에서 n = 1로 두고, 아래서 n이 1이냐 아니느냐로 CppIsBest 함수를 호출했는데요.

CppIsBest 함수는 고문자 순으로 출력하게 하는 함수입니다.

만약 n이 1이라면, 한줄 딸랑 받은거니 정리 하고 자시고 없어서

그냥 prev를 고대로 찍어버림 되니까요.

초기화가 귀찮아서 그냥 prev, curr를 전역변수로(이 경우 NULL 혹은 0으로 자동 초기화 됩니다.)

선언해 버렸습니다.

degree는 해당 노드에서의 전체 차수를 의미하고, out_degree는 해당 노드에서의 진출 차수를 의미합니다.

CppIsBest 함수의 초반부에 i가 0부터 FUCKYOUSPARKING까지 돌 때는

다름아니라... 차수를 가지고 가장 큰 문자열이 뭔지를 판별합니다.

이후 maximum까지 돌때 고(?)문자 순으로 찍지요.

두개의 내부 루프중 첫번째는 0부터 maximum까지 돌면서

j번째 문자의 진출차수가 0이라면 그걸 출력해주는걸 반복합니다.

두번째 내부 루프는 해당 글자들의 차수를 원상복구 시켜주는 역할을 하지요.

.... 너무 횡설수설로 써놨네.

여튼, 유향그래프로 만들어놓고 진출차수를 이용해 체크해 순서를 "예상"하는 방법입니다.

-ㅁ-;;;;;;

외의 방법으로는 2차원 배열에 입력을 다 쑤셔넣고는

큐에 또 우르르.... 넣고

큐에서 새로운 문자를 만날때까지 꺼내서 얹어놓고...

다시 우겨넣고...

이리 반복하다가 큐에 남은 녀석들을 그냥 차례로 출력하는 방법도 있습니다만,

그건 구현하기 귀찮았으므로 -_-

------------------------------------------------------------------------------------

스'뽜'킹군.

하드해 하드해 -ㅁ- 어려웠다구
posted by Lonewolf dlbo

Rare Order 


한 희귀 서적 수집가가 최근에 어떤 책이 영어와 같은 문자로 이루어져 있지만 낯설은 언어로 적혀있는 것을 발견하였습니다.  짧은 색인이 있지만, 영어의 알파벳과 같이 생각하지 못할만큼 다른 순서로 적혀있었습니다. 수집가는 색인을 이용하여 문자의 순서를 확인해보려 했지만 지루함과 당혹감을 느끼며 포기했습니다.

당신은 수집가의 작업을 마무리할 프로그램을 작성해야 합니다. 특히, 이미 특정 방법에 의해 짜여진 문자열들을 분류하고 어떤 순서인지를 알아내야 합니다.

입력


입력은 대문자로, 한 줄에 한 문자열이 들어갑니다. 각 문자열은 최대 20개의 문자를 포함할 수 있습니다. 목록의 마지막은 '#' 문자를 사용합니다. 모든 문자가 사용되어야 하는건 아니지만, 목록에 사용된 문자들 모두가 특정 방법으로 짜여진 순서라는 것을 설명할 수 있어야 합니다.

출력


출력은 대문자로, 입력할 데이터 파일에서 생성된 모든 문자를 순서에 따라 하나씩 나열합니다.

입력 예시

XWY
ZX
ZXY
ZXW
YWWX
#

출력 예시

XZYW

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

PKU 1455. Crazy Tea Party  (12) 2009.02.25
PKU 2719. Faulty Odometer  (0) 2009.02.16
UVa 200. Rare Order  (9) 2009.02.07
PKU 2551. Ones  (5) 2009.01.21
PKU 1904. King's Quest  (8) 2009.01.15
PKU 1953. World Cup Noise  (0) 2009.01.09
posted by Sparking

Rare Order 

A rare book collector recently discovered a book written in an unfamiliar language that used the same characters as the English language. The book contained a short index, but the ordering of the items in the index was different from what one would expect if the characters were ordered the same way as in the English alphabet. The collector tried to use the index to determine the ordering of characters (i.e., the collating sequence) of the strange alphabet, then gave up with frustration at the tedium of the task.

You are to write a program to complete the collector's work. In particular, your program will take a set of strings that has been sorted according to a particular collating sequence and determine what that sequence is.

Input

The input consists of an ordered list of strings of uppercase letters, one string per line. Each string contains at most 20 characters. The end of the list is signalled by a line with the single character `#'. Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used.

Output

Your output should be a single line containing uppercase letters in the order that specifies the collating sequence used to produce the input data file.

Sample Input

XWY
ZX
ZXY
ZXW
YWWX
#

Sample Output

XZYW

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

PKU 1455. Crazy Tea Party  (2) 2009.02.25
PKU 2719. Faulty Odometer  (0) 2009.02.16
UVa 200. Rare Order  (0) 2009.02.07
PKU 2551. Ones  (0) 2009.01.21
PKU 1904. King's Quest  (2) 2009.01.15
PKU 1953. World Cup Noise  (0) 2009.01.09
posted by Sparking
2008.12.15 19:24 Solutions/Fanta's Solution

Run ID User Problem Result Memory Time Language Code Length Submit Time
4487384 jht009 1145 Accepted 200K 16MS C 558B 2008-12-15 18:12:21

지각인가요
알콜코딩 성공 ㅎㅎㅎㅎ
취하지도 않고 냄새만 맡아가면서 해봤어요.
사람이 할 짓은 아닌 듯 ㅇㅅㅇ
술 왜마시죠??????????

'Solutions > Fanta's Solution' 카테고리의 다른 글

PKU 1089. Intervals. AC  (4) 2008.12.26
PKU 1089. Intervals. TLE  (1) 2008.12.23
UVa. 112, PKU 1145. Tree Summing. AC  (4) 2008.12.15
PKU 3438. Look and Say. AC  (4) 2008.12.05
PKU 2521. How much did the businessman lose. AC  (2) 2008.12.02
PKU 2636. Electrical Outlets. AC  (0) 2008.11.28
posted by 지환태
TAG pku, UVA
prev 1 next