PROG0580 - Conan the Bacterium
In 1956 Arthur W. Anderson performed some experiments at the Oregon Agricultural Experiment Station (Corvallis, Oregon, US) to determine whether canned food could be sterilized using high doses of gamma radiation. A tin of meat was exposed to a dose of radiation that was thought to kill all known forms of life. After Anderson found out that the meat still spoiled after radiation, he managed to isolate a yet unknown bacterial species from the rotten meat.
The species was named Deinococcus radiodurans, a name derived from the Ancient Greek words δεινός (deinos) and κόκκος (kokkos) — meaning "terrible grain/berry" — and the Latin words radius and durare — meaning "surviving radiation". It is an polyextremophilic bacteria that is not only one of the most radiation-resistant organisms known, but it can also survive cold, dehydration, vacuum and acid. It has been listed as the world's toughest bacterium in The Guinness Book of World Records. As a consequence of its hardiness, it has been nicknamed Conan the Bacterium.
In 2003 American scientists demonstrated that D. radiodurans could be used as a means of information storage that might survive nuclear catastrophes. They translated the song It's a Small World into a series of DNA segments 150 base pairs long, inserted these into the bacteria, and were able to retrieve them without errors 100 bacterial generations later.
Assignment
You are involved in a scientific study that investigates the possibilities to store all the world's knowledge into D. radiodurans, just in case humanity would cease to exist after a nuclear catastrophe. You have been able to grow a variant species in the lab whose cell division goes faster as the dose of radiation is increased, and that stops growing as soon as radiation stops. For a given dose of radiation, you have determined that every second each cell divides itself into $a$ cells and that due to some abnormal effects of the radiation $b$ more cells are created. Thus, if at a given point in time there are $x$ cells in a test tube, one second later there are $ax + b$ cells in the test tube. You decide to set up two experiments to further investigate the properties of the new species.
At the beginning of the first experiment, there is a single cell in the test tube. Then you radiate the test tube during $n$ seconds. After you have stopped the radiation, you count $z$ cells in the test tube.
At the beginning of the second experiment, the test tube is sterilized and $t$ new cells are put into the test tube. The goal of this experiment is to determine whether these $t$ cells will divide independent of each other according to the procedure in the first experiment. If this is the case, the question that needs to be answered before running the experiment is how many seconds $s$ you will need to radiate the test tube to obtain at least $z$ cells in the test tube.
Say, for example, that $a=3$ and $b = 1$, and that we radiate the test tube for $n = 3$ seconds during the first experiment. In this case, the cells will grow each second as indicated in the second column of the table below. After three seconds, the test tube will contain $z = 40$ cells. If we start the second experiment with $t = 5$ cell in the test tube, these cells will grow each second as indicated in the third column of the table. After $s = 2$ seconds there will be exactly 49 cells in the test tube, which is larger than or equal to the number of cells $z = 40$ obtained after the first experiment.
| second | # cells (experiment 1) | # cells (experiment 2) |
|---|---|---|
| 0 | 1 | 5 |
| 1 | 4 | 16 |
| 2 | 13 | 49 |
| 3 | 40 |
Input
The input contains four integers $a$, $b$, $n$ and $t \in \mathbb{N}_0$, each on a separate line. The values $a$ and $b$ represent the parameters that determine the cell division of the bacterial species. The value $n$ indicates the number of seconds the test tube is radiated during the first experiment. The value $t$ indicates the number of cells that are in the test tube at the start of the second experiment.
Output
For each experiment, a single line of output must be generated that indicates how many cells there are in the test tube at the end of the experiment, and how many seconds the test tube has been radiated during the experiment. For the first experiment, the number of seconds the test tube is radiated can be read from the input. For the second experiment, the initial number of cells in the test tube can be read from the input. Derive the exact formatting of the output from the example given below.
Example
This example corresponds to the one discussed in the introduction of this assignment.
Input:
3 1 3 5
Output:
experiment #1: 40 cells after 3 seconds experiment #2: 49 cells after 2 seconds
In 1956 voerde Arthur W. Anderson aan de Oregon Agricultural Experiment Station (Corvallis, Oregon, VSA) een aantal experimenten uit om na te gaan of ingeblikt voedsel kon gesteriliseerd worden door middel van een hoge dosis gammastraling. Daarbij werd een blikje vlees blootgesteld aan een dosis straling waarvan algemeen werd aangenomen dat ze alle bekende levensvormen zou afdoden. Nadat bleek dat het vlees nog steeds bedierf, slaagde men erin om een tot dan toe onbekende soort bacteriën uit het bedorven vlees te isoleren.
De soort kreeg de naam Deinococcus radiodurans, een samenstelling van de oude Griekse woorden δεινός (deinos) en κόκκος (kokkos) — wat zoveel betekent als "verschrikkelijk graantje" — en de Latijnse woorden radius en durare — wat zoveel betekent als "straling overleven". Het is één van de meest extremofiele bacteriën die niet alleen zeer stralingsbestendig is, maar ook koude, dehydratatie, vacuüm en zuur kan overleven. De soort staat vermeld in The Guinness Book Of World Records als 's werelds meest hardnekkige bacterie. Als gevolg van deze hardnekkigheid kreeg de bacterie ook de bijnaam Conan the Bacterium.
In 2003 toonden Amerikaanse wetenschappers aan dat D. radiodurans kan gebruikt worden als een drager voor het opslaan van gegevens die zelfs bestand is tegen nucleaire rampen. Ze vertaalden het liedje It's a Small World naar een reeks DNA-fragmenten van 150 baseparen lang, brachten die in in het genoom van de bacterie, en slaagden erin om het liedje intact te recupereren na 100 bacteriële generaties.
Opgave
Je bent betrokken bij een wetenschappelijke studie naar de mogelijkheid om D. radiodurans te gebruiken voor het opslaan van alle kennis ter wereld, voor het geval de mensheid ooit zou uitsterven ten gevolge van een nucleaire catastrofe. Daarbij heb je een variant van de soort weten te kweken waarbij de celdeling steeds sneller gaat naarmate je de dosis van de straling laat toenemen, en die stopt met delen wanneer er geen straling meer is. Voor een bepaalde hoeveelheid straling heb je kunnen bepalen dat elke cel zich elke seconde deelt in $a$ cellen en dat er door uitzonderlijke effecten van de straling ook nog eens $b$ extra cellen bijkomen. Als je dus start met $x$ cellen in een proefbuis, dan zijn er een seconde later $ax + b$ cellen in de proefbuis. Je besluit om twee experimenten op te zetten om de eigenschappen van deze nieuwe soort verder te bestuderen.
Bij aanvang van het eerste experiment plaats je één enkele cel in een proefbuis. Daarna bestraal je de proefbuis gedurende $n$ seconden. Nadat je de straling hebt uitgezet tel je $z$ cellen in de proefbuis.
Bij aanvang van het tweede experiment wordt de proefbuis gesteriliseerd, en plaats je $t$ cellen in de proefbuis. Het doel van dit experiment is om na te gaan of deze $t$ cellen zich onafhankelijk van elkaar zullen delen volgens dezelfde procedure als bij het eerste experiment. Indien dat het geval is, dan is de vraag die je op voorhand moet beantwoorden hoeveel seconden $s$ je de proefbuis minimaal zal moeten bestralen om terug minstens $z$ cellen in de proefbuis te krijgen.
Veronderstel bijvoorbeeld dat $a=3$ en $b = 1$, en dat we tijdens het eerste experiment de cel gedurende $n = 3$ seconden bestralen. Dan groeien de cellen iedere seconde aan zoals aangegeven in de tweede kolom van onderstaande tabel. Na 3 seconden krijgen we uiteindelijk $z = 40$ cellen in de proefbuis. Als we in het tweede experiment starten met $t = 5$ cellen in de proefbuis, dan groeien de cellen iedere seconde aan zoals aangegeven in de derde kolom van de tabel. Na $s = 2$ seconden zijn er precies 49 cellen in de proefbuis, wat groter dan of gelijk is aan het aantal cellen $z = 40$ die we bekomen hadden na het eerste experiment.
| seconde | # cellen (experiment 1) | # cellen (experiment 2) |
|---|---|---|
| 0 | 1 | 5 |
| 1 | 4 | 16 |
| 2 | 13 | 49 |
| 3 | 40 |
Invoer
De invoer bestaat uit vier getallen $a$, $b$, $n$ en $t \in \mathbb{N}_0$ die elk op een afzonderlijke regel staan. Hierbij staan $a$ en $b$ voor de parameters die de celdeling van de bacteriën bepalen. De waarde $n$ geeft aan hoeveel seconden je de proefbuis bestraalt tijdens het eerste experiment. De waarde $t$ geeft aan hoeveel cellen er zich in de proefbuis bevinden bij aanvang van het tweede experiment.
Uitvoer
Voor elk van de uitgevoerde experimenten schrijf je een regel uit, die aangeeft hoeveel cellen er zich in de proefbuis bevinden op het einde van het experiment, en hoeveel seconden de proefbuis werd bestraald tijdens het uitvoeren van het experiment. Voor het eerste experiment krijg je het aantal te bestralen seconden gegeven in de invoer. Voor het tweede experiment krijg je het initieel aantal cellen in de proefbuis gegeven in de invoer. Bekijk onderstaand voorbeeld om te zien hoe de uitvoer precies moet opgemaakt worden.
Voorbeeld
Dit voorbeeld correspondeert met het voorbeeld dat in de inleiding van de opgave werd beschreven.
Invoer:
3 1 3 5
Uitvoer:
experiment #1: 40 cellen na 3 seconden experiment #2: 49 cellen na 2 seconden
| Added by: | Peter Dawyndt |
| Date: | 2015-10-18 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
RSS