시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 346 | 77 | 43 | 19.545% |
1979년 댄 브리클린과 밥 프랜스턴은 첫 번째 스프레드시트 어플리케이션인 VisiCalc를 만들었다. 이 프로그램은 매우 크게 성공했으며, 애플 II 컴퓨터의 필수 앱이었다. 오늘날 스프레드시트는 대다수의 데스크탑 컴퓨터에 설치되어져 있다.
스프레드시트에 핵심이 되는 아이디어는 매우 간단하지만 강력하다. 스프레드시트는 표로 이루어져 있으며, 표의 각 칸은 정수나 수식으로 이루어져있다. 수식은 다른 칸에 쓰여 있는 값을 기반으로 계산된다.
오늘은 매우 간단한 스프레드시트 앱을 만들려고 한다. 스프레드시트의 각 칸은 정수나 수식으로 이루어져 있으며, 수식은 합만 지원한다. 스프레드시트의 각 칸에 적힌 정수나 수식이 주어졌을 때, 수식을 모두 계산해내는 프로그램을 작성하시오.
스프레드시트의 각 칸은 아래와 같이 번호가 매겨져 있다.
A1 B1 C1 D1 E1 F1 ... A2 B2 C2 D2 E2 F2 ... A3 B3 C3 D3 E3 F3 ... A4 B4 C4 D4 E4 F4 ... A5 B5 C5 D5 E5 F5 ... A6 B6 C6 D6 E6 F6 ... ... ... ... ... ... ... ...
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스의 첫째 줄에는 스프레드시트의 열의 개수 M과 행의 개수 N이 주어진다. 다음 줄부터 N개의 줄에는 스프레드시트의 내용이 주어진다. 각 행은 열의 정보가 주어지며, 공백으로 구분되어져 있다.
각각의 칸은 정수가 적혀있거나, 수식이 적혀있다. 수식은 =로 시작되며, 그 뒤에 칸의 이름이 +로 구분되어져서 주어진다. 수식의 값은 각 칸에 쓰여 있는 칸에 적혀져있는 수식을 모두 더한 값이다. 수식은 수식이 적혀있는 칸을 가리킬 수 있으며, 수식에는 공백이 주어지지 않는다.
가리키는 관계가 사이클을 이루는 경우는 없기 때문에, 항상 수식을 계산할 수 있다.
칸의 이름 중에서 행은 1부터 999까지의 정수로 나타내며, 열은 A, B, C, ..., Z, AA, AB, AC, ..., AZ, BA, ..., BZ, CA, ... ZZ, AAA, AAB, AAC, ... AAZ, ABA, ..., ABZ, ACA, ..., ZZZ 로 문자가 매겨져 있다. 각각의 열 번호는 1~18278번에 해당한다. 가장 왼쪽 위의 칸 번호는 A1이다.
각 칸에 적혀있는 수는 절댓값이 100,000보다 작거나 같은 정수이며, 수식의 값이 231-1을 넘어가는 경우는 없다. 또한, 각 테스트 케이스마다 총 칸 개수는 1,700,000개를 넘지 않으며, 수식이 다른 칸을 가리키는 총 횟수는 250,000개를 넘지 않는다.
각각의 테스트 케이스마다, 수식을 모두 계산해서 출력한다.
1 4 3 10 34 37 =A1+B1+C1 40 17 34 =A2+B2+C2 =A1+A2 =B1+B2 =C1+C2 =D1+D2
10 34 37 81 40 17 34 91 50 51 71 172
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 1995 F번