davood_b
یک شنبه 04 بهمن 1383, 17:00 عصر
Page 1
29th ACM International CollegiateProgramming Contest, 2004-2005Asia Region, Tehran SiteSharif University of Technology1–3 Dec. 2004Sponsored by Problem G(Program filename: G.cpp, G.dpr, or G.java)ACM-TelecomACM-Telecom provides communication services for international telephone calls. Cost of callinga country (call rates), varies from one to another. The company maintains the rates in a cost tablemapping the country codes to call rates. Upon receiving a call, an automatic system determinesthe country code by looking at the leftmost digits in the 8-digit dialed number and charges theclient according to the call rate of that country. More precisely, the automatic system maintains alist of country codes sorted in decreasing order. Upon receiving a call, the system starts from thetop of the list and checks if the country code is a prefix of the dialed number. The first countrycode satisfying this property is considered as the destination of the call and the client is chargedaccording to the call rate of that country. Note that the cost table covers every possible 8-digitnumber dialed, i.e., every dialed number matches with some country code in the table. Given therelatively high number of rows in the cost table and the increasing number of calls, the computationof call rates has become a quite lengthy process. Your task is to find a new cost table with theminimum number of rows such that the computed call costs for every possible (8-digit) dialednumber are the same as before.Input(filename: G.in)The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test casesin the input. Each test case starts with a line containing a single integer N(1 ≤ N ≤ 1000) whichis the number of rows in the cost table. Following the first line, there are N lines of the form codecost where code is an integer between 1 and 9999 inclusive, and cost (1 ≤ cost ≤ 100) is a positiveinteger which is the cost rate of the calls to the country code. There are no two lines with the samecountry code in a test case.Output(filename: G.out)For each test case, there is one line in the output containing the minimum number of rows of thetable required to compute the costs correctly.Sample Input112331 433 4335 41 12 23 34 45 56 67 78 89 9Sample Output101
29th ACM International CollegiateProgramming Contest, 2004-2005Asia Region, Tehran SiteSharif University of Technology1–3 Dec. 2004Sponsored by Problem G(Program filename: G.cpp, G.dpr, or G.java)ACM-TelecomACM-Telecom provides communication services for international telephone calls. Cost of callinga country (call rates), varies from one to another. The company maintains the rates in a cost tablemapping the country codes to call rates. Upon receiving a call, an automatic system determinesthe country code by looking at the leftmost digits in the 8-digit dialed number and charges theclient according to the call rate of that country. More precisely, the automatic system maintains alist of country codes sorted in decreasing order. Upon receiving a call, the system starts from thetop of the list and checks if the country code is a prefix of the dialed number. The first countrycode satisfying this property is considered as the destination of the call and the client is chargedaccording to the call rate of that country. Note that the cost table covers every possible 8-digitnumber dialed, i.e., every dialed number matches with some country code in the table. Given therelatively high number of rows in the cost table and the increasing number of calls, the computationof call rates has become a quite lengthy process. Your task is to find a new cost table with theminimum number of rows such that the computed call costs for every possible (8-digit) dialednumber are the same as before.Input(filename: G.in)The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test casesin the input. Each test case starts with a line containing a single integer N(1 ≤ N ≤ 1000) whichis the number of rows in the cost table. Following the first line, there are N lines of the form codecost where code is an integer between 1 and 9999 inclusive, and cost (1 ≤ cost ≤ 100) is a positiveinteger which is the cost rate of the calls to the country code. There are no two lines with the samecountry code in a test case.Output(filename: G.out)For each test case, there is one line in the output containing the minimum number of rows of thetable required to compute the costs correctly.Sample Input112331 433 4335 41 12 23 34 45 56 67 78 89 9Sample Output101