Chemical reactions

Problem code: G5

All submissions for this problem are available.

Johnny is preparing a chemical experiment for school. The experiment involves a certain number of different liquid chemical substances which have been mixed together and are currently reacting with each other. There are n different types of liquid substances. However, each substance appears in k different variants called isomers, and Johnny cannot distinguish between the different isomers...

We can assume that time is discrete and measured in minutes. During each minute, each possible reaction is described as follows: a b ratio type, meaning that ratio of liquid a (i.e., part of total amount, no matter which isomer) transforms into liquid b. If the reaction type is normal, then isomer i of liquid a transforms into isomer i of liquid b. If reaction type is special, then isomer i transforms into isomer i+1.

At time 0, each substance is in its initial isomer form, having number 1. For the special threshold value k, once isomer k of any substance passes through a special reaction, it transforms into solid state matter and precipitates from the mixure, no longer taking part in reactions (so, for all practical purposes, we can say it disappears). Moreover, during each minute, a small part of each liquid disappears (transforms into gaseous state and evaporates). From Johnny's point of view, the evaporation happens just before the reactions in any given minute.

Starting from time 0, exactly once a minute, Johnny takes note of the amount of each liquid in the mixture. He does this for a very, very long time, and then he sums the obtained amounts for each liquid (i.e., for each liquid, he adds the amount there was at time 0, at time 1, at time 2, etc.). The resulting n numbers are the result of the experiment. However, Johnny would like to know the results of experiment beforehand, so he asks you for a little help. Compute the results of his experiment, knowing that initially he just mixes the same amount (1 unit) of isomer 1 of each substance.

Input

First, 1≤n≤100, then 1≤k≤1000. Then, n floating point numbers follow, describing the proportion of liquid of each type that evaporates in each minute. Then, one integer m, the number of reactions, followed by m reaction definitions. Each definition consists of integers 0≤a<n, 0≤b<n, floating point 0<r≤1, and integer s=0 or 1, meaning that part r of the total amount of liquid a transforms into liquid b every minute (in the normal way if s=0, and in a special reaction, otherwise). No two pairs (a,b) are the same between definitions, i.e., always a != b.

Output

Exactly n numbers, representing the measured results of the experiment for each substance. Precision up to at least 6 digits after the decimal point is required.

Example

Input:
2
10
0.1 0.1
2
0 1 0.5 1
1 0 0.5 1

Output:
8.6556936725 8.6556936725
Author: admin
Date Added: 15-08-2009
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

So does each reaction affect

jcomeau_ictx @ 27 Oct 2009 05:16 PM

So does each reaction affect all isomers of the affected liquid proportionately? I don't see where that is specified, apologies if I overlooked it.

The answer, judging by my

jcomeau_ictx @ 29 Oct 2009 01:39 AM

The answer, judging by my correct output to the given test data, is "yes".

Here's a Python program to give some stress-test data, though it results in NaN's when I run my program against it (and takes over 8 minutes currently to even reach 10000 iterations):

#!/usr/bin/python
"generate data for G5 program at CodeChef"
import sys, os, random
n, k, m = 100, 1000, 1000
print n
print k
print ' '.join(map(str, [random.random() for x in xrange(n)]))
print m
j = 0  # offset
for i in xrange(m):
 j += (i % n == 0)
 print i % n, (i + j) % n, random.random(), j % 2

It looks as though it might be necessary, among other speedups, to convert all the data to ints by multiplying by 1000000000, then converting back to doubles for output. Floating-point math is possibly slowing things down.

Updated stress-test data

jcomeau_ictx @ 29 Oct 2009 02:13 AM

Updated stress-test data generator, doesn't produce NaNs:

 

#!/usr/bin/python
"generate data for G5 program at CodeChef"
import sys, os, random
n, k, m = 100, 1000, 1000
print n
print k
print ' '.join(map(str, [random.random() / 10 for x in xrange(n)]))
print m
j = 0  # offset
for i in xrange(m):
 j += (i % n == 0)
 print i % n, (i + j) % n, random.random() / 10, j % 2


My program runs the data in 17.16 seconds, still way too slow, but encouraging. Ignore the "int" idea, I don't see how to make it work when the evaporation and reaction fractions are all moved to the left of the decimal point... the numbers will need to be scaled after each operation, which is probably as slow or slower than using floating point.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions