UVA – 435 – Dividing Coins

 #include &lt;stdio.h&gt;<br /><br />#include &lt;iostream&gt;<br /><br />#include &lt;algorithm&gt;<br /><br />#include &lt;math.h&gt;<br /><br />#include &lt;string.h&gt;<br /><br />#include &lt;string&gt;<br /><br />#include &lt;set&gt;<br /><br />#include &lt;map&gt;<br /><br />using namespace std;<br /><br />#define lop(ii, ii0, iin) for(ii=ii0; ii&lt;iin; ++ii)<br /><br />#define rep(ii, NN) lop(ii, 0, NN)<br /><br />int a[105], v[25005], i, j, half;<br /><br />int main() {<br /><br />int T, N, sum,t;<br /><br />scanf("%d", &amp;T);<br /><br />while (T-- &amp;&amp; scanf("%d", &amp;N) &amp;&amp; !(sum = 0)) {<br /><br />memset(v, 0, sizeof v);<br /><br />rep(i, N)<br /><br />t = scanf("%d", a + i), sum += a[i];<br /><br />half = sum / 2, v[0] = 1;<br /><br />rep(i, N)<br /><br />for (j = half; j &gt;= 1; j--)<br /><br />v[j] |= (a[i] &lt;= j ? v[j - a[i]] : false);<br /><br />for (j = half; j &gt;= 1; j--)<br /><br />if (v[j]) break;<br /><br />printf("%d\n", sum - 2 * j);<br /><br />}<br /><br />return 0;<br /><br />}<br /><br />
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: