程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程解疑 >> each-ACM-Telecom

each-ACM-Telecom

編輯:編程解疑
ACM-Telecom

Description

ACM-Telecom provides communication services for international telephone calls. Cost of calling a country (call rates), varies from one to another. The company maintains the rates in a cost table mapping the country codes to call rates. Upon receiving a call, an automatic system determines the country code by looking at the leftmost digits in the 8-digit dialed number and charges the client according to the call rate of that country. More precisely, the automatic system maintains a list of country codes sorted in decreasing order. Upon receiving a call, the system starts from the top of the list and checks if the country code is a prefix of the dialed number. The first country code satisfying this property is considered as the destination of the call and the client is charged according to the call rate of that country. Note that the cost table covers every possible 8-digit number dialed, i.e., every dialed number matches with some country code in the table. Given the relatively high number of rows in the cost table and the increasing number of calls, the computation of call rates has become a quite lengthy process. Your task is to find a new cost table with the minimum number of rows such that the computed call costs for every possible (8-digit) dialed number are the same as before.
Input

The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test cases in the input. Each test case starts with a line containing a single integer N(1 ≤ N ≤ 1000) which is the number of rows in the cost table. Following the first line, there are N lines of the form code cost where code is an integer between 1 and 9999 inclusive, and cost (1 ≤ cost ≤ 100) is a positive integer which is the cost rate of the calls to the country code. There are no two lines with the same country code in a test case.
Output

For each test case, there is one line in the output containing the minimum number of rows of the table required to compute the costs correctly.
Sample Input

1
12
331 4
33 4
335 4
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
Sample Output

10

最佳回答:


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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved