태터데스크 관리자

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

태터데스크 메시지

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

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

댓글을 달아 주세요

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

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

댓글을 달아 주세요

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

댓글을 달아 주세요

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

댓글을 달아 주세요

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

댓글을 달아 주세요

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

댓글을 달아 주세요

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

댓글을 달아 주세요

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

댓글을 달아 주세요

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

 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

댓글을 달아 주세요

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

댓글을 달아 주세요

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

댓글을 달아 주세요


For a sequence of N integers A1, A2, ... , AN, we can calculate their sum S and product P easily. With given N, S and P, can you find out the sequence A1, A2, ... , AN?

Input

The input only contains a line with three integers N, S and P. Here N is positive and not more than 1000000, and the absolute values of S and P do not exceed 150000000.

Output

Just output "No solution" if there is no such sequence, or you may output any solution with N integers A1, A2, ... , AN, separated by just one space.

Sample Input

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

Sample Output

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

Source

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

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
PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
posted by Lonewolf dlbo

댓글을 달아 주세요

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

댓글을 달아 주세요

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

댓글을 달아 주세요

A Simple Question of Chemistry
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4199 Accepted: 2809

Description

Your chemistry lab instructor is a very enthusiastic graduate student who clearly has forgotten what their undergraduate Chemistry 101 lab experience was like. Your instructor has come up with the brilliant idea that you will monitor the temperature of your mixture every minute for the entire lab. You will then plot the rate of change for the entire duration of the lab. 

Being a promising computer scientist, you know you can automate part of this procedure, so you are writing a program you can run on your laptop during chemistry labs. (Laptops are only occasionally dissolved by the chemicals used in such labs.) You will write a program that will let you enter in each temperature as you observe it. The program will then calculate the difference between this temperature and the previous one, and print out the difference. Then you can feed this input into a simple graphing program and finish your plot before you leave the chemistry lab. 

Input

The input is a series of temperatures, one per line, ranging from -10 to 200. The temperatures may be specified up to two decimal places. After the final observation, the number 999 will indicate the end of the input data stream. All data sets will have at least two temperature observations. 

Output

Your program should output a series of differences between each temperature and the previous temperature. There is one fewer difference observed than the number of temperature observations (output nothing for the first temperature). Differences are always output to two decimal points, with no leading zeroes (except for the ones place for a number less than 1, such as 0.01) or spaces. After the final output, print a line with "End of Output". 

Sample Input

10.0
12.05
30.25
20
999

Sample Output

2.05
18.20
-10.25
End of Output

Source

'PKU & UVa problems > Original 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  (0) 2009.12.12
PKU 3372. Candy Distribution  (0) 2009.11.25
posted by Sparking

댓글을 달아 주세요

Number-guessing Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3240 Accepted: 2406

Description

Larry likes playing the number-guessing game.

Two players are needed in a game. Suppose they are X and Y, and X presents a number for Y to guess. Firstly, X chooses a number with four different digits, keeping it in mind, and tells Y to start guessing. Every time Y has guessed, X should give out *A*B to show Y how close to the number his answer is. Here the symbol * stands for a number, and the number before A is the number of digits in Y's answer with both correct value and position. The number before B is the number of digits in Y's answer with correct value but incorrect position.

For example, if X chooses the number 5204, and Y guesses 4902, then X should give out 1A2B, in which 1A corresponds for digit 0 with both correct value and position and 2B corresponds for digit 2 and 4 with correct value but incorrect position. Then Y will go on guessing according to 1A2B that X presents him until he gets the totally correct number 5204 (when X shows him 4A0B).

Now you are given two numbers, and what you need to do is just testing how close they are.

Input

The first line of the input is an integer T which indicates the number of test cases. For each test case, input two numbers. Each number contains four different digits.

Output

For each test case, output *A*B stands for how close the two numbers are.
 

Sample Input

2
5204 4902
0123 3210

Sample Output

1A2B
0A4B

Source

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

PKU 2390. Bank Interest  (0) 2010.03.02
PKU 2871. A Simple Question of Chemistry  (0) 2010.02.26
PKU 3589. Number-guessing Game  (0) 2010.02.01
UVa 562. Dividing Coins  (0) 2009.12.12
PKU 3372. Candy Distribution  (0) 2009.11.25
PKU 3224. Go for Lab Cup!  (0) 2009.11.09
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

댓글을 달아 주세요

Candy Distribution
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3678 Accepted: 1902

Description

N children standing in circle who are numbered 1 through N clockwise are waiting their candies. Their teacher distributes the candies by in the following way:

First the teacher gives child No.1 and No.2 a candy each. Then he walks clockwise along the circle, skipping one child (child No.3) and giving the next one (child No.4) a candy. And then he goes on his walk, skipping two children (child No.5 and No.6) and giving the next one (child No.7) a candy. And so on.

Now you have to tell the teacher whether all the children will get at least one candy?

Input

The input consists of several data sets, each containing a positive integer N (2 ≤ N ≤ 1,000,000,000).

Output

For each data set the output should be either "YES" or "NO".

Sample Input

2
3 
4

Sample Output

YES
NO
YES

Source

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

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
PKU 1547. Clay Bully  (0) 2009.09.24
posted by Sparking

댓글을 달아 주세요

Go for Lab Cup!
Time Limit: 1000MS Memory Limit: 131072K
Total Submissions: 5062 Accepted: 2672

Description

The Lab Cup Table Tennis Competition is going to take place soon among laboratories in PKU. Students from the AI Lab are all extreme enthusiasts in table tennis and hold strong will to represent the lab in the competition. Limited by the quota, however, only one of them can be selected to play in the competition.

To make the selection fair, they agreed on a single round robin tournament, in which every pair of students played a match decided by best of 5 games. The one winning the most matches would become representative of the lab. Now Ava, head of the lab, has in hand a form containing the scores of all matches. Who should she decide on for the competition?

Input

The input contains exactly one test case. The test case starts with a line containing n (2 ≤ n ≤ 100), the number of students in the lab. Then follows an n × n matrix A. Each element in the matrix will be one of 0, 1, 2 and 3. The element at row i and column j, aij, is the number of games won by the ith student in his/her match with the jth student. Exactly one of aij and aji (i  j) is 3 and the other one will be less than 3. All diagonal elements of the matrix are 0’s.

Output

Output the number of the student who won the most matches. In the case of a tie, choose the one numbered the smallest.

Sample Input

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

Sample Output

4

Source

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

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

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
PKU 1547. Clay Bully  (0) 2009.09.24
PKU 2000. Gold Coins  (0) 2009.09.07
posted by Sparking

댓글을 달아 주세요

The Cow Lineup
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 3397 Accepted: 2028

Description

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row.Each cow is labeled with a number in the range 1...K (1 <= K <=10,000) identifying her breed. For example, a line of 14 cows might have these breeds: 
    1 5 3 2 5 1 3 4 4 2 5 1 2 3

Farmer John's acute mathematical mind notices all sorts of properties of number sequences like that above. For instance, he notices that the sequence 3 4 1 3 is a subsequence (not necessarily contiguous) of the sequence of breed IDs above. FJ is curious what is the length of the shortest possible sequence he can construct out of numbers in the range 1..K that is NOT a subsequence of the breed IDs of his cows. Help him solve this problem. 

Input

* Line 1: Two integers, N and K 

* Lines 2..N+1: Each line contains a single integer that is the breed ID of a cow. Line 2 describes cow 1; line 3 describes cow 2; and so on. 

Output

* Line 1: The length of the shortest sequence that is not a subsequence of the input 

Sample Input

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

Sample Output

3

Hint

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

Source

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

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
PKU 1547. Clay Bully  (0) 2009.09.24
PKU 2000. Gold Coins  (0) 2009.09.07
PKU 2853. Sequence Sem Possibilities  (0) 2009.08.20
posted by Sparking

댓글을 달아 주세요

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

    해석 틀린것좀 지적해달래서 봤는데 나도 뭔소린지 잘.. -_-;;

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.12.24 19:39  Addr Edit/Del Reply

    ㅋㅋ 아

    이거 몇시간 전에 이해해서 소스좀 끄적거렸는데

    좀 더럽게 나올듯 ㅋㅋㅋ

Clay Bully
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 4783 Accepted: 2896

Description

Ms. Terry is a pre-school art teacher who likes to have her students work with clay. One of her assignments is to form a lump of clay into a block and then measure the dimensions of the block. However, in every class, there is always one child who insists on taking some clay from some other child. Since Ms. Terry always gives every child in a class the same amount of clay to begin with, you can write a program that helps Ms. Terry find the bully and victim after she measures each child's finished block.

Input

There are one or more classes of students, followed by a final line containing only the value -1. Each class starts with a line containing an integer, n, which is the number of students in the class, followed by n lines of student information. Each line of student information consists of three positive integers, representing the dimensions of the clay block, followed by the student's first name. There can never be more than 9 students nor less than 2 students in any class. Each student's name is at most 8 characters. Ms. Terry always gives each student at most 250 cubic units of clay. There is exactly one bully and one victim in each class.

Output

For each class print a single line exactly as shown in the sample output.

Sample Input

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

Sample Output

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

Source

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

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

댓글을 달아 주세요

Gold Coins
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 11700 Accepted: 7242

Description

The king pays his loyal knight in gold coins. On the first day of his service, the knight receives one gold coin. On each of the next two days (the second and third days of service), the knight receives two gold coins. On each of the next three days (the fourth, fifth, and sixth days of service), the knight receives three gold coins. On each of the next four days (the seventh, eighth, ninth, and tenth days of service), the knight receives four gold coins. This pattern of payments will continue indefinitely: after receiving N gold coins on each of N consecutive days, the knight will receive N+1 gold coins on each of the next N+1 consecutive days, where N is any positive integer. 

Your program will determine the total number of gold coins paid to the knight in any given number of days (starting from Day 1). 

Input

The input contains at least one, but no more than 21 lines. Each line of the input file (except the last one) contains data for one test case of the problem, consisting of exactly one integer (in the range 1..10000), representing the number of days. The end of the input is signaled by a line containing the number 0.

