当前位置：文档库 › 2012TianJinOnlineProblemSet

2012TianJinOnlineProblemSet

1001

1001..Faulty Odometer

Description

You are given a car odometer which displays the miles traveled as an integer.The odometer has a defect,however:it proceeds from the digit2to the digit4and from the digit7to the digit9,always skipping over the digit3and8.This defect shows up in all positions(the one's,the ten's,the hundred's,etc.).For example,if the odometer displays15229and the car travels one mile,odometer reading changes to15240 (instead of15230).

Input

Each line of input contains a positive integer in the range1..999999999which represents an odometer reading.(Leading zeros will not appear in the input.)The end of input is indicated by a line containing a single0.You may assume that no odometer reading will contain the digit3and8.

Output

Each line of input will produce exactly one line of output,which will contain:the odometer reading from the input,a colon,one blank space,and the actual number of miles traveled by the car.

Sample Input

2005

250

1500

999999

Sample Output

15:12

2005:1028

250:160

1500:768

999999:262143

1002..Number

1002

Description

Here are two numbers A and B(0

For each x,f(x)equals to the amount of x’s special numbers.

For example,f(6)=1,because6only have one special number which is4.And f(12)=3,its special numbers are8,9,10.

When f(x)is odd,we consider x as a real number.

Now given2integers x and y,your job is to calculate how many real numbers are between them.

Input

In the first line there is an integer T(T<=2000),indicates the number of test cases. Then T line follows,each line contains two integers x and y(1<=x<=y<=2^63-1) separated by a single space.

Output

Output the total number of real numbers.

Sample Input

110

Sample Output

Hint

For the second case,the real numbers are6,8,9,10.

1003

1003..Island Transport

Description

In the vast waters far far away,there are many islands.People are living on the islands,and all the transport among the islands relies on the ships.

You have a transportation company there.Some routes are opened for passengers. Each route is a straight line connecting two different islands,and it is bidirectional. Within an hour,a route can transport a certain number of passengers in one direction. For safety,no two routes are cross or overlap and no routes will pass an island except the departing island and the arriving island.Each island can be treated as a point on the XY plane coordinate system.X coordinate increase from west to east,and Y coordinate increase from south to north.

The transport capacity is important to you.Suppose many passengers depart from the westernmost island and would like to arrive at the easternmost island,the maximum number of passengers arrive at the latter within every hour is the transport capacity.Please calculate it.

Input

The first line contains one integer T(1<=T<=20),the number of test cases.

Then T test cases follow.The first line of each test case contains two integers N and M(2<=N,M<=100000),the number of islands and the number of routes.Islands are number from1to N.

Then N lines follow.Each line contain two integers,the X and Y coordinate of an island.The K-th line in the N lines describes the island K.The absolute values of all the coordinates are no more than100000.

Then M lines follow.Each line contains three integers I1,I2(1<=I1,I2<=N)and C (1<=C<=10000).It means there is a route connecting island I1and island I2,and it can transport C passengers in one direction within an hour.

It is guaranteed that the routes obey the rules described above.There is only one island is westernmost and only one island is easternmost.No two islands would have the same coordinates.Each island can go to any other island by the routes.

Output

For each test case,output an integer in one line,the transport capacity.

Sample Input 2

133

234

243

156

453

144

243

342

-1-1

121

236

455

563

146

255

364

Sample Output 9

1004

1004..Judges'response

Description

The contest is running and the judges is busy watching the progress of the contest. Suddenly,N-1(N<=16)contestants hand up their hand at the same time.The judges should go to answer the contestants'question one by one.The judges already foresee that answering contest i's question would cost Ci minutes.In order to serve all the contestant,each judges is assigned to serve some subset of the contestants.As the judges have limited patience,each one of them can serve the contestants for no more than M minutes.

You are asked to solve two problems:

1.At least how many judges should be sent so that they can serve all the contestants?(Because the judges have limited patience,each one of them cannot serve too many contestants.)

2.If there are infinite number of judges,how to assign the route for each judge so that the sum of their walking time is minimized?Each contestant i is reside in place (xi,yi),the judges are in place(x1,y1).Assuming the walking speed of the judge is1.

Input

There are several test cases,Each case begin with two integer N,M(with the meaning in the above context,2<=N<=16,0<=M<=100000).

Then N lines follow and line i will contain two numbers x,y(0<=x,y<=1000), indicating the coordinate of place i.

Then another N lines follow and line i will contain numbers Ci(0<=Ci<=1000), indicating the time to solve contestant i's question.C1will0as place1is for the judges.

The distance between place i and place j is defined as ceil(sqrt((xi-xj)^2+(yi-yj)^2)).(ceil means rounding the number up,e.g.ceil(4.1)=5)

Output

For each case,output two numbers.The first is the minimum number of judges for question1.The second is the minimum sum of walking time for question2.

If it's impossible to serve all the contestants,please output-1-1instead.

Sample Input 33

1635

3040

3752

4949

5264

3162

5233

4241

5241

5758

6242

4257

2768

4367

5848

5827

3769

Sample Output 16

-1-1

8467

1005

1005..A very hard mathematic problem

Description

Haoren is very good at solving mathematic problems.Today he is working a problem like this:

Find three positive integers X,Y and Z(X1)that holds

X^Z+Y^Z+XYZ=K

where K is another given integer.

Here the operator“^”means power,e.g.,2^3=2*2*2.

Finding a solution is quite easy to Haoren.Now he wants to challenge more: What’s the total number of different solutions?

Surprisingly,he is unable to solve this one.It seems that it’s really a very hard mathematic problem.

Now,it’s your turn.

Input

There are multiple test cases.

For each case,there is only one integer K(0

K=0implies the end of input.

Output

Output the total number of solutions in a line for each test case.

Sample Input

Sample Output

Hints

9=1^2+2^2+1*2*2

53=2^3+3^3+2*3*3

1006

1006..You Are the One

Description

The TV shows such as You Are the One has been very popular.In order to meet the need of boys who are still single,TJUT hold the show itself.The show is hold in the Small hall,so it attracts a lot of boys and girls.Now there are n boys enrolling in.At the beginning,the n boys stand in a row and go to the stage one by one.However,the director suddenly knows that very boy has a value of diaosi D,if the boy is k-th one go to the stage,the unhappiness of him will be(k-1)*D,because he has to wait for (k-1)people.Luckily,there is a dark room in the Small hall,so the director can put the boy into the dark room temporarily and let the boys behind his go to stage before him.For the dark room is very narrow,the boy who first get into dark room has to leave last.The director wants to change the order of boys by the dark room,so the summary of unhappiness will be least.Can you help him?

Input

The first line contains a single integer T,the number of test cases.

For each case,the first line is n(0

The next n line are n integer D1-Dn means the value of diaosi of boys(0<=Di<= 100)

Output

For each test case,output the least summary of unhappiness.

Sample Input:

Sample Output:

Case#1:20

Case#2:24

1007..Travel

1007

Description

PP loves travel.Her dream is to travel around country A which consists of N cities and M roads connecting them.PP has measured the money each road costs.But she still has one more problem:she doesn't have enough money.So she must work during her travel.She has chosen some cities that she must visit and stay to work.In City_i she can do some work to earn Ci money,but before that she has to pay Di money to get the work license.She can't work in that city if she doesn't get the license but she can go through the city without license.In each chosen city,PP can only earn money and get license once.In other cities,she will not earn or pay money so that you can consider Ci=Di=0.Please help her make a plan to visit all chosen cities and get license in all of them under all rules above.

PP lives in city1,and she will start her journey from city1.and end her journey at city1too.

Input

The first line of input consists of one integer T which means T cases will follow.

Then follows T cases,each of which begins with three integers:the number of cities N(N<=100),number of roads M(M<=5000)and her initiative money Money(Money<=10^5).

Then follows M lines.Each contains three integers u,v,w,which means there is a road between city u and city v and the cost is w.u and v are between1and N (inclusive),w<=10^5.

Then follows a integer H(H<=15),which is the number of chosen cities.

Then follows H lines.Each contains three integers Num,Ci,Di,which means the i_th chosen city number and Ci,Di described above.(Ci,Di<=10^5)

Output

If PP can visit all chosen cities and get all licenses,output"YES",otherwise output "NO".

Sample Input 2

4510

121

232

132

141

342

185

252

3101

21100

1210000

21000001

Sample Output YES

1008..circuits

1008

Description

Given a map of N*M(2<=N,M<=12),'.'means empty,'*'means walls.You need to build K circuits and no circuits could be nested in another.How many ways do we have?

Input

The first line of input has an integer T,number of cases.

For each case:

The first line has three integers N M K,as described above.

Then the following N lines each has M characters,‘.’or‘*’.

Output

For each case output one lines.

Each line is the answer%1000000007to the case.

Sample Input:

441

**..

....

441

....

Sample Output

1009..Data Handler

1009

Description

You are in charge of data in a company,so you are called"Data Handler".Different from the data in computer,the data you have are really in huge volume,and each data contains only one integer.All the data are placed in a line from left to right.There are two"hand"to handle the data,call hand"L"and hand"R".Every hand is between two adjacent data or at the end of the data line.

In one day,the company gives you many commands to handle these data,so you should finish them one by one.At the beginning,there are N data,and hand"L"and "R"are in some positions.Each command is one the following formats:

(1)MoveLeft L/R:it means that you should move the hand"L"/"R"left one data unit;

(2)MoveRight L/R:it means that you should move the hand"L"/"R"right one data unit;

(3)Insert L X:it means that you should insert the data that contains X at the right of the hand"L";

(4)Insert R X:it means that you should insert the data that contains X at the left of the hand"R";

(5)Delete L:it means that you should delete the one data at the right of the hand "L";

(6)Delete R:it means that you should delete the one data at the left of the hand "R";

(7)Reverse:it means that you should reverse all the data between hand"L"and hand"R".

After finish all the commands,you should record all the data from left to right.So please do it.

Input

The first line contains an integer T(1<=T<=10),the number of test cases.

Then T test cases follow.For each test case,the first line contains an integer N(1<=N<=500000),the number of data at the beginning.The second line contains N integers,means the integer in each data,from left to right.The third line contains two integers L and R(1<=L<=R<=N),the positions of hand"L"and hand"R".It means that hand"L"is at the left of the L-th data and hand"R"is at the right of the R-th data. The fourth line contains one integer M(1<=M<=500000),the number of commands. Then M lines follow,each line contains a command in the above format.All the integers in the data will in range[-10000,10000].

It is guaranteed that there are always some data between hand"L"and"R",and if the hand is at the left/right end of the data line,it will not receive the command MoveLeft/MoveRight.

Because of large input,please use scanf instead of cin.

Output

For each test case,output the integers in the data from left to right in one line, separated in a single space.

Because of large output,please use printf instead of cout.

Sample Input

12345

MoveLeft R

Insert R6

Reverse

Delete R

Insert L7

6536520726096604-4046

Delete L

Insert R-9221

Reverse

Delete L

MoveRight L

Sample Output

764325

260952076604-4046

1010

1010..Intelligent IME

Description

We all use cell phone today.And we must be familiar with the intelligent English input method on the cell phone.To be specific,the number buttons may correspond to some English letters respectively,as shown below:

2:a,b,c3:d,e,f4:g,h,i5:j,k,l6:m,n,o

7:p,q,r,s8:t,u,v9:w,x,y,z

When we want to input the word“wing”,we press the button9,4,6,4,then the input method will choose from an embedded dictionary,all words matching the input number sequence,such as“wing”,“whoi”,“zhog”.Here comes our question,given a dictionary,how many words in it match some input number sequences?

Input

First is an integer T,indicating the number of test cases.Then T block follows, each of which is formatted like this:

Two integer N(1<=N<=5000),M(1<=M<=5000),indicating the number of input number sequences and the number of words in the dictionary,respectively.Then comes N lines,each line contains a number sequence,consisting of no more than6 digits.Then comes M lines,each line contains a letter string,consisting of no more than6lower letters.It is guaranteed that there are neither duplicated number sequences nor duplicated words.

Output

For each input block,output N integers,indicating how many words in the dictionary match the corresponding number sequence,each integer per line.

Sample Input

64448

night

might

Sample Output 3