뒤섞인 출력: 2부 timer 20s memory 1024MB

이 문제를 풀기 위해 Interleaved Output: Part 1을 읽을 필요는 없다. Part 1과 Part 2는 (이 안내 문구를 제외하고) 처음 두 문단이 동일하다. 두 파트의 핵심적인 차이점은 밑줄로 표시해 두었다.

목성의 먼 위성에서 개발자 컨퍼런스 이벤트들이 열릴 예정이다! 이벤트 이름은 IO(대문자 I, 대문자 O), Io(대문자 I, 소문자 o), iO(소문자 i, 대문자 O), io(소문자 i, 소문자 o)이다.

이벤트를 홍보하는 가장 좋은 방법은 이벤트 이름을 한 글자씩 출력하고 그 결과가 디지털 디스플레이에 나타나는 특수 컴퓨터를 사용하는 것이다. 이런 컴퓨터는 오직 한 이벤트의 이름만 알고 있으며, 자신의 이벤트 이름을 0번 이상 출력하도록 프로그래밍되어 있다. 예를 들어 IO를 두 번 출력하도록 프로그래밍된 컴퓨터는 I, O, I, O를 순서대로 출력하여 최종 문자열 IOIO를 만든다.

당신은 컨퍼런스 आयोज자들이 각 이벤트를 홍보하기 위해 정확히 한 대의 컴퓨터만 사용한다는 것을 알고 있다. 각 컴퓨터는 자신의 이벤트 이름을 0번 이상 출력할 수 있다. 또한 컴퓨터들이 모두 같은 횟수만큼 출력하도록 설정되어 있는 것도 아니다.

모든 컴퓨터의 출력은 끝났지만, 불행히도 모두 같은 디스플레이에 출력해 버렸다! 컴퓨터들이 동시에 출력했기 때문에, 최종 출력 문자열에서는 이벤트 이름들이 서로 뒤섞여(interleave) 있을 수 있다. 당신은 그 문자열이 만들어질 수 있었던 가능한 방법들을 생각해 보고 있다.

예를 들어 문자열 IiOioIoO는 다음과 같이 만들어졌을 수 있다:

    index:  1 2 3 4 5 6 7 8
    IO:     . . . . . . . .
    Io:     I . . . o I o .
    iO:     . i O i . . . O
    io:     . . . . . . . .
    string: I i O i o I o O
  

이 해석에서는 Io 이벤트가 2번, iO 이벤트가 2번 홍보되었고, 나머지 두 이벤트는 전혀 홍보되지 않았다.

IO 컴퓨터가 이벤트를 두 번 홍보한 유효한 해석은 존재하지 않는다는 점에 유의하라. 그런 경우라면 남는 출력인 iioo가 io 컴퓨터에서 나와야 했는데, 그것은 불가능하다 — 그 컴퓨터는 i를 연속으로 두 번 출력해야 하기 때문이다.

하지만 IO 컴퓨터가 이벤트를 한 번 홍보하는 것은 가능하며, 예를 들면 다음과 같은 해석이 있다:

    index:  1 2 3 4 5 6 7 8
    IO:     . . . . . I . O
    Io:     I . . . o . . .
    iO:     . i O . . . . .
    io:     . . . i . . o .
    string: I i O i o I o O
  

최종 출력 문자열이 주어질 때, 이벤트 IO가 홍보되었을 수 있는 횟수의 최댓값은 얼마인가?

입력 문자열에는 적어도 하나의 유효한 해석이 존재함이 보장된다. 예를 들어 oI, IOI, IIOO는 유효한 입력이 아니다.