1º UTF.c

• Durante a prova:
  • É permitido consultar, e até mesmo copiar, qualquer volume de material impresso ou manuscrito trazido pelos competidores, como livros, cadernos, e apostilas.
  • Não é permitido usar nenhum equipamento eletrônico, nem mesmo celulares ou relógios, exceto a máquina disponibilizada para o time no laboratório.
  • Cada time terá uma única máquina para utilizar, independentemente de o time consistir em 1, 2, ou 3 integrantes. Os estudantes de um mesmo time poderão, claro, revezar o uso dessa máquina conforme a estratégia que melhor considerarem.
  • Todos os integrantes do time devem ser da mesma instituição e campus, mas não precisam ser necessariamente do mesmo curso.
  • Não é permitido que competidores de times distintos se comuniquem.
  • Se o competidor precisar sair do laboratório durante a prova (por exemplo, para ir ao banheiro, ou para comer ou beber alguma coisa), deverá levantar a mão e aguardar o apoio da equipe. Durante esses períodos de curta ausência, o competidor não poderá se comunicar com quaisquer pessoas que encontre, a não ser que não pretenda voltar mais ao laboratório.
  • Não é permitido consumir alimentos ou bebidas nos laboratórios.

• A prova consiste num caderno de problemas nos moldes dos problemas da Maratona de Programação, envolvendo conteúdos básicos comuns a disciplinas introdutórias de Computação e alguns pequenos desafios.
• Para cada problema, o time deverá desenvolver uma solução em uma das seguintes linguagens permitidas: C, C++, Java, ou Python. O código deverá então ser submetido no local apropriado no sistema, e será julgado por um juiz automático, que avaliará o comportamento do programa para um conjunto de casos de teste secretos. Apesar de cada problema conter exemplos de casos de teste, com os quais os competidores podem testar seus códigos localmente, frisa-se que o conjunto de casos de teste secretos do juiz é geralmente muito maior.
• Toda submissão deve ser uma tentativa legítima de resolver o problema correspondente. Cada submissão pode resultar num dos seguintes vereditos:
  1. NO - COMPILATIOR ERROR: seu código não foi aceito porque o compilador não conseguiu compilá-lo corretamente;
  2. NO - TIME LIMIT EXCEEDED: seu código não foi aceito porque o programa demorou muito tempo para rodar para algum caso de teste;
  3. NO - RUNTIME ERROR: seu código não foi aceito porque o programa foi abortado pelo sistema operacional por executar alguma operação inválida, como acesso indevido à memória ou exceção de ponto flutuante;
  4. NO - WRONG ANSWER: seu código não foi aceito porque o programa não imprimiu a saída esperada para algum caso de teste;
  5. NO - CLASS NAME MISMATCH (erro exclusivo para códigos submetidos como códigos em Java): seu código não foi aceito porque o nome da classe pública não seguiu o padrão convencionado;
  6. YES: seu código foi aceito e sua equipe ganhou um balão! Parabéns!
• Todos os times que realizarem a prova receberão um certificado de participação. Certificados especiais de reconhecimento serão também entregues:
  • aos três melhores times no placar geral;
  • ao melhor time da UTFPR, caso não tenha sido contemplado no item anterior;
  • ao melhor time composto apenas por mulheres, pessoas transgênero, ou pessoas não-binárias, caso não tenha sido contemplado nos itens anteriores (Prêmio Ada Lovelace do UTF.c);
  • ao melhor time composto apenas por estudantes do Ensino Médio, caso não tenha sido contemplado nos itens anteriores.
• O sistema utilizado nas máquinas da competição será o Maratona Linux, que os estudantes deverão usar para submeter as soluções para os problemas da prova. Para abrir o sistema de submissão dos códigos, basta abrir o navegador no Maratona Linux. Outras páginas da Internet além do sistema de submissão estarão bloqueadas. Qualquer tentativa de tentar violar esse bloqueio acarretará na desclassificação imediata do time.
• Os competidores poderão pedir esclarecimentos sobre os enunciados dos problemas durante a prova apenas através do recurso CLARIFICATIONS, no sistema de submissão. Não serão respondidas perguntas sobre as soluções dos problemas, apenas sobre os enunciados. Perguntas sobre a prova não poderão ser feitas à equipe de apoio.

