Description

 http://uva.onlinejudge.org/external/114/11462.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/113/11321.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/107/10763.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/119/11997.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/100/10067.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.

 Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. 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. A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

is in the lower-left-hand corner:

and has the sum of 15.

Input

The input consists of an 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 integers separated by white-space (newlines and spaces). These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on 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

The output is the sum of the maximal sub-rectangle.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Now, your task is to calculate the numbers of the prime numbers between 1 and an integer N.

Input

The input file contains several cases. The first line contains an integer T ( 1 <= T <= 1,000) represent the number of cases. The next T lines, there will be an integer N ( 1 <= N <= 1,000,000) on a single line.

Output

Please output the number of prime numbers between 1 and N.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The only printer in the computer science students' union is experiencing an extremely heavy workload. Sometimes there are a hundred jobs in the printer queue and you may have to wait for hours to get a single page of output.

Because some jobs are more important than others, the Hacker General has invented and implemented a simple priority system for the print job queue. Now, each job is assigned a priority between 1 and 9 (with 9 being the highest priority, and 1 being the lowest), and the printer operates as follows.

• The first job J in queue is taken from the queue.
• If there is some job in the queue with a higher priority than job J, then move J to the end of the queue without printing it.
• Otherwise, print job J (and do not put it back in the queue).

In this way, all those important muffin recipes that the Hacker General is printing get printed very quickly. Of course, those annoying term papers that others are printing may have to wait for quite some time to get printed, but that's life.

Your problem with the new policy is that it has become quite tricky to determine when your print job will actually be completed. You decide to write a program to figure this out. The program will be given the current queue (as a list of priorities) as well as the position of your job in the queue, and must then calculate how long it will take until your job is printed, assuming that no additional jobs will be added to the queue. To simplify matters, we assume that printing a job always takes exactly one minute, and that adding and removing jobs from the queue is instantaneous.

Input

 One line with a positive integer: the number of test cases (at most 100). Then for each test case:

• One line with two integers n and m, where n is the number of jobs in the queue (1 ≤ n ≤ 100) and m is the position of your job (0 ≤ m ≤ n-1). The first position in the queue is number 0, the second is number 1, and so on.
• One line with n integers in the range 1 to 9, giving the priorities of the jobs in the queue. The first integer gives the priority of the first job, the second integer the priority of the second job, and so on.

Output

 For each test case, print one line with a single integer; the number of minutes until your job is completely printed, assuming that no additional print jobs will arrive.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given several segments of line (int the X axis) with coordinates [L_i,R_i]. You are to choose the minimal amount of them, such they would completely cover the segment [0,M].

Input

The first line is the number of test cases, followed by a blank line.

Each test case in the input should contains an integer M(1<=M<=5000), followed by pairs "L_i R_i"(|L_i|, |R_i|<=50000, i<=100000), each on a separate line. Each test case of input is terminated by pair "0 0".

Each test case will be separated by a single line.

Output

For each test case, in the first line of output your programm should print the minimal number of line segments which can cover segment [0,M]. In the following lines, the coordinates of segments, sorted by their left end (L_i), should be printed in the same format as in the input. Pair "0 0" should not be printed. If [0,M] can not be covered by given line segments, your programm should print "0"(without quotes).

Print a blank line between the outputs for two consecutive test cases.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

計算 R = B^P mod M
對相當大的B、P、M請寫一個有效率的演算法來。

Input

每筆測試資料有3行，各有1個整數分別代表B、P、M。
其中 0 <= B <= 2147483647 0 <= P <= 2147483647 1 <= M <= 46340

Output

輸出計算的結果，每筆測試資料一行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. G. works as a tourist guide. His current assignment is to take some tourists from one city to another. Some two-way roads connect the cities. For each pair of neighboring cities there is a bus service that runs only between those two cities and uses the road that directly connects them. Each bus service has a limit on the maximum number of passengers it can carry. Mr. G. has a map showing the cities and the roads connecting them. He also has the information regarding each bus service. He understands that it may not always be possible for him to take all the tourists to the destination city in a single trip. For example, consider the following road map of 7 cities. The edges connecting the cities represent the roads and the number written on each edge indicates the passenger limit of the bus service that runs on that road.


Now, if he wants to take 99 tourists from city 1 to city 7, he will require at least 5 trips, since he has to ride the bus with each group, and the route he should take is : 1 - 2 - 4 - 7.

But, Mr. G. finds it difficult to find the best route all by himself so that he may be able to take all the tourists to the destination city in minimum number of trips. So, he seeks your help.

