JDCC '17 Contest 3 S3 - Interview Progression

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Atharva is currently in an interview. He has memorized a list of \(S\) statements that he is prepared to say during the interview. The interviewer is marking him by points. He starts the interview with one point. Every statement he says affects his points in some way – as a function of his current points. Find a way to maximize the amount of points he gets in the interview.

The statements change his points in one of three ways (as a function of ​p-number of points):

1.+c​ where the new number of points is \(p ​+ ​c\)

2.^c​ where the new number of points is \(c ^ p\)

3.*c​ where the new number of points is ​\(c\times p\)

Input Specification

The first line contains ​\(S\)​ , the number of statements that Atharva has prepared.

The next ​\(S\) ​lines contain a statement in the form stated above, describing how the statement affects the points.

\(1 \le​ S ​\le 10​^5\)

\(0 \le ​c​ \le 10​^9​\) (whole number)

Output Specification

On the first line, output the number of statements he should say.

On the second line, output a number of indices (0-indexed), representing the order Atharva should say the statements so that he can maximize his points.

If there are multiple ways to do this, pick the way with the least number of statements and the least lexicographical order.

Sample Input 1

3
+0
^1
*1

Sample Output 1

0

Sample Input 2

3
^2
+5
*3

Sample Output 2

3
1 2 0

Explanation for Sample Outputs

For the first sample, no matter what Atharva says, his points stay at \(1\).

For the second sample Atharva can achieve a maximum score of \(2​^{3 \times (1+5)​} = 262144\).


Comments

There are no comments at the moment.