Output

There is exactly one line of output for each test case. This line contains the number of days from the corresponding line of input, followed by one blank space and the total number of gold coins paid to the knight in the given number of days, starting with Day 1.

Sample Input

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

Sample Output

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

Source

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

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

댓글을 달아 주세요

Sequence Sum Possibilities
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3213 Accepted: 2159

Description

Most positive integers may be written as a sum of a sequence of at least two consecutive positive integers. For instance,

6 = 1 + 2 + 3
9 = 5 + 4 = 2 + 3 + 4
but 8 cannot be so written.

Write a program which will compute how many different ways an input number may be written as a sum of a sequence of at least two consecutive positive integers.

Input

The first line of input will contain the number of problem instances N on a line by itself, (1  N  1000) . This will be followed by N lines, one for each problem instance. Each problem line will have the problem number, a single space and the number to be written as a sequence of consecutive positive integers. The second number will be less than 231 (so will fit in a 32-bit integer).

Output

The output for each problem instance will be a single line containing the problem number, a single space and the number of ways the input number can be written as a sequence of consecutive positive integers.

Sample Input

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

Sample Output

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

Source

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

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

댓글을 달아 주세요

Trees
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5383 Accepted: 3713

Description

The road off the east gate of Peking University used to be decorated with a lot of trees. However, because of the construction of a subway, a lot of them are cut down or moved away. Now please help to count how many trees are left. 

Let's only consider one side of the road. Assume that trees were planted every 1m (meter) from the beginning of the road. Now some sections of the road are assigned for subway station, crossover or other buildings, so trees in those sections will be moved away or cut down. Your job is to give the number of trees left. 

For example, the road is 300m long and trees are planted every 1m from the beginning of the road (0m). That's to say that there used to be 301 trees on the road. Now the section from 100m to 200m is assigned for subway station, so 101 trees need to be moved away and only 200 trees are left.

Input

There are several test cases in the input. Each case starts with an integer L (1 <= L < 2000000000) representing the length of the road and M (1 <= M <= 5000) representing the number of sections that are assigned for other use. 

The following M lines each describes a section. A line is in such format: 

Start End 

Here Start and End (0 <= Start <= End <= L) are both non-negative integers representing the start point and the end point of the section. It is confirmed that these sections do not overlap with each other. 

A case with L = 0 and M = 0 ends the input.

Output

Output the number of trees left in one line for each test case.

Sample Input

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

Sample Output

200
300

Source

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

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

댓글을 달아 주세요

Coins
Time Limit: 1000MS Memory Limit: 131072K
Total Submissions: 4206 Accepted: 2615

Description

Snoopy has three coins. One day he tossed them on a table then and tried to flip some of them so that they had either all heads or all tails facing up. After several attempts, he found that regardless of the initial configuration of the coins, he could always achieve the goal by doing exactly two flippings, under the condition that only one coin could be flipped each time and a coin could be flipped more than once. He also noticed that he could never succeed with less than two flippings.

Snoopy then wondered, if he had n coins, was there a minimum number x such that he could do exactly x flippings to satisfy his requirements?

Input

The input contains multiple test cases. Each test case consists of a single positive integer n (n < 10,000) on a separate line. A zero indicates the end of input and should not be processed.

Output

For each test case output a single line containing your answer without leading or trailing spaces. If the answer does not exist, output “No Solution!

Sample Input

2
3
0

Sample Output

No Solution!
2

Source

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

PKU 2853. Sequence Sem Possibilities  (0) 2009.08.20
PKU 2665. Trees  (0) 2009.08.04
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
posted by Sparking

댓글을 달아 주세요

Cow Multiplication
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4984 Accepted: 3304

Description

Bessie is tired of multiplying pairs of numbers the usual way, so she invented her own style of multiplication. In her style, A*B is equal to the sum of all possible pairwise products between the digits of A and B. For example, the product 123*45 is equal to 1*4 + 1*5 + 2*4 + 2*5 + 3*4 + 3*5 = 54. Given two integers A and B (1 ≤ A, B ≤ 1,000,000,000), determine A*B in Bessie's style of multiplication.

Input

* Line 1: Two space-separated integers: A and B.

Output

* Line 1: A single line that is the A*B in Bessie's style of multiplication.

Sample Input

123 45

Sample Output

54

Source

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

PKU 2665. Trees  (0) 2009.08.04
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
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

댓글을 달아 주세요

THE DRUNK JAILER
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10751 Accepted: 6990

Description

A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner in it, and each cell is locked. 
One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the 
hall locking every other cell (cells 2, 4, 6, ?). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He 
repeats this for n rounds, takes a final drink, and passes out. 
Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape. 
Given the number of cells, determine how many prisoners escape jail.

Input

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n. 

Output

For each line, you must print out the number of prisoners that escape when the prison has n cells. 

Sample Input

2
5
100

Sample Output

2
10

Source

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

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
PKU 2840. Big Clock  (0) 2009.05.11
posted by Sparking

댓글을 달아 주세요

prev 1 2 3 next