Input

The input will contain one or more test cases. The first line of each test case will contain two integers: N (N<= 100) and R representing respectively the number of cities and the number of road segments. Then R lines will follow each containing three integers: C₁, C₂ and P. C₁ and C₂ are the city numbers and P (P> 1) is the limit on the maximum number of passengers to be carried by the bus service between the two cities. City numbers are positive integers ranging from 1 to N. The (R + 1)-th line will contain three integers: S, D and T representing respectively the starting city, the destination city and the number of tourists to be guided.

The input will end with two zeroes for N and R.

Output

For each test case in the input first output the scenario number. Then output the minimum number of trips required for this case on a separate line. Print a blank line after the output of each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 ≤ n ≤ 10⁵. Then follow n integers h₁, ..., h_n, where 0 ≤ h_i ≤ 10⁹. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1927

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

設 A 為一個有 n 個數字的序列。
如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則稱他們為一個逆序數對

Input

多筆測資
每筆測資兩行
第一行為一正整數n
第二行n個數字，表示A序列
以EOF結束輸入

所有數字皆可存於32bit signed integer(ex: int in C++)
n<=10⁶

Output

每筆測資輸出一行一個數字：A的逆序數對的個數

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A和B是兩種細菌，這兩種細菌每天會增長，不過由於互利共生，AB細菌增長的量會跟彼此相關，公式如下

a(t) = 2*a(t-1) + b(t-1)

b(t) = 1*a(t-1) + 3*b(t-1)

a(t), b(t)分別表示時間t, A細菌和B細菌的數量

給時間0兩細菌的數量，求時間t的兩細菌的數量

對了，由於數量可能太大，你只要輸出數量除以1000000007的餘數就好

Input

多筆測資

每筆冊資一行三個整數，分別為時間0時, A細菌的數量a, B細菌的數量b, 第三個整數為時間t

以EOF結束

0 ≤ a,b ≤ 2³²-1

0 ≤ t ≤ 10¹⁵

Output

每筆測資一行
時間t的兩細菌的數量(mod 1000000007) 以一個空白格開

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你N個正整數, x[1]~x[N], 你可以做以下操作
操作 : 選出一組(x[i],x[j]) {i != j && x[i]>x[j]}, 然後令x[i] = x[i]-x[j];
目標 : 使最後的總合x[1]+x[2]+…x[N]越小越好!
操作的次數沒有限制!
Sorce : codeforces #228

Input

輸入有多筆測資.
每筆測資第一行為正整數N (1<=N<=1000)
接下來一行則會有N個正整數, 分別代表x[1]…x[N](1<=x[i]<=1000)

Output

每筆測資輸出一行一個數字 : 最小可能的總和.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 Mimi, Moumou兩人是青梅竹馬，從小就玩在一起（雖然他們現在也才小學三年級而已）。愛玩的兩人，平常的遊戲玩久了之後就覺得無聊沒勁，常常湊在一起發明新的遊戲。

這天他們又開始在設計新遊戲了，遊戲的規則如下：

1.     先在地上畫N個圓圈，編號1到N，並規定1號圓圈是起點、N號是終點

2.     在這N個圓圈之間任意互相畫”單向”箭頭，箭頭起點和終點各有一圓圈且兩圓圈不為同一圓，假設有一箭頭從圓a連到圓b，則遊戲中可以從a跳到b。

3.     檢查1, 2步驟所畫出的圖，確保任何編號1 ~ N-1的圓都有路徑可以走到終點，同時圖中也不可以有迴圈產生（也就是對於任何一個圓，絕對不會有路徑可以從自己走到自己），對任兩圓a, b最多只有一個箭頭從a指向b。

4.     兩個人進行遊戲，開始時先由一人站在起點（1號圓），另一個人站在圖外。

5.     遊戲中假設甲站在一個圓 C 中而乙在圖外，則乙要從 C 所指出去的箭頭中選一個箭頭，站到這個箭頭所指的圓上，然後甲則離開C走到圖外。

6.     兩人重複步驟5的動作，直到其中一人到達終點，到達終點的人為贏家。

例如下圖：

N = 5，假設由Mimi開始，且遊戲過程為

Mimi 在 1, Moumou 到 2, Mimi 到 3, Moumou 到 5 遊戲結束，由Moumou獲勝。

Input

每筆測資會有多行。
第一行會有兩個整數，分別為N,M。
之後會有M行，每行有兩個整數A,B，
代表A到B有一個單向的箭頭。
之後會有一行Mimi或Moumou，
代表遊戲一開始誰站在起點。
測資保證沒有不符合題目的測資。
當遇到N,M均為0時，代表測資結束。