• Para qualquer par de times \(A, B\) competindo, o time \(A\) ficará à frente do time \(B\) no placar se:
  1. tiver mais balões que o time \(B\);
  2. tiver igual número de balões que o time \(B\), mas pontuação de tempo menor.
• Times com igual número de balões e igual pontuação de tempo são considerados tecnicamente empatados.
• A pontuação de tempo de todos os times começa zerada.
• A competição consiste em 180 minutos de prova, contados a partir de 0. Cada submissão recebe uma timestamp, correspondente ao minuto em que o código foi submetido no sistema (não necessariamente o mesmo minuto em que veio e ser julgado).
• Se a submissão resulta em YES, e se corresponde ao primeiro código aceito que o time conseguiu desenvolver para aquele problema, é somado na pontuação de tempo do time:
  • a timestamp da submissão \(+\) o acumulado de penalidade que o time já tem naquele problema.
• Se a submissão resulta em NO e o time ainda não teve submissão alguma aceita para aquele problema, é acumulado para aquele problema uma penalidade de 20 pontos.
• A penalidade acumulada para um problema só é somada à pontuação de tempo do time quando o time vem de fato a ter uma submissão aceita para aquele problema.

• Para códigos submetidos em C ou C++:
  • Seu programa deve retornar zero, executando, como último comando, return 0 ou exit(0).
  • É sabido que em alguns casos de problemas com entradas muito grandes, os objetos cin podem ser lentos, por conta da sincronização de buffers da biblioteca stdio. Caso deseje utilizar cin e cout, um jeito de se contornar este problema é executando-se o comando ios base::sync_with_stdio(0), no início de sua função main. Note que, neste caso, o uso de scanf e printf no mesmo programa é contra-indicado, uma vez que, com buffers separados, comportamentos inadequados podem ocorrer.
  • Códigos em C serão compilados pelo sistema com: gcc -g -O2 -std=gnu11 -static -lm
  • Códigos em C++ serão compilados pelo sistema com: g++ -g -O2 -std=gnu++20 -static
  • É recomendável compilar localmente seu código com as flags acima especificadas para garantir que sua submissão não resultará em NO - COMPILATION ERROR.
• Para códigos submetidos em Java:
  • O nome do arquivo deverá corresponder à letra do problema. Exemplo: A.java, B.java, C.java etc.

  • O nome da classe pública do código deve ser uma letra maiúscula, também correspondente à letra do problema (A, B, C etc.). Isto é, por exemplo, use

    public class A {
      public static void main(String[] args) throws IOException {
        // code
      }
    }
    

    ao invés de

    public class Main {
      public static void main(String[] args) throws IOException {
        // code
      }
    }
    

  • O código será compilado com javac.
• Para códigos submetidos em Python:
  • Apenas Python 3 é suportado.
  • Não há a garantia de que códigos submetidos em Python passarão dentro do limite de tempo especificado para cada problema.

• Submeta apenas o código-fonte de seu programa! Não submeta o arquivo executável!

• Os códigos são avaliados de modo automático. Portanto, siga rigorosamente os formatos da entrada e da saída especificados nos enunciados dos problemas, conforme os exemplos fornecidos no caderno de prova. Por exemplo, se o problema pede para seu programa ler um inteiro positivo \(N < 100\) e imprimir o quadrado de \(N\), uma possível solução em C seria:

  #include<stdio.h>
  
  int main(void) {
    int n;
    scanf("%d", &n);
    printf("%d\n", n * n);
  }
  

  • Não imprima nada além do valor esperado! Por exemplo, NÃO inclua no seu código coisas como printf("Digite o numero: ");
  • Os elaboradores da prova garantem que seu programa só será testado com entradas que satisfazem as restrições do enunciado. Se o enunciado garante que o valor \(N\) da entrada é um inteiro positivo menor que \(100\), você pode confiar nessa garantia, não sendo necessário testá-la, nem validá-la.
• Se você é iniciante no mundo da Programação Competitiva, recomendamos a Jornada de Iniciação do Clube de Programação

• Prof. Leandro Zatesko (DAINF/UTFPR-CT)
• Fernando Kiotheka (UFPR)

