Digits Forest

Problem code: DIGFORST

All submissions for this problem are available.

Given a simple undirected graph containing N vertices numbered 1 to N, each vertex containing a digit from {1,2,..7}. Starting at the vertex 1 with an empty string S, we travel through some vertices (with no limitations) to the vertex N. For every vertex on the way, we add the respective digit to the right of the string S. At last we get S as a decimal integer. You are requested to find such a way satisfying S is divisible by all of its digits, and the sum of digits of S must be as small as possible.

Input

There are several test cases (fifteen at most), each formed as follows:

  • The first line contains a positive integer N (N ≤ 100).
  • The second line contains N digits (separated by spaces), the i-th digit is the value of the i-th vertex.
  • N last lines, each contains N values of {0, 1} (separated by spaces), the j-th value of the i-th line is equal to 1 if there is an edge connecting two vertices (i, j), otherwise 0.
The input is ended with N = 0.

Output

For each test case, output on a line the minimum sum of digits found, or -1 if there's no solution.

Example

Input:
4
1 2 1 4
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0
0

Output:
7
Author: anhdq
Tester: subra
Editorial http://discuss.codechef.com/problems/DIGFORST
Date Added: 22-08-2011
Time Limit: 3 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, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

What to output for the case

KADR @ 1 May 2012 07:38 PM
What to output for the case when N = 1 and there is no edge from the 1st vertex to itself? In this case we will have an empty string at the end.

@KADR: the vertex 1 's value

anhdq_adm @ 1 May 2012 08:11 PM
@KADR: the vertex 1 's value is always the first digit of the string S.

is the square formed by the

fugitivesam @ 2 May 2012 03:02 PM
is the square formed by the numbers in the last N lines always symmetrical about the top-left to bottom-down diagonal ? in other words, if if an edge connects {i,j} does it also connect {j,i}?

@fugitivesam: yes, because it

anhdq_adm @ 2 May 2012 03:27 PM
@fugitivesam: yes, because it is "undirected" graph

Will there be self loops ?

mcsharma1990 @ 2 May 2012 06:31 PM
Will there be self loops ?

"we travel through some

shadow @ 2 May 2012 06:51 PM
"we travel through some vertices (with no limitations)" does this mean a node can be visited more than once even the Nth vertex?

@mcsharma1990: yes @shadow:

anhdq_adm @ 2 May 2012 09:13 PM
@mcsharma1990: yes @shadow: yes :)

can we travel a vertex twice?

pratishgupta91 @ 3 May 2012 11:48 PM
can we travel a vertex twice?

Can we assume that there will

thesoulhacker @ 4 May 2012 04:33 PM
Can we assume that there will be no cycles in the path from vertex 1 to vertex N ?

and anyone explain how is the

diamondfist @ 4 May 2012 06:02 PM
and anyone explain how is the answer 7 ?? cause if i go from 1 to 4 .. the string will contain "1" and its divisible by its digits and the sum is minimum, isn't it ?? what am i missing ??

@pratishgupta91: already

anhdq_adm @ 4 May 2012 07:05 PM
@pratishgupta91: already answered; @thesoulhacker: it doesn't cause any problem; @diamondfist: it should be "14" if you travel like that

can i go like this 1424, it

amriteshanand @ 7 May 2012 06:13 PM
can i go like this 1424, it is divisible by 1,2,4 sum is greater than 7 i know but is this a valid path or we can touch the last node just once.

@anhdq_adm if it is a simple

Amit Karmakar @ 7 May 2012 07:25 PM
@anhdq_adm if it is a simple graph why can there be self-loops?

@amriteshanand: it's a valid

anhdq_adm @ 8 May 2012 08:52 AM
@amriteshanand: it's a valid path; @Amit Karmakar: yes, it totally satisfies the statement

I'm not getting , one time

susan @ 9 May 2012 10:27 AM
I'm not getting , one time you say that there will be self loops as well as loops , now you are saying path "contains no loops also self loops"and also whether the end vertex can be visited twice ?

@anhdq_adm: I agree with

betlista @ 9 May 2012 12:31 PM
@anhdq_adm: I agree with @susan, it is confusing... I created few pictures to ask precisely 1.) are self loops possible? a[i][i] = 1 - see http://i.imgur.com/8C0pK.png 2.) are loops possible? - see http://i.imgur.com/3fkBb.png 3.) is the graph connected? see - http://i.imgur.com/Dijvm.png I believe, that none of these makes it more difficult, but I'm just implementing my solution, so I don't know for sure

I updated image for 2.)

betlista @ 9 May 2012 03:33 PM
I updated image for 2.) http://i.imgur.com/aAr90.png (previous was not correct) and added new one loop2 - http://i.imgur.com/95xkO.png

also 1.) was incorrect - new

betlista @ 9 May 2012 03:45 PM
also 1.) was incorrect - new one is http://i.imgur.com/hqUgJ.png

Hi guys, it may get confused

anhdq_adm @ 9 May 2012 09:17 PM
Hi guys, it may get confused with the term "simple graph". In this problem, "simple graph" means there's at most one connected graph. And there are loops also self-loops :) I think it doesn't affect much, sorry for the inconvenience !

say the number is X = d_1 d_2

theone.pa1 @ 10 May 2012 10:12 PM
say the number is X = d_1 d_2 d_3 ... d_n... where d_i are digits ( for all i ) of X ..... X%d_i should be zero , for all i ......let me know if I'm getting it all wrong !

@theone.pa1: yes

anhdq_adm @ 10 May 2012 10:43 PM
@theone.pa1: yes

SUCCESSFUL SUBMISSIONS


Fetching successful submissions