N<=10000
1<=A,B<=N

Output

對於每一筆測資，假設兩人在挑選圓圈時，均使用對自己最有利的方式進行，
請輸出這組測資中，勝利的人是誰。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

首先我們定義一個爪子的長相 :
一個爪子包含4個點, 假設編號為1到4
則這個爪子有三條邊 :
1 2
1 3
1 4
一個爪子會如上所述.

現在題目會給你一張無向圖, 每個點的度數都是三. (每個點有三條邊連接)
請問這張圖是否可以分解成一堆爪子??
爪子的點可以共用, 但是每條邊只能出現在一個爪子裡.

以第一組測資為例, 可以有三個爪子, 分別是
一.
6 4
6 5
6 2
二.
1 2
1 4
1 5
三.
3 4
3 2
3 5
可以發現編號4的點就被三個爪子共用.

Input

輸入會有多組測資.

每組測資第一行為一個數字V, 代表圖的點個數 (4<=V<=300)
接下來每行有兩個數字a b , 代表編號a和編號b之間有一條邊 (1<=a,b<=V)
當a,b 都為0時表示這組測試資料的邊都讀完了.

當V = 0時表示測資結尾.

詳細請參考sample input.

Output

每組測資輸出一行.
如果圖可以拆解成許多爪的話輸出YES, 否則輸出NO.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 chess queens. The task is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the sum of the numbers on the squares selected is the maximum . (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one queen.)

Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions.

Input

Input will consist of K (the number of boards), on a line by itself, followed by K sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a non-negative integer less than 100. Each case is separated by a blank line. There will never be more than 20 boards.

Output

The outputs of all test cases should be printed in order. For each test case a line, print the highest score right justified in field 5 characters wide.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please maintain a max-heap, which stores integers and is able to support following operations:

(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.

(2) POP – Delete the maximum element from the heap.

(3) TOP – Print the maximum element in the heap.

Input

There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 1024 at any time.

Output

For each “TOP” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S₁ and S₂ are both valid, then S₁S₂ is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it.
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.

Input

The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.

Output

Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point.
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2829

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1095

 I know, up on top you are seeing great sights, But down at the bottom, we, too, should have rights. We turtles can’t stand it. Our shells will all crack! Besides, we need food. We are starving!” groaned Mack.

     Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle’s throne. Each of the five thousand, six hundred and seven turtles ordered by Yertle has a different weight and strength. Your task is to build the largest stack of turtles possible.

Input

 Standard input consists of several lines, each containing a pair of integers separated by one or more space characters, specifying the weight and strength of a turtle. The weight of the turtle is in grams. The strength, also in grams, is the turtle’s overall carrying capacity, including its own weight. That is, a turtle weighing 300g with a strength of 1000g could carry 700g of turtles on its back. There are at most 5,607 turtles.

Output

 Your output is a single integer indicating the maximum number of turtles that can be stacked without exceeding the strength of any one.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

n個人在排隊買午餐，餐廳突然宣布晚半個小時開，等待實在太浪費時間了，於是大家休息去做自己的事半個小時再回來，於是大家一人拿一張字卡，寫下前面人的學號，跟後面人的學號，如果前面或後面沒人就寫0，半個小時回來後大家發現，要還原原本的隊列不是那麼容易，於是請你寫個程式幫大家

source:http://codeforces.com/contest/490/problem/B

Input

多筆測資請用EOF結束
每筆測資第一行n，之後n行兩個整數分別為前面人的學號和後面人的學號
2<=n<=10^5
1<=學號<=10^6 且每個人學號不重複

Output

每筆測資請輸出一行n個數字，代表原隊列的順序（學號）學號間用一個空白隔開

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Source

PDF

Background

Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) -- finding whether all the cities in a salesperson's route can be visited exactly once with a specified limit on travel time -- is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check.

This problem deals with finding a minimal path through a grid of points while traveling only from left to right.

The Problem

Given an  matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix ``wraps'' so that it represents a horizontal cylinder. Legal steps are illustrated below.

The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited.

For example, two slightly different  matrices are shown below (the only difference is the numbers in the bottom row).

The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.

Input

 The input consists of a sequence of matrix specifications. Each matrix specification consists of the row and column dimensions in that order on a line followed by  integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in an input file. Input is terminated by end-of-file.

For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive. No path's weight will exceed integer values representable using 30 bits.

Output

