PROG0124 - The diatomist
Klaus Kemp is the sole modern practitioner of a lost Victorian art form — arranging diatoms into tiny, dazzling patterns, like microscopic stained-glass windows.
Diatoms are single-celled algae that live in shells of glass-like silica. There are hundreds of thousands of varieties, ranging in size from 5 to 50 thousandths of a millimeter. In the latter part of the 19th century, professional microscopists arranged them into patterns for wealthy clients, but how they did this is unknown — they took their secrets with them. Kemp spent eight years perfecting his own technique, which involves arranging the shapes meticulously in a film of glue over a period of several days. In an article in Wired he explained it as follows:
"As a youngster of 16 I had a great passion for natural history and came across a collection of sample tubes of diatoms from the Victorian era. I was immediately struck by the beauty and symmetry of diatoms. The symmetry and sculpturing on an organism that one cannot see with the naked eye astonished me, and after 60 years of following this passion I can still get excited from the next sample I receive or collect."
Assignment
In this assignment we ask ourselves the question how many smaller circles having radius $r \in \mathbb{R}^+$ fit inside a larger circle having radius $R \in \mathbb{R}^+$, without the smaller circles overlapping each other. For example, we can fit at most 12 smaller circles in the larger circle shown in the following figure.
So far, nobody has been able to find the generic answer to this question, but the maximal number of smaller circles $n$ can be approximated using the following formula: $$n = \left\lfloor 0.83\frac{R^2}{r^2} - 1.9 \right\rfloor$$ where $\lfloor x\rfloor$ is the largest integer that does not exceed $x \in \mathbb{R}$.
Input
Two numbers $r$ and $R \in \mathbb{R}^+$ — each on a separate line — that respectively indicate the radius of the smaller and larger circles. As such, it must hold that $r \leq R$.
Output
A single line that indicates the maximum number of smaller circles that fit inside the larger circle, and the percentage of the larger circle that is covered by these smaller circles. Use the above formula to estimate the maximum number of smaller circles that fit inside the larger circle. The percentage of the larger circle covered must be expressed as a floating point number with two decimal digits. Rounding must be used to determine the digits of the floating point number.
Example
Input:
2.38 10.14
Output:
13 smaller circles cover 71.62% of the larger circle
Klaus Kemp is de enige moderne beoefenaar van een verloren gewaande Victoriaanse kunstvorm — het schikken van diatomeeën in minuscule, oogverblindende patronen die wat weg hebben van microscopische mozaïeken of glas-in-loodramen.
Diatomeeën zijn eencellige wieren met een extern skelet van kiezel (siliciumdioxide, SiO2). De klasse van de diatomeeën telt ongeveer 10.000 verschillende soorten, waarvan de meeste variëren in grootte van 10 tot 100 micrometer. Op het einde van de 19e eeuw ontstond het ambacht om ze door professionele microscopisten in allerlei patronen te laten schikken voor vermogende klanten. Hoe ze er precies in slaagden om dat te doen is onbekend — ze namen hun geheimen immers mee in hun graf. Kemp deed ongeveer acht jaar over het perfectioneren van zijn eigen techniek, die erin bestaat om de vormen over een periode van enkele dagen op een heel nauwkeurige manier te schikken in een laagje lijm. In een artikel in Wired legt hij het als volgt uit:
"Als jonge gast van 16 had ik een enorme passie voor de geschiedenis van de levenswetenschappen, en zo botste ik toevallig op een verzameling proefbuizen met diatomeeën uit de Victoriaanse tijd. Ik was meteen getroffen door de schoonheid en de symmetrie van diatomeeën. De symmetrie en sculpturen op een levend organisme die men niet met het blote oog kan waarnemen, deden me met verstomming slaan. Zelfs na 60 jaar met deze passie bezig te zijn, kan ik nog steeds opgewonden geraken bij het volgende staal dat ik neem of ontvang van een collega."
Opgave
In deze opgave vragen we ons af hoeveel kleinere cirkels met straal $r \in \mathbb{R}^+$ kunnen geschikt worden in een grotere cirkel met straal $R \in \mathbb{R}^+$, zonder dat de kleinere cirkels elkaar overlappen. Zo passen er bijvoorbeeld maximaal 12 kleinere cirkels in de grotere cirkel uit onderstaande figuur.
Er werd vooralsnog nog geen algemeen antwoord op deze vraag gevonden, maar het maximaal aantal kleinere cirkels $n$ kan op de volgende manier benaderd worden: $$n = \left\lfloor 0.83\frac{R^2}{r^2} - 1.9 \right\rfloor$$ Hierbij is $\lfloor x\rfloor$ het grootste geheel getal dat niet groter is dan $x \in \mathbb{R}$.
Invoer
Twee getallen $r$ en $R \in \mathbb{R}^+$ — elk op een afzonderlijke regel — die respectievelijk de straal van een kleinere en een grotere cirkel aangeven. Er geldt met andere woorden dat $r \leq R$.
Uitvoer
Een regel die aangeeft hoeveel kleinere cirkels er maximaal in de grotere cirkel kunnen geschikt worden, en de bedekkingsgraad van de grotere cirkel die daarmee bekomen wordt. Voor het schatten van het maximaal aantal kleinere cirkels moet bovenstaande formule gebruikt worden. De bedekkingsgraad moet uitgeschreven worden als een reeël getal dat afgerond is tot op twee cijfers na de komma.
Voorbeeld
Invoer:
2.38 10.14
Uitvoer:
13 kleine cirkels bedekken 71.62% van de grote cirkel
| Added by: | Peter Dawyndt |
| Date: | 2011-08-06 |
| Time limit: | 10s-30s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS