태터데스크 관리자

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

태터데스크 메시지

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

댓글을 달아 주세요

서로 다른 두 소수의 합
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

댓글을 달아 주세요

제일 크게
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

댓글을 달아 주세요

2010.05.16 21:09 Solutions/Fanta's Solution

간단한 백트래킹 문제네요.

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

PKU 2245. Lotto. AC  (0) 2010.05.16
PKU 2390. Bank Interest. AC  (0) 2010.05.16
PKU 2551. Ones. AC  (0) 2010.05.10
PKU 2551. Ones. TLE  (2) 2010.05.09
PKU 3372. Candy Distribution. AC  (1) 2010.02.14
PKU 3224. Go for Lab Cup! AC  (0) 2010.02.01
posted by 지환태
TAG pku

댓글을 달아 주세요

2010.05.10 23:55 Solutions/Fanta's Solution
오버플로우를 방지하기 위해
(a * b) % c = ((a % c) * (b % c)) % c
(a + b) % c = ((a % c) + (b % c)) % c
를 사용했습니다.


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

PKU 2245. Lotto. AC  (0) 2010.05.16
PKU 2390. Bank Interest. AC  (0) 2010.05.16
PKU 2551. Ones. AC  (0) 2010.05.10
PKU 2551. Ones. TLE  (2) 2010.05.09
PKU 3372. Candy Distribution. AC  (1) 2010.02.14
PKU 3224. Go for Lab Cup! AC  (0) 2010.02.01
posted by 지환태
TAG pku

댓글을 달아 주세요

2010.05.09 15:38 Solutions/Fanta's Solution
21을 예로들면

1 = 1
1 + 10 = 11
1 + 10 + 100 = 105 + 6
1 + 10 + 100 + 1000 = 105 + 21 + 966 + 19
1 + 10 + 100 + 1000 + 10000 = 105 + 21 + 966 + 21 + 9996 + 2
1 + 10 + 100 + 1000 + 10000 + 100000 = 105 + 21 + 966 + 9996 + 21 + 99981

오버플로우를 생각 못했네요

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

PKU 2390. Bank Interest. AC  (0) 2010.05.16
PKU 2551. Ones. AC  (0) 2010.05.10
PKU 2551. Ones. TLE  (2) 2010.05.09
PKU 3372. Candy Distribution. AC  (1) 2010.02.14
PKU 3224. Go for Lab Cup! AC  (0) 2010.02.01
PKU 2845. 01000001. AC  (0) 2010.01.25
posted by 지환태
TAG pku

댓글을 달아 주세요

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

    11111과 111111의 우변이 잘못되었네요 '-';

    11111 = 105 + 21 + "966" + 21 + 9996 + 2

    111111 = 105 + 21 + "966 + 21" + 9996 + 21 + 99981

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

댓글을 달아 주세요

간단한 화학문제
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

댓글을 달아 주세요