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

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

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

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

당신은 컨퍼런스 주최자들이 이 컴퓨터들을 사용하고 있다는 것은 알지만, 각 이벤트를 홍보하는 컴퓨터가 몇 대인지는 모른다. 각 이벤트에 대해, 그 이벤트 이름을 출력하도록 프로그래밍된 컴퓨터가 (0대를 포함해) 몇 대든 있을 수 있다. 또한 컴퓨터들이 모두 같은 횟수만큼 출력하도록 설정되어 있는 것도 아니다. 예를 들어 Io를 한 번씩 출력하는 컴퓨터가 3대 있고, Io를 두 번 출력하는 컴퓨터가 1대 있을 수도 있다.

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

예를 들어 문자열 IiOioIoO는 다음과 같이 두 대의 컴퓨터로 만들어졌을 수 있다:

• A: Io를 두 번 출력하도록 프로그래밍됨
• B: iO를 두 번 출력하도록 프로그래밍됨

    index:  1 2 3 4 5 6 7 8
    A:      I . . . o I o .
    B:      . i O i . . . O
    string: I i O i o I o O
  

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

하지만 이 문자열은 세 대의 컴퓨터로 만들어졌을 수도 있다:

• A: IO를 두 번 출력하도록 프로그래밍됨
• B: io를 한 번 출력하도록 프로그래밍됨
• C: io를 한 번 출력하도록 프로그래밍됨

    index:  1 2 3 4 5 6 7 8
    A:      I . O . . I . O
    B:      . i . . o . . .
    C:      . . . i . . o .
    string: I i O i o I o O
  

이 해석에서는 IO 이벤트가 2번, io 이벤트가 2번 홍보되었고, 나머지 두 이벤트는 전혀 홍보되지 않았다. 이 해석에서는 io를 출력하는 컴퓨터가 두 대 필요하다는 점에 유의하라. io를 한 대가 두 번 출력했다면 i를 연속으로 두 번 출력해야 하는데, 그것은 허용되지 않는다.

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

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