|
|
Podjetje
FlatRadio d.d. se je prijavilo na razpis za postavitev radijskega oddajnika, ki
bo pokrival Centralno nižavje. Ker je v konkurenca huda, si želijo postaviti
najnižjo možno ceno. Cena oddajnika raste sorazmerno z oddajno močjo, zato so
ugotovili, da bo najbolje postaviti čim šibkejšega Glavnemu inženirju so zaupali nalogo ugotoviti, kako močan
oddajnik potrebujejo.
Po kratkem
posvetu z geografi je spoznal dve pomembni dejstvi, ki sta mu poenostavili
delo:
1) Centralno nižavje je popolnoma
ravno.
2) Vse prebivalstvo Centralnega nižavja je skoncentrirano v n mestih.
Inženirjev zaključek je bil: mesta v Centralnem nižavju lahko ponazorimo s točkami na ravnini. Ker je moč oddajnika sorazmerna z doseženo razdaljo, moramo oddajnik postaviti tako, da je maksimalna oddaljenost do kateregakoli mesta najmanjša. Z drugimi besedami, potrebno je najti krog z najmanjšim polmerom, ki vsebuje danih n točk v ravnini.
Podatki so sestavljeni iz več primerov. Vsak primer se začne z naravnim številom n, 2 <= n <= 100. Sledijo koordinate n mest (v kilometrih, od neke začetne točke). Vhodni podatki se zaključijo z vrsto, ki vsebuje ničlo.
Za vsak primer izpišite x in y koordinato oddajnika in največjo možno razdaljo, ki jo mora pokrivati v obliki (x, y) r=razdalja. Podatki naj bodo v kilometrih, zakroženi na tri decimalke.
3
0 0
1.000 0.000
0.500 0.866
3
0 0
1.000 0.000
0.500 0.200
0
(0.500, 0.289) r=0.577
(0.500, 0.000) r=0.500
|
|
This problem involves determining, for a group of gift-giving friends, how much more each person gives than they receive (and vice versa for those that view gift-giving with cynicism).
In this problem each person sets aside some money for gift-giving and divides this money evenly among all those to whom gifts are given.
However, in any group of friends, some people are more giving than others (or at least may have more acquaintances) and some people have more money than others.
Given a group of friends, the money each person in the group spends on gifts, and a (sub)list of friends to whom each person gives gifts; you are to write a program that determines how much more (or less) each person in the group gives than they receive.
The input is a sequence of gift-giving groups. A group consists of several lines:
All names are lower-case letters, there are no more than 10 people in a group, and no name is more than 12 characters in length. Money is a non-negative integer less than 2000.
The input consists of one or more groups and is terminated by a group of size 0.
For each group of gift-givers, the name of each person in the group should be printed on a line followed by the net gain (or loss) received (or spent) by the person. Names in a group should be printed in the same order in which they first appear in the input.
The output for each group should be separated from other groups by a blank line. All gifts are integers. Each person gives the same integer amount of money to each friend to whom any money is given, and gives as much as possible. Any money not given is kept and is part of a person's ``net worth'' printed in the output.
5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0
3
liz steve dave
liz 30 1 steve
steve 55 2 liz dave
dave 0 2 steve liz
0
dave 302
laura 66
owen -359
vick 141
amr -150
liz -3
steve -24
dave 27
|
|
Gondwanaland Telecom makes charges for calls according to distance and time of day. The basis of the charging is contained in the following schedule, where the charging step is related to the distance:
|
Charging Step |
Day Rate |
Evening Rate |
Night Rate |
|
A |
0.10 |
0.06 |
0.02 |
|
B |
0.25 |
0.15 |
0.05 |
|
C |
0.53 |
0.33 |
0.13 |
|
D |
0.87 |
0.47 |
0.17 |
|
E |
1.44 |
0.80 |
0.30 |
All charges are in dollars per minute of the call. Calls which straddle a rate boundary are charged according to the time spent in each section. Thus a call starting at 5:58 pm and terminating at 6:04 pm will be charged for 2 minutes at the day rate and for 4 minutes at the evening rate. Calls less than a minute are not recorded and no call may last more than 24 hours.
Write a program that reads call details and calculates the corresponding charges.
Input lines will consist of the charging step (upper case letter 'A'..'E'), the number called (a string of 7 digits and a hyphen in the approved format) and the start and end times of the call, all separated by exactly one blank. Times are recorded as hours and minutes in the 24 hour clock, separated by one blank and with two digits for each number. Input will be terminated by a line consisting of a single #.
Output will consist of the called number, the time in minutes the call spent in each of the charge categories, the charging step and the total cost in the format shown below.
A 183-5724 17 58 18 04
#
183-5724 2 4 0 A 0.44
|
|
The factorial of a number N (written N!) is defined as the product of all the integers from 1 to N. It is often defined recursively as follows:
1! = 1
N! = N * (N – 1)!
Factorials grow very rapidly -- 5! = 120, 10! = 3628800. One way of specifying such large numbers is by specifying the number of times each prime number occurs in it, thus 825 could be specified as (0 1 2 0 1) meaning no twos, 1 three, 2 fives, no sevens and 1 eleven.
Write a program that will read in a number N (2 <= N <= 100) and write out its factorial in terms of the numbers of the primes it contains.
Input will consist of a series of lines, each line containing a single integer N. The file will be terminated by a line consisting of a single 0.
Output will consist of a series of blocks of lines, one block for each line of the input. Each block will start with the number N, right justified in a field of width 3, and the characters ‘!’, space, and ‘=’. This will be followed by a list of the number of times each prime number occurs in N!.
These should be right justified in fields of width 3 and each line (except the last of a block, which may be shorter) should contain fifteen numbers. Any lines after the first should be indented. Follow the layout of the example shown below exactly.
5
53
0
5! = 3 1 1
53! = 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1
1
|
|
Odstavek besedila bi radi natisnili v pisavi, kjer so vsi znaki enako široki. Besedilo bo najbrž predolgo, da bi celega napisali v eni vrstici, zato ga bo treba razlomiti na več vrstic. Pri tem si želimo, da bi bile vse enako dolge, npr. po M znakov (izjema je zadnja vrstica, saj le-ta pri odstavkih običajno nima poravnanega desnega roba); da to dosežemo, bomo med besede po potrebi vrinili po več kot en presledek (če je med dvema besedama x presledkov, pravimo, da smo vrinili x – 1 dodatnih presledkov). Recimo torej, da smo besedilo razlomili v N vrstic, pri čemer je bilo treba v prvi vriniti P1 dodatnih presledkov, v drugi P2, itd., v predzadnji PN–1, v zadnji pa nobenega, saj smo rekli, da pri zadnji vrstici odstavka desnega roba pač ne poravnavamo. Na primer: če imamo M = 15 in bi radi v neko vrstico postavili besede ena, dve in tri, imamo tu v osnovi devet črk in dva presledka (enega med ena in dve ter enega med dve in tri), tako da bo treba vriniti še štiri dodatne presledke (Pi = 4), da pridemo do 15 znakov. Če v neko vrstico postavimo eno samo besedo, dolgo recimo L znakov, je treba v tako vrstico vriniti Pi = M – L dodatnih presledkov.
Nekateri razlomi so za oko prijetnejši, drugi manj (želimo si enakomerne gostote besedila); na primer: bolje je, če moramo v dve vrstici vriniti po pet presledkov, kot če jih vrinemo v eno deset in v drugo nobenega. Zato je dobro, če veliki Pi na oceno razloma vplivajo veliko bolj kot majhni. Definirajmo oceno razloma kot vsoto kubov P13 + P23 + ... + PN–13 ; manjša ko je ta ocena, boljši je razlom. Tvoja naloga je napisati program, ki bo znal za dano besedilo določiti oceno najboljšega razloma.
Tvoj program bo dobil na vhodu več testnih primerov. V prvi vrstici vsakega testnega primera sta števili M in K, ločeni s presledkom (M pove, kako širok stolpec besedila bi radi postavili); ta vrstica ne bo daljša od 30 znakov Naslednjih K vrstic vsebuje besedilo, ki ga moraš razlomiti. Zagotavljamo ti, da ne bo v tem besedilu nobena beseda daljša od M znakov. Pri tem je beseda definirana kot strnjeno zaporedje ne-presledkov, ki leži v celoti na eni vrstici in ga na obeh straneh obdajajo presledki ali pa začetek/konec vrstice. Če je torej med besedami v vhodni datoteki več presledkov ali pa je kakšna vrstica celo prazna, moraš takšne presledke pač ignorirati. Veljalo bo 1 <= M <= 1000, 1 <= K <= 1000, vsaka od tistih K vrstic pa bo dolga največ 1000 znakov (ne vštevši znaka za konec vrstice). Vhodna datoteka se konča z vrstico, ki vsebuje dve ničli namesto dopustnih vrednosti M in K. To ne šteje kot testni primer.
Za vsak testni primer izpiši vrstico, v kateri je ocena najboljšega razloma besedila pri tistem testnem primeru. Zagotavljamo, da ta ocena pri nobenem testnem primeru ne bo presegala 1000000000.
20 4
aaa bbb ccc dddd eee fffffff g
hh i jjj kk lll mm nnn oooo pp
qq rrr ss tttt uu vvvv www xxx yy zzz
aa bbb cccc dd eee ff ggg hh
0 0
25
To, mimogrede, ustreza naslednjemu razlomu besedila:
aaa bbb ccc dddd eee (0 dodatnih presledkov = 0 kazenskih točk)
fffffff g hh i jjj (2 dodatna presledka= 8 kazenskih točk)
kk lll mm nnn oooo (2 dodatna presledka= 8 kazenskih točk)
pp qq rrr ss tttt uu (0 dodatnih presledkov = 0 kazenskih točk)
vvvv www xxx yy zzz (1 dodaten presledek = 1 kazenska točka)
aa bbb cccc dd eee (2 dodatna presledka= 8 kazenskih točk)
ff ggg hh (0 dodatnih presledkov = 0 kazenskih točk)
Skupaj torej res dobimo oceno razloma 25.