• Prof. Leandro Zatesko (DAINF/UTFPR-CT)
• Fernando Kiotheka (UFPR)
• Bernardo Vendruscolo Mendes (UTFPR-CT)
• Eduardo Moreira (UDESC)
• Enzo Rodrigues (UDESC)
• Eric Grochowicz (UDESC)
• Gabriel Conke (UTFPR-CT)
• Gabriel Spadafora (UTFPR-CT)
• Henrique Bubniak (UTFPR-CT)
• Henrique Mendes (UTFPR-CT)
• João Oliveira (UDESC)
• João Rauli Sarmento (UTFPR-CT)
• Mateus Vilanova Passos (UTFPR-CT)
• Pedro Vinicius Silva (UFPR)
• Raul Almeida (UFPR)
• Thais Carvalho (UTFPR-CT)
• Thiago Aguiar (UTFPR-CT)
• Thiago Trannin (UFPR)
• Vinicius Tikara (UFPR)
• Profª. Marina Esther Groshaus (DAINF/UTFPR-CT)
• Profª. Nádia Kozievitch (DAINF/UTFPR-CT)
• Profª. Rita Berardi (DAINF/UTFPR-CT)

Please note that being well-versed in competitive programming is not the end goal, but only a means to an end. The true end goal is to produce all-rounder computer scientists/programmers who are much readier to produce better software and to face harder CS research problems in the future.

— Steve & Felix Halim, Competitive Programming Book

Um número é múltiplo de 3 se e só se a soma de seus dígitos é um múltiplo de 3. Portanto, não importa se os dígitos estão na ordem ou não. Só precisamos somar os dígitos recebidos e verificar se a soma é um múltiplo de 3.

Exemplo de código em C/C++:

#include<stdio.h>

int main(void) {
  int a, b;
  scanf("%d %d", &a, &b);
  if ((a + b) % 3 == 0) printf(":)\n");
  else printf(":(\n");
  return 0;
}

Vamos mostrar que se \(N\) é par, Sonic sempre tem uma estratégia vencedora para fazer Amy perder, não importando as escolhas de Amy. Observe que se \(N=0\), Amy não possui movimento disponível, logo perde. Suponhamos, então, que \(N > 0\) (i.e. \(N\geq 2\), já que estamos analisando o caso em que \(N\) é par). Amy tem à sua disposição uma fileira de \(N\) vasos alternados entre rosas (\(R\)) e tulipas (\(T\)), como no exempo abaixo para \(N=10\):

Vamos mostrar que, qualquer que seja o vaso que Amy escolha remover, Sonic sempre consegue responder removendo um vaso de modo que, na próxima jogada de Amy, ela se depara exatamente com a configuração que o jogo teria se tivesse começado naquele momento, mas para \(N-2\) vasos. Assim, a cada rodada, Sonic força com que Amy se depare com a configuração inicial do jogo (i.e. sem vasos adjacentes iguais) para \(N,N-2,\dotsc\) até \(0\) vasos, situação em que Amy perde.

Tendo à sua frente a configuração inicial do jogo para \(N\) vasos, se Amy escolhe remover um vaso das extremidades da fileira, Sonic pode remover um vaso também das extremidades e atingir seu objetivo, como no exemplo:

Por outro lado, se Amy escolhe remover um vaso que não está nas extremidades, Sonic sempre pode remover um vaso adjacente ao que Amy removeu, também atingindo seu objetivo, como no exemplo:

Mostramos, portanto, que se \(N\) é par, Sonic sempre consegue fazer Amy perder. Consequentemente, se \(N\) é ímpar, Amy sempre consegue fazer com que Sonic receba a configuração inicial (sem vasos adjacentes iguais) para um número par de vasos, logo sempre consegue forçar que ela seja a vencedora.

Assim, tudo o que precisamos fazer é verificar se \(N\) é par ou ímpar.

Exemplo de código em C/C++:

#include<stdio.h>

int main(void) {
  int n;
  scanf("%d", &n);
  if (n & 1) printf("Amy\n");
  else printf("Sonic\n");
  return 0;
}

Para cada \(i\)-ésima mesa (\(1\leq i\leq N\)), precisamos contar quantas mesas desde a posição \(1\) até a posição \(i-1\) têm um alvo, i.e. precisamos somar todos os valores desde \(M_1\) até \(M_{i-1}\).

Na entrada, recebemos duas esferas \(E_1,E_2\), dadas pelas coordenadas \((x,y,z)\) do centro e pela medida do raio: \(E_1=(x_1,y_1,z_1,r_1)\); \(E_2=(x_2,y_2,z_2,r_2)\). O que o problema pede é que decidamos se as esferas têm interseção (ainda que a interseção seja só um ponto) ou não. Duas esferas se intersectam se e somente se a distância entre seus centros é não maior que a soma de seus raios, i.e.

