InternationalOlympiadinInformatics2015
26thJuly-2ndAugust2015
Almaty,Kazakhstan
Day1
teams
Language:en-PRT
Teams
Háumaclassede estudantes,numeradosde a
.Cadadiaoprofessordaclassetem
algunsprojetosparaosestudantes.Cadaprojetotemqueserexecutadoporumaequipadeestudantes
nessemesmodia.Osprojetospodemterdificuldadesvariadas.Paracadaprojeto,oprofessorsabeo
tamanhoexatodeumaequipaquedevetrabalharnesseprojeto.
Estudantesdiferentespodempreferirtrabalharemequipasdediferentestamanhos.Mais
precisamente,oestudante somentepodeseralocadoaumaequipadetamanhoentre
e
inclusive.Acadadia,umestudantepodeseralocadoanomáximoumaequipa.Algunsestudantes
podemnãoseralocadosanenhumaequipa.Cadaequipatrabalharáemumúnicoprojeto.
Oprofessorjáescolheuosprojetosparacadaumdospróximos dias.Paracadaumdesses dias,
determineseépossívelalocarestudantesaequipasdetalformaqueexistaumaequipatrabalhando
emcadaprojeto.
Exemplo
Suponhaqueexistam
estudantese
dias.Asrestriçõesdosestudantesparaos
tamanhosdasequipassãodadasnatabelaabaixo.
estudante 0 1 2 3
1 2 2 2
2 3 3 4
Noprimeirodiahá
projetos.Ostamanhosdasequipasdevemser
e
.
Estasduasequipaspodemserformadasalocandooestudante0aumaequipadetamanho1eos
demaisestudantesaumaequipadetamanho3.
Nosegundodiahánovamente
projetos,masdestavezostamanhosdasequipasdevemser
e
.Nestecasonãoépossívelformarasequipas,poisexisteapenasum
estudantequepodeestaremumaequipadetamanho1.
Tarefa
Vocêreceberáadescriçãodetodososestudantes: , e ,assimcomoumasequênciade
questões—umasobrecadadia.Cadaquestãoconsistedeumnúmero deprojetosnaquelediae
umasequência detamanho contendoostamanhosrequeridosdasequipas.Paracadaquestão,
seuprogramadeveretornarseépossívelformartodasasequipas.
Vocêdeveimplementarasfunçõesinitecan:
init(N,A,B)—Oavaliadorchamaráestafunçãonoinício,umaúnicavez.
1/2
N:onúmerodeestudantes.
A:umvetordecomprimentoN:A[i]éotamanhomínimodaequipaparaoestudante .
B:umvetordecomprimentoN:B[i]éotamanhomáximodaequipaparaoestudante .
Afunçãonãoretornaqualquervalor.
Vocêpodeconsiderarque
A[i] B[i] Nparacada
N
.
can(M,K)—Apóschamarinitumavez,oavaliadorchamaráestafunção vezes
consecutivas,umaparacadadia.
M:onúmerodeprojetosparaessedia.
K:umvetordecomprimentoMcontendootamanhodaequiparequeridoparacadaum
dessesprojetos.
Afunçãodeveretornar1seépossívelformartodasasequipas,e0casocontrário.
Vocêpodeconsiderarque
M N,equeparacada
K[i] N.NotequeasomadetodososK[i]podeexcederN.
M
temos
Subtarefas
Vamosdenotarpor asomadosvaloresdeMemtodasaschamadasacan(M,K).
subtarefa pontos
Restriçõesadicionais
1
2
3
4
nenhuma
nenhuma
21
13
43
23
Avaliadorexemplo
Oavaliadorexemplolêaentradanoseguinteformato:
linha1:N
linhas2,…,N+1:A[i]B[i]
linhaN+2:Q
linhasN+3,…,N+Q+2:MK[0]K[1]…K[M-1]
Paracadaquestão,oavaliadorexemploescrevenasaídaovalorretornadoporcan.
2/2