C++

Forum

 
i want help in problem

mido22 (8)
how can i solve that type of problems 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
Corrupted
Kamel has got a text document which was created on Microsoft Windows with an extension
that does not work on Ubuntu. Unfortunately he has switched to Ubuntu and now the text file
can not be opened. But he tried to change the extension to (.txt) which can work on Ubuntu
and it worked! However, the poor guy has found that the file components have been corrupted.
The file included some listed information and they were numbered in points, there were subnumbering
and in the sub-numbers there might be sub-numbering again and so on. For
example:
1. #######
2. ####
1. ####
2. #####
3. ##
1. ######
2. ####
4. #######
1. ###
Where the Hashes ‘#’ are some written information.
But when the files was corrupted the text (in the previous example) appeared as:
1. #######
2. ####
1. ####
2. #####
3. ##
1. ######
2. ####
4. #######
1. ###
Now he can not understand the text after what happened and he needs your help. Help Kamel
to find how many ways the numbering he has found in the corrupted file could have been subnumbered
in the original text document.
Note that numbering should start with 1 and increases by 1 in every new point in the same subnumbering,
where:
1.
1.
2.
1.
is valid, but
1.
1.
2.
2.
is not valid.
Input Format
You will be given integer N, the number of lines in the file. In the next line, N integers the
numbering that Kamel has found in the corrupted file in order. All the gieven N integers will not
exceed 100.
Output Format
If there is no possible solution output the string “IMPOSSIBLE”, else your program should
output the number of possible ways the sub-numbering could have been like in the original text
document file.
Scoring
The test cases are divided into 4 subtasks:
Subtask 1 (20 Points):
● 1<=N<=5
Subtask 2 (20 Points):
● N will not exceed 100 (1<=N<=100).
● All given numbers will not exceed 2.
● It is guaranteed that the number of possible solutions will not exceed 4,000,000.
Subtask 3 (30 points):
● N will not exceed 400 (1<=N<=400).
● It is guaranteed that the number of possible solutions will not exceed 4,000,000.
Subtask 4 (30 Points):
● N will not exceed 400 (1<=N<=400).
● Number of possible solutions will need to be returned as a 64-bit Integer.
●
Example Input
9
1 2 1 2 3 1 2 4 1
Example Output
2
Explanation of the Example
The original text might have been one of the following:
First:
1.
2.
1.
2.
3.
1.
2.
4.
1.
Second:
1.
2.
1.
2.
3.
1.
2.
4.
1.
helios (17575)
It can be solved by backtracking: the input is treated as describing a tree and you have to find a test to be executed at each node of the tree by a function that traverses the tree. Once the function reaches a leaf, it means a solution has been found and can be added to a list of solutions. Once the tree has been completely traversed, the list of solutions contains all possible solutions to the problem.
Last edited on
mido22 (8)
hmmm can u give me pseudo code to this problem
Azagaros (410)
Is this for a class assignment? You build the information in a binary tree, or b-tree. Traversing down the tree from a root node you generate the pattern you are looking for. Have they talked about binary trees in your class? Or if this is just for fun look up binary trees on wiki, they might have a simple implementation code in a number of languages. Helios basically gave you the algorithm. It looks like a basic program form a a class to some of us.
helios (17575)
hmmm can u give me pseudo code to this problem
I could, but I won't.

You build the information in a binary tree, or b-tree
Binary tree and B-tree are not synonyms. They're two different data structures used in vary different situations.
Also, it's not necessary to actually build a tree (in this case it won't be binary, by the way). The function only needs to behave as though it was traversing one, when in reality it will simply be incrementing some counters and probably calling itself.
mido22 (8)
really i don't understand u except with pseudo code
it is a homework but i 'm searching for hard problems because i want to be in progress in programming so i can learn ur idea only from codes....
helios (17575)
What's the point of looking for hard problems if you're going to ask other people to solve them for you?
mido22 (8)
now i am not asking someone to solve hard problems for me i want only to see new codes of new algorithms that i didn't use this algorithm before
Topic archived. No new replies allowed.