Note que verificar \eqref{eqraiz} é equivalente a verificar:

com a vantagem de que, para verificar \eqref{eqnutella}, podemos trabalhar apenas com inteiros, já que os valores fornecidos na entrada são todos inteiros.

Exemplo de código em C/C++:

#include<stdio.h>

int main(void) {
  int x1, y1, z1, r1, x2, y2, z2, r2, dx, dy, dz, normsq, sr;
  scanf("%d %d %d %d %d %d %d %d",
        &x1, &y1, &z1, &r1, &x2, &y2, &z2, &r2);
  dx = x1 - x2; dy = y1 - y2; dz = z1 - z2;
  normsq = dx * dx + dy * dy + dz * dz;
  sr = r1 + r2;
  printf("%c\n", normsq <= sr * sr ? 'S' : 'N');
  return 0;
}

Para cada posição de \(0\) até \(N-1\), seja \(\boldsymbol{s}[i]\) o caracter correspondente ao \(i\)-ésimo tick (H, X, ou -), e seja \(\boldsymbol{scr}[i]\) a pontuação obtida o \(i\)-ésimo tick, desconsiderando o uso da habilidade especial. Podemos computar \(\boldsymbol{scr}[]\) com uma varredura linear sobre \(\boldsymbol{s}[]\), apenas mantendo, para cada \(i\)-ésimo tick, um valor \(\boldsymbol{cons}[]\) que represente:

• quantos ticks consecutivos já foram acertados até aquele momento, se \(\boldsymbol{s}[i]=H\);
• \(0\), caso contrário.

Por exemplo:

     i =  0 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 17 18
   s[]    H H H - H H H H H H  H  H  H  H  H  H  X  -  H
cons[]    1 2 3 0 4 5 6 7 8 9  10 11 12 13 14 15 0  0  1
 scr[]    1 1 1 1 1 1 1 1 1 1  2  2  2  2  2  2  0  0  1

Tendo os valores do array \(\boldsymbol{scr}[]\) computados, seja \(unlock\) o instante em que a habilidade especial foi desbloqueada, i.e. a primeira posição tal que \(\boldsymbol{cons}[unlock]=15\), ou \(\infty\) caso todos os valores em \(\boldsymbol{cons}[]\) sejam menores que \(15\). O que precisamos fazer é encontrar qual a janela de \(K\) posições consecutivas do subarray \(\boldsymbol{scr}[unlock..n-1]\) que possui a maior soma, pois é nessa janela que utilizaremos o fator multiplicativo \(2\) correspondente ao uso da habilidade especial. Se esse subarray tiver menos de \(K\) posições, a janela será todo o subarray. Se o subarray for vazio (caso em que \(unlock=\infty\)), a janela será vazia.

Para encontrarmos a janela, basta computarmos, também numa varredura linear, a soma dos prefixos do array \(\boldsymbol{scr}[]\). A janela deve terminar na posição que atingir o maior valor de soma de prefixo e que posicionar a janela apenas em posições válidas (i.e. no início da janela, a habilidade especial não pode estar bloqueada).

Exemplo de código em C/C++:

#include<stdio.h>
#include<string.h>

#define MAX 112345

typedef long long ll;

int n, k;
char s[MAX];
int cons[MAX], scr[MAX];
ll sum[MAX], window[MAX];


int main(void) {
  int i, cnt = 0, _start, _end, unlock;
  ll ans = 0;
  scanf("%d %d %s", &n, &k, s);
  for (i = n; i < n + k; i++) s[i] = '-';
  s[n + k] = 0; n += k;
  memset(cons, 0, sizeof(cons));
  unlock = n;
  for (i = 0; i < n; i++) {
    if (s[i] == 'X') cons[i] = cnt = 0;
    else cons[i] = s[i] == 'H' ? ++cnt : 0;
    if (cons[i] == 15 && unlock == n) unlock = i;
    scr[i] = cons[i] ? (cons[i] >= 40 ? 5 : (1 + cons[i] / 10)) : 0;
  }
  sum[0] = scr[0];
  for (i = 1; i < n; i++) sum[i] = sum[i - 1] + scr[i];
  for (i = 0; i < n; i++)
    window[i] = sum[i] - (i - k >= 0 ? sum[i - k] : 0);
  _end = 0;
  for (i = 1; i < n; i++)
    if (window[i] > window[_end] && i - k + 1 > unlock) _end = i;
  if (_end) _start = _end - k + 1;
  else _start = _end = -1;
  for (i = 0; i < n; i++)
    if (cons[i])
      ans +=  scr[i] * (i >= _start && i <= _end ? 2 : 1);
  printf("%lld\n", ans);
  return 0;
}

A chave para resolver este problema é perceber que a quantidade \(M\) de andares é pequena: no máximo \(200\). Assim, podemos iterar todos os pares \((x,y)\) possíveis de andares e considerar, para cada par, o que aconteceria se os portais fossem instalados em \(x\) e em \(y\), i.e. seguir a lista dos andares que Chell precisa visitar e, para cada par \((A_{i-1},A_i)\) de andares consecutivos nessa lista, tomar a melhor das seguintes opções:

• ir de \(A_{i-1}\) a \(A_i\) usando somente escadas;
• ir de \(A_{i-1}\) a \(x\) usando escadas e depois de \(y\) a \(A_{i}\) usando escadas;
• ir de \(A_{i-1}\) a \(y\) usando escadas e depois de \(x\) a \(A_{i}\) usando escadas.

Como para cada par \((x,y)\) considerado realizamos uma única varredura linear sobre os \(N\) andares na lista de Chell, a complexidade desta solução é \(O(NM^2)\), o que é suficiente para passar no limite de tempo do problema, já que \(NM^2\sim 1.6\times 10^7\) para \(N\sim 400\) e \(N\sim 200\).

Exemplo de código em C++:

#include<bits/stdc++.h>
using namespace std;

#define MAX 500
#define INF 112345678

int m, n, a[MAX];

int main(void) {
  int i, x, y, ans1 = 0, ans2 = INF;
  scanf("%d %d", &m, &n);
  a[0] = a[m + 1] = 0;
  for (i = 1; i <= m; i++) scanf("%d", &a[i]);
  for (i = 1; i <= m + 1; i++)
    ans1 += abs(a[i] - a[i - 1]);
  for (x = 0; x < n; x++)
    for (y = x + 1; y < n; y++) {
      int tmp = 0;
      for (i = 1; i <= m + 1; i++)
        tmp += min(min(abs(a[i] - a[i - 1]),
                       abs(a[i] - x) + abs(a[i - 1] - y)),
                   abs(a[i] - y) + abs(a[i - 1] - x));
      ans2 = min(ans2, tmp);
    }
  printf("%d\n", ans1 - ans2);
  return 0;
}

Este é um problema mais de implementação, que admite várias abordagens. Sendo \(\boldsymbol a[][]\) a matriz de caracteres lida da entrada, a estratégia da implementação abaixo consiste no seguinte:

1. Primeiro identificamos as posições de \(\boldsymbol a[][]\) que de fato podem ser ocupadas pelo bloco, marcando-as com x. Assim, podemos contar, para cada linha \(i\), quantos caracteres x ou . temos, armazenando o resultado em \(\boldsymbol{cp}[i]\). Veja que só nos interessam as linhas \(i\) que têm \(\boldsymbol{cp}[i]=1\) ou \(\boldsymbol{cp}[i]=2\). Por exemplo, para a matriz

   ..........
   ...#.....#
   ....##..##
   #...######
   ##..######
   

   ficamos com

   XXXXXXXXXX   cp[1] = 10
   XXX#XXXXX#   cp[2] = 8
   XXX.##XX##   cp[3] = 6
   #XX.######   cp[4] = 3
   ##X.######   cp[5] = 2
   

2. Agora, consideramos cada linha \(i\) que tem \(\boldsymbol{cp}[i]\) igual a \(1\) ou \(2\), tomando \(j\) o índice de alguma das posições da linha que tem x ou .. Basta, então, verificar se é possivel preencher a linha \(i\) posicionando o bloco sobre \(j\) e sobre as posições adjacentes, considerando todas as possíveis rotações do bloco.

Exemplo de código em C/C++:

#include<stdio.h>
#include<string.h>

#define MAX 900

int n, m, cp[MAX], jp[MAX];
char a[MAX][MAX];

