포켓몬 전공의 친근한 인상을 가진 Oak 교수는 지금까지도 포켓몬의 조상에 대한 많은 질문을 고민해 왔다.

많은 포켓몬 트레이너가 심각하게 생각하는 것 중 하나는 자신의 포켓몬 도감에 있는 포켓몬들의 공통 조상을 찾는 것이다. 자세하게는, 각 포켓몬 트레이너는 “자신이 가진 포켓몬 중 정확히 L마리에게만 조상이 되는” 포켓몬의 수를 알고 싶어 한다. L의 값은, 물론, 질문하는 트레이너가 결정하는 값이다.

포켓몬 월드에서, 포켓몬 A와 포켓몬 B의 유전자가 주어졌을 때, 포켓몬 A가 포켓몬 B의 조상인 것과 포켓몬 A의 유전자가 포켓몬 B의 유전자의 접두사인 것은 동치이다. 또한, 모든 빈 문자열이 아닌 유전자 문자열에 대해, 각 유전자를 가진 포켓몬은 포켓몬 월드에 항상 존재한다.

Oak 교수의 포켓몬 유전자 데이터베이스가 주어졌을 때, 트레이너의 질문에 답해주자.

#3720 upload 2 done 1 how_to_reg 1

Pokegene timer 2s memory 512MB

#3720

Pokegene 2s 512MB