Two lines should be output for each matrix specification in the input file, the first line represents a minimal-weight path, and the second line is the cost of a minimal path. The path consists of a sequence of n integers (separated by one or more spaces) representing the rows that constitute the minimal path. If there is more than one path of minimal weight the path that is lexicographically smallest should be output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1832

 This is a two player game. Initially there are n integer numbers in an array and players A and B get chance to take them alternatively. Each player can take one or more numbers from the left or right end of the array but cannot take from both ends at a time. He can take as many consecutive numbers as he wants during his time. The game ends when all numbers are taken from the array by the players. The point of each player is calculated by the summation of the numbers, which he has taken. Each player tries to achieve more points from other. If both players play optimally and player A starts the game then how much more point can player A get than player B?

Input

 The input consists of a number of cases. Each case starts with a line specifying the integer n (0 < n ≤100), the number of elements in the array. After that, n numbers are given for the game. Input is terminated by a line where n=0.

Output

 For each test case, print a number, which represents the maximum difference that the first player obtained after playing this game optimally.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Source

PDF

Background

Many problems in Computer Science involve maximizing some measure according to constraints.

Consider a history exam in which students are asked to put several historical events into chronological order. Students who order all the events correctly will receive full credit, but how should partial credit be awarded to students who incorrectly rank one or more of the historical events?

Some possibilities for partial credit include:

1. 1 point for each event whose rank matches its correct rank
2. 1 point for each event in the longest (not necessarily contiguous) sequence of events which are in the correct order relative to each other.

For example, if four events are correctly ordered 1 2 3 4 then the order 1 3 2 4 would receive a score of 2 using the first method (events 1 and 4 are correctly ranked) and a score of 3 using the second method (event sequences 1 2 4 and 1 3 4 are both in the correct order relative to each other).

In this problem you are asked to write a program to score such questions using the second method.

The Problem

Given the correct chronological order of n events  as  where  denotes the ranking of event i in the correct chronological order and a sequence of student responses  where  denotes the chronological rank given by the student to event i; determine the length of the longest (not necessarily contiguous) sequence of events in the student responses that are in the correct chronological order relative to each other.

Input

 The first line of the input will consist of one integer n indicating the number of events with  . The second line will containn integers, indicating the correct chronological order of n events. The remaining lines will each consist of n integers with each line representing a student's chronological ordering of the n events. All lines will contain n numbers in the range  , with each number appearing exactly once per line, and with each number separated from other numbers on the same line by one or more spaces.

Output

 For each student ranking of events your program should print the score for that ranking. There should be one line of output for each student ranking.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=378

 Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:

The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (x_i, y_i, z_i) . A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.

Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks.

Input

 The input file will contain one or more test cases. The first line of each test case contains an integer n, representing the number of different blocks in the following data set. The maximum value for n is 30. Each of the next n lines contains three integers representing the values x_i , y_i and z_i .

Input is terminated by a value of zero (0) for n.

Output

 For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height"

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Source

PDF

Write a program that will select the longest strictly increasing subsequence from a sequence of integers.

Input

 The input file will contain a sequence of integers (positive, negative, and/or zero). Each line of the input file will contain one integer.

Output

 The output for this program will be a line indicating the length of the longest subsequence, a newline, a dash character ('-'), a newline, and then the subsequence itself printed with one integer per line. If the input contains more than one longest subsequence, the output file should print the one that occurs last in the input file.

Notice that the second 8 was not included -- the subsequence must be strictly increasing.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Source

PDF

After making a purchase at a large department store, Mel's change was 17 cents. He received 1 dime, 1 nickel, and 2 pennies. Later that day, he was shopping at a convenience store. Again his change was 17 cents. This time he received 2 nickels and 7 pennies. He began to wonder ' "How many stores can I shop in and receive 17 cents change in a different configuration of coins? After a suitable mental struggle, he decided the answer was 6. He then challenged you to consider the general problem.

Write a program which will determine the number of different combinations of US coins (penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c) which may be used to produce a given amount of money.

Input

 The input will consist of a set of numbers between 0 and 30000 inclusive, one per line in the input file.

Output

The output will consist of the appropriate statement from the selection below on a single line in the output file for each input value. The number m is the number your program computes, n is the input value.

There are m ways to produce n cents change.

There is only 1 way to produce n cents change.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

The input consists of several test cases.

Output

 For each test case, output “yes” or “no” in a new line to check whether the target does exist or not.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

src : UVA 989

pdf : UVA989

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://poj.org/problem?id=3255

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1926

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1742

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss