Segredo do cofre, Teleférico
Autor(es): Dayna
O sistema de segredo para abrir um cofre envolve deslizar um controle sobre uma barra com N posi ̧c ̃oes. Cada posi ̧c ̃ao cont ́em um n ́umero entre 0 e 9.
O segredo depende de quantas vezes cada n ́umero aparece dentro do controle enquanto ele ́e deslizado de uma posi ̧c ̃ao para outra. Por exemplo, se a barra ́e 9 4 3 9 1 ... e movemos da posi ̧c ̃ao 1 para a 9, contamos todos os n ́umeros nesse intervalo. Se em seguida movemos da 9 para a 4, contamos os n ́umeros no intervalo reverso.
Importante: O final de um movimento ́e o in ́ıcio do pr ́oximo. Para n ̃ao contar o mesmo n ́umero duas vezes no mesmo instante (o pivˆo), o n ́umero da posi ̧c ̃ao inicial de um movimento (exceto o primeiro) n ̃ao deve ser re-contabilizado.
Dada a configura ̧c ̃ao da barra e a sequˆencia de movimentos, seu programa deve contar a frequˆencia total de cada d ́ıgito (0 a 9).
A primeira linha cont ́em dois inteiros N e M (2 ≤ N, M ≤ 105). A segunda linha cont ́em N inteiros (a barra). A terceira linha cont ́em M inteiros (a sequˆencia de posi ̧c ̃oes visitadas, 1-based).
Imprima uma linha com 10 inteiros, representando a contagem total de cada d ́ıgito de 0 a 9.
14 5 9 4 3 9 1 2 4 5 1 1 9 7 0 5 1 9 4 11 13
1 6 3 1 4 3 0 1 0 4
5 4 5 8 0 5 1 1 4 2 5
3 1 0 0 0 3 0 0 2 0
Uma simula ̧c ̃ao direta (percorrer a barra posi ̧c ̃ao por posi ̧c ̃ao para cada movimento) teria complexi- dade O(N × M), o que para 105 resulta em 1010 opera ̧c ̃oes (TLE).
A solu ̧c ̃ao eficiente utiliza Soma de Prefixos (Prefix Sums). Constru ́ımos uma matriz auxil- iar freq[N+1][10], onde freq[i][d] armazena quantas vezes o d ́ıgito d apareceu nas primeiras i posi ̧c ̃oes da barra.
Assim, para saber quantos d ́ıgitos d existem no intervalo [L, R], fazemos:
Quantidade = freq[R][d] − freq[L − 1][d]
Essa opera ̧c ̃ao ́e O(1).
Detalhe do Pivˆo: Ao mover de A → B e depois de B → C, a posi ̧c ̃ao B ́e o fim do primeiro movimento e o in ́ıcio do segundo. Para n ̃ao contar B duas vezes, a l ́ogica ́e:
Primeiro movimento (P1 → P2): Contamos o intervalo completo [P1, P2].
Pr ́oximos movimentos (Pant → Patual): Contamos o intervalo excluindo o in ́ıcio.
const fs = require (’fs ’) ;
// --- FAST I/O SETUP ---
const buffer = fs . readFileSync (0) ;
let bufferIdx = 0;
function readInt () {
let res = 0;
while ( bufferIdx < buffer . length && buffer [ bufferIdx ] <= 32) bufferIdx ++;
if ( bufferIdx >= buffer . length ) return null ;
while ( bufferIdx < buffer . length && buffer [ bufferIdx ] > 32) {
res = res * 10 + ( buffer [ bufferIdx ++] - 48) ;
}
return res ;
}
function solve () {
const N = readInt () ;
const M = readInt () ;
if ( N === null ) return ;
// Matriz de Soma de Prefixos
// counts [i][d] = quantas vezes o digito ’d’ aparece em barra [0...i -1]
// Usamos Int32Array para performance e memoria
// Achatamos a matriz : index = i * 10 + d
const counts = new Int32Array (( N + 1) * 10) ;
// Leitura da Barra e Construcao do Prefix Sum
for ( let i = 1; i <= N ; i ++) {
const val = readInt () ;
// Copia os valores da posicao anterior
for ( let d = 0; d < 10; d ++) {
counts [ i * 10 + d ] = counts [( i - 1) * 10 + d ];
}
// Incrementa o digito atual
counts [ i * 10 + val ]++;
}
const result = new Int32Array (10) ;
// Leitura dos Movimentos
let prevPos = readInt () ; // Posicao 1 - based
// O primeiro movimento nao existe " anterior " ,
// mas precisamos contar o numero onde ele comeca ?
// O enunciado diz " deslizar DA posicao inicial ATE a proxima ".
// A logica padrao eh: 1o movimento conta start e end .
// Proximos contam so end ( pois start ja foi contado ).
// Vamos processar o primeiro movimento separadamente ou tratar tudo no loop ?
// Estrategia : Somar intervalos .
// Para o movimento i -> j: somar (min (i,j), max (i,j)).
// Porem , isso conta os pivos 2x.
// Entao subtraimos o valor da posicao ’prevPos ’ a cada iteracao ,
// EXCETO na primeira vez (ou somamos prevPos manualmente no final ).
// Melhor abordagem : Intervalo semi - aberto para movimentos subsequentes .
// Movimento 1 ( inicio -> dest ): Intervalo [inicio , dest ] ( Inclusivo )
for ( let k = 1; k < M ; k ++) {
const currPos = readInt () ;
let start , end ;
if ( k === 1) {
// Primeiro movimento : Inclusivo total
start = Math . min ( prevPos , currPos ) ;
end = Math . max ( prevPos , currPos ) ;
} else {
// Movimentos seguintes : Exclui o ponto de partida (ja contado )
if ( currPos > prevPos ) {
start = prevPos + 1;
end = currPos ;
} else {
start = currPos ;
end = prevPos - 1;
}
}
// Soma usando Prefix Sum
for ( let d = 0; d < 10; d ++) {
const countInRange = counts [ end * 10 + d ] - counts [( start - 1) * 10 +
;
result [ d ] += countInRange ;
}
prevPos = currPos ;
}
// Formata saida
console . log ( result . join (’ ’) ) ;
}
solve () ;A turma do col ́egio vai fazer uma excurs ̃ao na serra e todos os alunos e monitores v ̃ao tomar um telef ́erico para subir at ́e o pico de uma montanha. A cabine do telef ́erico pode levar C pessoas no m ́aximo, contando alunos e monitores.
Por quest ̃ao de seguran ̧ca, tem que ter pelo menos um monitor dentro da cabine junto com os alunos. Por exemplo, se cabem C = 10 pessoas e a turma tem A = 20 alunos:
Dados a capacidade C da cabine e o n ́umero total A de alunos, calcule o n ́umero m ́ınimo de viagens.
A primeira linha cont ́em um inteiro C, a capacidade da cabine. A segunda linha cont ́em um inteiro A, o n ́umero total de alunos.
Imprima uma linha contendo um n ́umero inteiro representando o n ́umero m ́ınimo de viagens.
10 20
3
12 55
5
100 87
1
O problema se resume a uma divis ̃ao arredondada para cima (fun ̧c ̃ao teto ou ceil). Sabemos que em cada viagem um lugar ́e obrigatoriamente do monitor. Logo, a capacidade de transporte de alunos por viagem ́e:
Capacidade Efetiva = C − 1
O n ́umero de viagens necess ́arias ́e quantos grupos de tamanho (C − 1) conseguimos formar com
A alunos. Se sobrar qualquer resto, precisamos de uma viagem extra. Matematicamente:
Viagens = A C − 1
var input = require (’fs ’) . readFileSync (’/dev / stdin ’, ’utf8 ’) ;
var lines = input . trim () . split (/\ s +/) ;
var C = parseInt ( lines [0]) ;
var A = parseInt ( lines [1]) ;
// Capacidade real para alunos ( tira o lugar do monitor )
var capacidadeAlunos = C - 1;
// Calculamos a divisao arredondada para cima ( Ceil )
// Ex: 20 / 9 = 2.22 -> Math . ceil (2.22) = 3
var viagens = Math . ceil ( A / capacidadeAlunos ) ;
console . log ( viagens ) ;