문자열 방정식

시간 제한1초메모리 제한128 MB

요약
여러 개의 서로 다른 짧은 문자열과 그 반복을 두 쪽으로 나누어, 양쪽에 쓰인 문자 구성이 같아지도록 만들 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
수학, 정수론, 동적 계획법, 해시맵
정답자
아직 제출이 없습니다

문제

3+8=4+73 + 8 = 4 + 7 과 같은 수식은 누구나 이해할 수 있습니다. 그런데 숫자 대신 문자열을 다룬다면 어떻게 될까요? 덧셈과 같음은 각각 어떤 의미가 될까요?

두 문자열 xx 와 yy 에 대하여, x+yx + y 를 두 문자열을 이어 붙인 것(연결)으로 정의합니다. 또한 x=yx = y 는 xx 가 yy 의 애너그램(anagram)임을, 즉 xx 의 문자들을 재배열하여 yy 를 만들 수 있음을 뜻하는 것으로 정의합니다.

서로 다른, 비어 있지 않은 문자열 nn 개가 주어집니다. 각 문자열은 최대 1010 개의 소문자로 이루어져 있습니다. 또한 모든 문자열에 등장하는 서로 다른 문자는 최대 1010 종류라고 가정할 수 있습니다. 위 정의에 따라, 어떤 문자열들을 방정식의 왼쪽에 두고 또 어떤 문자열들을 오른쪽에 두어서 양변의 "합"이 서로 "같도록" 만들 수 있는지 판별하십시오. 각 문자열은 한 변에서 00 번 이상 사용할 수 있지만, 어떤 문자열도 양변에 동시에 나타날 수는 없으며, 양변 모두 적어도 하나의 문자열을 사용해야 합니다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 각 테스트 케이스는 정수 nn (2≤n≤1002 \le n \le 100) 이 적힌 줄로 시작합니다. 이어지는 nn 개의 줄에는 nn 개의 문자열이 한 줄에 하나씩 주어집니다. 입력은 n=0n = 0 인 줄로 끝나며, 이 줄은 처리하지 않습니다.

출력

각 테스트 케이스마다, 위와 같은 방정식을 만들 수 있으면 yes 를, 그렇지 않으면 no 를 한 줄에 출력하십시오.

예제7

  1. 예제 1

    입력
    2
    hello
    world
    7
    i
    am
    lord
    voldemort
    tom
    marvolo
    riddle
    0
    
    예상 출력
    no
    yes
    
  2. 예제 2

    입력
    2
    ab
    ba
    0
    
    예상 출력
    yes
    
  3. 예제 3

    입력
    2
    ab
    cd
    0
    
    예상 출력
    no
    
  4. 예제 4

    입력
    3
    a
    b
    ab
    0
    
    예상 출력
    yes
    
  5. 예제 5

    입력
    3
    aa
    ab
    bb
    0
    
    예상 출력
    yes
    
  6. 예제 6

    입력
    3
    a
    b
    c
    0
    
    예상 출력
    no
    
  7. 예제 7

    입력
    2
    abc
    cba
    3
    x
    y
    z
    2
    mango
    tango
    0
    
    예상 출력
    yes
    no
    no