int main(void) {
  int i, j;
  scanf("%d %d", &n, &m);
  memset(cp, 0, sizeof(cp));
  memset(a, 0, sizeof(a));
  for (i = 1; i <= n; i++) scanf(" %s", a[i] + 1);
  for (j = 0; j <= m + 1; j++) a[0][j] = a[n + 1][j] = '#';
  for (i = 0; i <= n + 1; i++) a[i][0] = a[i][m + 1] = '#';
  for (j = 1; j <= m; j++)
    if (a[1][j] == '.')
      { a[1][j] = 'x'; cp[1]++; jp[1] = j; }
  for (i = 2; i <= n; i++)
    for (j = 1; j <= m; j++)
      if (a[i][j] == '.') {
        cp[i]++; jp[i] = j;
        if (a[i - 1][j] == 'x') a[i][j] = 'x';
      }
  for (i = 1; i <= n; i++) {
    j = jp[i];
    if (cp[i] == 1 && a[i][j] == 'x' &&
        a[i - 1][j] == 'x' && a[i - 1][j - 1] == 'x') {
      printf("%d %d\n", i - 1, j - 1);
      return 0;
    } else if (cp[i] == 1 && a[i][j] == 'x' &&
               a[i - 1][j] == 'x' && a[i - 1][j + 1] == 'x') {
      printf("%d %d\n", i - 1, j);
      return 0;
    } else if (cp[i] == 2 && a[i][j] == 'x' && a[i][j - 1] == 'x' &&
               a[i - 1][j] == 'x' && a[i - 1][j - 1] == 'x') {
      printf("%d %d\n", i - 1, j - 1);
      return 0;
    } else if (cp[i] == 2 && a[i][j] == 'x' && a[i][j - 1] == 'x' &&
               (a[i + 1][j] == 'x' || a[i + 1][j - 1] == 'x')) {
      printf("%d %d\n", i, j - 1);
      return 0;
    }}
  printf("-1\n");
  return 0;
}

Como \(N\) é um valor pequeno (no máximo \(8\)), e como a quantidade de espaços que temos para preencher também é um valor pequeno (exatamente \(8\)), podemos simplesmente enumerar exaustivamente (força-bruta) todas as possibilidades para o preenchimento dos espaços. Para cada maneira distinta de fabricar um baú que estivermos enumerando, teremos que escolher, para cada espaço, qual dos \(N\) tipos de madeira vamos utilizar. Portanto, enumeraremos \(O(8^N)\) maneiras. Como \(8^N\sim 1.6\times 10^7\) para \(N\sim 8\), esta solução é suficiente para passar no limite de tempo.

Exemplo de código em C/C++, que implementa a enumeração exaustiva com recursão (backtracking):

#include<stdio.h>

int n, c[8];

int brute(int i) {
  int j, ans = 0;
  if (i == 8) return 1;
  for (j = 0; j < n; j++)
    if (c[j] > 0) {
      c[j]--;
      ans += brute(i + 1);
      c[j]++;
    }
  return ans;
}

int main(void) {
  int i;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &c[i]);
  printf("%d\n", brute(0));
  return 0;
}

Para facilitar a explicação, vamos considerar que a sala do Prof. Pacman está na posição \(0\). Assim, os banheiros à esquerda estão em posição negativas, e os banheiros à direita estão em posições positivas.

É fácil provar que, na solução ótima, Prof. Pacman muda de direção no máximo uma vez. Podemos considerar que ele sempre muda de direção uma vez, pois na solução em que ele vai só para esquerda, por exemplo, podemos considerar que ele começou indo para a direita, mas mudou de direção já na posição \(0\).

Assim, a solução ótima é a solução em que, para alguma porta \(i\) (banheiro ou a sala do Prof. Pacman) que está na posição \(p(i)\), o Prof. Pacman vai até a porta \(i\), retorna à sua sala, e depois segue o quanto puder na outra direção, parando em alguma porta \(j\) que está na posição \(p(j)\). Nessa solução, Prof. Pacman percorre \(2\lvert p(i)\rvert + \lvert p(j)\rvert\) metros (lembre que convencionamos que a sala de Prof. Pacman está na posição \(0\)).

Então, tudo o que precisamos fazer, para cada porta \(i\) tal que \(2\lvert p(i)\rvert\leq L\), é encontrar a porta \(j\) do outro lado da sala do Prof. Pacman que maximiza \(\lvert p(j)\rvert\) e que satisfaz \(\lvert p(j)\rvert \leq L - 2\lvert p(i)\rvert\), o que podemos fazer com uma busca binária. Assim, conseguimos descobrir a quantidade \(m(i)\) de banheiros visitados nessa solução, em que mudamos de direção na porta \(i\). A resposta do problema é \(\max_i m(i)\).

Exemplo de código em C++:

#include<bits/stdc++.h>
using namespace std;

int main(void) {
  int p, l, b, i, d;
  vector<int> lft, rig; // banheiros à esquerda (lft) e à direita (rig)
  scanf("%d %d %d", &p, &l, &b);
  while (b--) {
    int q;
    scanf("%d", &q);
    if (q < p) lft.push_back(p - q); // guardamos a posição relativa a p
    else rig.push_back(q - p);
  }
  sort(lft.begin(), lft.end());
  int ans = upper_bound(lft.begin(), lft.end(), l) - lft.begin();
  ans = max(ans, (int)(upper_bound(rig.begin(), rig.end(), l) - rig.begin()));
  for (i = 0; i < (int)lft.size() && (d = l - 2 * lft[i]) >= 0; i++) {
    int j = upper_bound(rig.begin(), rig.end(), d) - rig.begin();
    ans = max(ans, i + 1 + j);
  }
  for (i = 0; i < (int)rig.size() && (d = l - 2 * rig[i]) >= 0; i++) {
    int j = upper_bound(lft.begin(), lft.end(), d) - lft.begin();
    ans = max(ans, i + 1 + j);
  }
  printf("%d\n", ans);
  return 0;
}

Do enunciado do problema, temos dois tipos de evento: chuva (1) e consulta (2). Para responder a cada consulta sobre um bairro \(I\), precisamos saber quando foi (tempo) que choveu em \(I\) pela última vez e comparar com o valor \(X\) (a quantidade de dias sem chuva a partir da qual o bairro passa a sofrer racionamento). Vamos, então, organizar os eventos chuva \(1\ J\) num array \(\boldsymbol a[]\) de pares \((\text{tempo},J)\), sendo \(\text{tempo}\) a posição do evento na lista de eventos, lembrando que \(J\) representa que choveu em todos os bairros de \(1\) a \(J\). Por exemplo, considere que \(N=5\) e \(X=3\), e que temos os seguintes eventos, em sequência:

1 5
1 2
1 3

Após o terceiro evento, temos

No entanto, perceba que, ao adicionar \((3,3)\) ao array, a informação de que choveu no tempo \(2\) em todos os bairros de \(1\) a \(2\) passa a ser inútil e pode ser descartada, uma vez que todos esses bairros são contemplados num evento de chuva mais recente. Assim, ficamos com

Note que, tendo como próximo evento chuva

1 1

ficamos com

Veja que não podemos descartar nenhum dos eventos do array, pois, embora também tenha chovido no bairro \(1\) no tempo \(3\), a informação de que choveu em \(1\) também no tempo \(4\) é mais recente e deve ser mantida (e não podemos descartar o evento chuva que ocorreu no tempo \(3\) pois ele abrange também os bairros \(2\) e \(3\)).

Assim, a cada evento chuva \(J\) que vamos inserir ao final do array, vamos remover do final do array todos os eventos chuva \(J'\) que tenham \(J'\leq J\), pois correspondem a informações que podem ser descartadas. Como cada evento chuva vai entrar no array uma vez e sair no máximo uma vez, o número amortizado de operações realizadas a cada evento chuva é \(O(1)\).

Mantendo o array organizado dessa forma, percebemos que os pares estão sempre ordenados tanto no primeiro membro quanto no segundo: no primeiro, seguem uma ordem crescente; no segundo, uma ordem decrescente. Logo, quando temos um evento de consulta \(2 I\), tudo o que precisamos fazer é localizar no array qual o último evento de chuva que abrange o bairro \(I\), i.e. qual o último par \((t,J)\) do array tal que \(J\geq I\), o que podemos fazer com uma busca binária. Como o array nunca terá mais de \(N\) pares, e como cada evento chuva custa tempo amortizado \(O(1)\) e cada evento consulta custa tempo \(O(\log N)\), temos que a complexidade total da solução é \(O(Q\log N)\), o que é suficiente para passar no limite de tempo, já que \(N,Q\sim 10^5\).