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++) { ...

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 be...

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 b...

  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-coor...