Rick's blog

[C_DP18-中] 沙漠綠洲 成績: 0 / 倒扣: 0.8 問題描述：  在沙漠中有一個村落，村落旁邊有一個綠洲，村民所有的水都要從綠洲取得，村長發給每一戶人家一個水桶，以及家中每個人一個水瓢，年齡愈大的人拿到的水瓢容積愈大，並且規定每戶人家每天只能只能裝一桶水，取水時必須排隊，每個人一次只能舀一瓢水，而且水瓢必須裝滿。今天小明全家出動，要去裝水，知道水桶可裝  M  公升的水， 請幫小明算算全家人如何在排最少舀水幾次能將水桶裝滿，而綠洲的水相當珍貴，所以不能讓水滿出水桶。 輸入說明：  第一行有一個正整數  N  ，表示共有  N  筆測試資料，之後有  N  行，每行為一筆測試資料。每筆測資第一個數為一個正整數  K  (1 <=  K  <= 100) ，代表家中人口數 ( 即水瓢的數量 ) ，之後有  K  +1 個正整數，前面  K  個數字分別代表各水瓢的容積，最後一個則代表水桶的容積 (M <= 10000)，每個整數間均有一個空格隔開。 輸出說明：  每筆測試資料 輸出最少舀水次數 於一行，若無法在不溢出的情況下 將水桶裝滿則輸出 0 。 範例 Sample Input     Sample Output 2 3 2 3 4 5 4 2 4 6 8 21     2     0 解法:動態規劃 import java.util.Scanner; public class ITSA_C_DP18 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int N = sc.nextInt(); for (int n = 0; n < N; n++) { int K = sc.nextInt(); int volume[] = new int[K + 1]; for (int v = 1; v <= K; v++) volume[v] = sc.n

Internet Bandwidth   On the Internet, machines (nodes) are richly interconnected, and many paths may exist between a given pair of nodes. The total message-carrying capacity (bandwidth) between two given nodes is the maximal amount of data per unit time that can be transmitted from one node to the other. Using a technique called packet switching, this data can be transmitted along several paths at the same time. For example, the following figure shows a network with four nodes (shown as circles), with a total of five connections among them. Every connection is labeled with a bandwidth that represents its data-carrying capacity per unit time. In our example, the bandwidth between node 1 and node 4 is 25, which might be thought of as the sum of the bandwidths 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4. No other combination of paths between nodes 1 and 4 provides a larger bandwidth. You must write a program that computes the bandwidth betwee

Problem B Cheapest Base Input:  Standard Input Output:  Standard Output When printing text on paper we need ink. But not every character needs the same amount of ink to print: letters such as 'W', 'M' and '8' are more expensive than thinner letters as ' i ', 'c' and '1'. In this problem we will evaluate the cost of printing numbers in several bases. As you know, numbers can be expressed in several different bases. Well known bases are binary (base 2; digits 0 and 1), decimal (base 10; digits 0 to 9) and hexadecimal (base 16; digits 0 to 9 and letters A to F). For the general base  n  we will use the first  n  characters of the string "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", which means the highest base in this problem is 36. The lowest base is of course 2. Every character from this string has an associated cost, represented by an integer value between 1 and 128. The cost to print a number in a certain base is the s

2006/2007 ACM International Collegiate Programming Contest University of Ulm Local Contest Wine trading in Gergovia As you may know from the comic "Asterix and the Chieftain's Shield", Gergovia consists of one street, and every inhabitant of the city is a wine salesman. You wonder how this economy works? Simple enough: everyone buys wine from other inhabitants of the city. Every day each inhabitant decides how much wine he wants to buy or sell. Interestingly, demand and supply is always the same, so that each inhabitant gets what he wants. There is one problem, however: Transporting wine from one house to another results in work. Since all wines are equally good, the inhabitants of Gergovia don't care which persons they are doing trade with, they are only interested in selling or buying a specific amount of wine. They are clever enough to figure out a way of trading so that the overall amount of work needed for transports is minimized. In this problem you are

  Kindergarten Counting Game   Everybody sit down in a circle. Ok. Listen to me carefully. ``Woooooo, you scwewy wabbit!'' Now, could someone tell me how many words I just said? Input and Output Input to your program will consist of a series of lines, each line containing multiple words (at least one). A ``word'' is defined as a consecutive sequence of letters (upper and/or lower case). Your program should output a word count for each line of input. Each word count should be printed on a separate line. Sample Input Meep Meep! I tot I taw a putty tat. I did! I did! I did taw a putty tat. Shsssssssssh ... I am hunting wabbits. Heh Heh Heh Heh ... Sample Output 2 7 10 9 Ex: hi!hello@world~   Answer:3 import java.util.Scanner; public class UVA494 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int count = 0; while (sc.hasNext()) { count = 0;

Problem C : Cola Time limit: 10 seconds Y ou see the following special offer by the convenience store: " A bottle of Choco Cola for every 3 empty bottles returned " Now you decide to buy some (say  N ) bottles of cola from the store. You would like to know how you can get the most cola from them. The figure below shows the case where  N  = 8 .  Method 1  is the standard way: after finishing your 8 bottles of cola, you have 8 empty bottles. Take 6 of them and you get 2 new bottles of cola. Now after drinking them you have 4 empty bottles, so you take 3 of them to get yet another new cola. Finally, you have only 2 bottles in hand, so you cannot get new cola any more. Hence, you have enjoyed 8 + 2 + 1 = 11 bottles of cola. You can actually do better! In  Method 2 , you first borrow an empty bottle from your friend (?! Or the storekeeper??), then you can enjoy 8 + 3 + 1 = 12 bottles of cola! Of course, you will have to return your remaining empty bottle back to your

  Mutant Flatworld Explorers   Background Robotics, robot motion planning, and machine learning are areas that cross the boundaries of many of the subdisciplines that comprise Computer Science: artificial intelligence, algorithms and complexity, electrical and mechanical engineering to name a few. In addition, robots as ``turtles'' (inspired by work by Papert, Abelson, and diSessa) and as ``beeper-pickers'' (inspired by work by Pattis) have been studied and used by students as an introduction to programming for many years. This problem involves determining the position of a robot exploring a pre-Columbian flat world. The Problem Given the dimensions of a rectangular grid and a sequence of robot positions and instructions, you are to write a program that determines for each sequence of robot positions and instructions the final position of the robot. A robot  position  consists of a grid coordinate (a pair of integers: x-coordinate followed by y-coordin

Problem E Eb Alto Saxophone Player Input:  standard input Output:  standard output Time Limit:  2 seconds Memory Limit:  16 MB Do you like saxophone? I have a Eb Alto Saxophone, shown below. My fingers move A LOT when playing some music, and I'm quite interested in how many times each finger PRESS the button. Assume that the music is composed of only 8 kinds of note. They are: C D E F G A B in one octave and C D E F G A B in a higher octave. We use c,d,e,f,g,a,b,C,D,E,F,G,A,B to represent them. The fingers I use for each note are: c: finger 2~4, 7~10 d: finger 2~4, 7~9 e: finger 2~4, 7, 8 f: finger 2~4, 7 g: finger 2~4 a: finger 2, 3 b: finger 2 C: finger 3 D: finger 1~4, 7~9 E: finger 1~4, 7, 8 F: finger 1~4, 7 G: finger 1~4 A: finger 1~3 B: finger 1~2 (Note that every finger is controlling a specified button, different fingers are controlling different buttons.) Write a program to help count the number of times each finger presses the button. A finger pres

Problem G: Die Game Life is not easy. Sometimes it is beyond your control. Now, as contestants of ACM ICPC, you might be just tasting the bitter of life. But don't worry! Do not look only on the dark side of life, but look also on the bright side. Life may be an enjoyable game of chance, like throwing dice. Do or die! Then, at last, you might be able to find the route to victory. This problem comes from a game using a die. By the way, do you know a die? It has nothing to do with "death." A die is a cubic object with six faces, each of which represents a different number from one to six and is marked with the corresponding number of spots. Since it is usually used in pair, "a die" is a rarely used word. You might have heard a famous phrase "the die is cast," though. When a game starts, a die stands still on a flat table. During the game, the die is tumbled in all directions by the dealer. You will win the game if you can predict the number seen on t

  Problem B: Minesweeper   The Problem Have you ever played Minesweeper? It's a cute little game which comes within a certain Operating System which name we can't really remember. Well, the goal of the game is to find where are all the mines within a MxN field. To help you, the game shows a number in a square which tells you how many mines there are adjacent to that square. For instance, supose the following 4x4 field with 2 mines (which are represented by an * character): *... .... .*.. .... If we would represent the same field placing the hint numbers described above, we would end up with: *100 2210 1*10 1110 As you may have already noticed, each square may have at most 8 adjacent squares. The Input The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n,m <= 100) which stands for the number of lines and columns of the field respectively. The next n lines contains exactly m characters an

Problem C: Hardwood Species Hardwoods are the botanical group of trees that have broad leaves, produce a fruit or nut, and generally go dormant in the winter. America's temperate climates produce forests with hundreds of hardwood species -- trees that share certain biological characteristics. Although oak, maple and cherry all are types of hardwood trees, for example, they are different species. Together, all the hardwood species represent 40 percent of the trees in the United States. On the other hand, softwoods, or conifers, from the Latin word meaning "cone-bearing," have needles. Widely available US softwoods include cedar, fir, hemlock, pine, redwood, spruce and cypress. In a home, the softwoods are used primarily as structural lumber such as 2x4s and 2x6s, with some limited decorative applications. Using satellite imaging technology, the Department of Natural Resources has compiled an inventory of every tree standing on a particular day. You are to compute t

Train Swapping   At an old railway station, you may still encounter one of the last remaining ``train swappers''. A train swapper is an employee of the railroad, whose sole job it is to rearrange the carriages of trains. Once the carriages are arranged in the optimal order, all the train driver has to do, is drop the carriages off, one by one, at the stations for which the load is meant. The title ``train swapper'' stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening up vertically, the bridge rotated around a pillar in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right. The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees, the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite direction, but train c

Problem H Tell me the frequencies! Input:  standard input Output:  standard output Given a line of text you will have to find out the frequencies of the ASCII characters present in it. The given lines will contain none of the first 32 or last 128 ASCII characters. Of course lines may end with ‘\n’ and ‘\r’ but always keep those out of consideration. Input Several lines of text are given as input. Each line of text is considered as a single input. Maximum length of each line is 1000. Output Print the ASCII value of the ASCII characters which are present and their frequency according to the given format below. A blank line should separate each set of output. Print the ASCII characters in the ascending order of their frequencies. If two characters are present the same time print the information of the ASCII character with higher ASCII value first. Input is terminated by end of file. Sample Input: AAABBC 122333 Sample Output: 67 1 66 2 65 3 49 1 50 2 51 3 解