Counting two neighboring colors in a grouped bead design
There is a design for threading beads in a row. The color of a bead is written as one lowercase English letter.
A design is one or more pieces written one after another with no spaces. A piece is either a single bead or a group.
A group is written as k(design) and means that the design inside the parentheses is threaded k times in a row.
For example, threading by a2(bc) gives abcbc, and threading by 2(a2(b)) gives abbabb.
Each design comes with two letters xy. Find how many places in the fully threaded row have a bead of color x immediately followed by a bead of color y.
The first line gives the number of designs t.
Each of the next t lines gives the two letters xy and a design, separated by a single space.
For each design, print the number of places on its own line.
Input
1 ≤ t ≤ 20. x and y are lowercase English letters and may be equal. The total length of the designs is at most 100,000. k is an integer from 1 to 10^9 and does not start with 0. The design inside parentheses is never empty. Groups are nested at most 3,000 deep. The fully threaded row has at most 10^15 beads
Output
For each design, the number of places where x is immediately followed by y, one per line
Example 1 · stdin
5
ba 3(ab)
ab a2(b)
ab 2(ca)b
ba 2(3(a)b)
aa 12(a)
stdout
2
1
1
1
11
Example 2 · stdin
2
ab 1000000(1000000(ab))
xy 3(x2(y))
stdout
1000000000000
3
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The threaded row can have up to 10^15 beads, so actually unfolding the design and counting never finishes in any language. Instead, remember just three things per group: the number of places counted inside it, its first bead and its last bead. On ( push what has been read so far onto a stack and start fresh; on ) pop it and merge. When the inner group repeats k times its count is multiplied by k, and if its last bead is x and its first bead is y, the k - 1 seams between repetitions are added. For the stack, Python uses append/pop of tuples on a list and JS uses push/pop on an array. In TS the type of stack.pop() is Frame | undefined, so using it directly is a type error (TS18048) and you have to say as Frame. Java uses push/pop of ArrayDeque<long[]>, and C# uses Push/Pop of a Stack<...> holding tuples. C builds it by hand from an array of structs and a top index. In C++ pop() of std::stack returns nothing, so read with top() first and then pop(). Craykon stacks with Add on four lists, reads the last value and removes it with RemoveAt. The answer can be close to 10^15, so Java and C# hold it in long, and C and C++ in long long. A JS/TS number and a Craykon number are exact in this range, and Python integers have no size limit. Trap one: do not forget the seams between repetitions. ba 3(ab) is ababab, so the answer is 2, but you get 0. Trap two: the bead right before a group and the first bead of the group are neighbors too. ab a2(b) is abb, so the answer is 1, but without counting it you get 0. Trap three: after a group closes, the last bead is the last bead of that group. Without the update, ab 2(ca)b (cacab) gives 0 instead of 1. Trap four: when a group starts with a group, the first bead of the inner group is the first bead of the outer group. Without passing it up, ba 2(3(a)b) (aaabaaab) gives 0 instead of 1. Trap five: a count can have several digits. Keeping only the last digit makes aa 12(a) give 1 instead of 11. Trap six: holding the number of places in an int in Java makes the first line of the second example -727379968 instead of 1000000000000. Trap seven: in Python, calling a function again for each group instead of using a stack dies with RecursionError on a design nested 3,000 deep. The examples do not show this. Trap eight: in Craykon, really reading a group as many times as its count stops on the first line of the second example with a 'Took too long' message.
Pythonmain.py · 46 lines
import sysdef count_pairs(x, y, design): """다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수""" stack = [] # 바깥 묶음들: (자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수) count, first, last = 0, "", "" # 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" times = 0 for ch in design: if ch.isdigit(): times = times * 10 + int(ch) elif ch == "(": stack.append((count, first, last, times)) count, first, last, times = 0, "", "", 0 elif ch == ")": in_count, in_first, in_last = count, first, last count, first, last, k = stack.pop() total = in_count * k if in_last == x and in_first == y: # 되풀이 사이의 이음매 k - 1곳 total += k - 1 if last == x and in_first == y: # 묶음 앞 구슬과 묶음의 첫 구슬 사이 total += 1 count += total if first == "": first = in_first last = in_last else: if last == x and ch == y: count += 1 if first == "": first = ch last = ch return countdef main(): lines = sys.stdin.read().split("\n") t = int(lines[0]) out = [] for line in lines[1:t + 1]: pair, design = line.split() out.append(str(count_pairs(pair[0], pair[1], design))) print("\n".join(out))main()
JavaScriptmain.js · 40 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수function countPairs(x, y, design) { const stack = []; // 바깥 묶음들: [자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수] let count = 0, first = "", last = ""; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" let times = 0; for (const ch of design) { if (ch >= "0" && ch <= "9") { times = times * 10 + Number(ch); } else if (ch === "(") { stack.push([count, first, last, times]); count = 0; first = ""; last = ""; times = 0; } else if (ch === ")") { const inCount = count, inFirst = first, inLast = last; const outer = stack.pop(); count = outer[0]; first = outer[1]; last = outer[2]; const k = outer[3]; let total = inCount * k; // 10^15 이하라서 number로 정확하다 if (inLast === x && inFirst === y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last === x && inFirst === y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first === "") first = inFirst; last = inLast; } else { if (last === x && ch === y) count += 1; if (first === "") first = ch; last = ch; } } return count;}const t = Number(lines[0]);const out = [];for (let i = 1; i <= t; i++) { const [pair, design] = lines[i].trim().split(" "); out.push(countPairs(pair[0], pair[1], design));}console.log(out.join("\n"));
TypeScriptmain.ts · 49 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");// 바깥 묶음 하나: 자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수interface Frame { count: number; first: string; last: string; times: number;}// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수function countPairs(x: string, y: string, design: string): number { const stack: Frame[] = []; let count = 0, first = "", last = ""; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" let times = 0; for (const ch of design) { if (ch >= "0" && ch <= "9") { times = times * 10 + Number(ch); } else if (ch === "(") { stack.push({ count, first, last, times }); count = 0; first = ""; last = ""; times = 0; } else if (ch === ")") { const inCount = count, inFirst = first, inLast = last; const outer = stack.pop() as Frame; // 도안이 올바르므로 스택은 비어 있지 않다 count = outer.count; first = outer.first; last = outer.last; const k = outer.times; let total = inCount * k; // 10^15 이하라서 number로 정확하다 if (inLast === x && inFirst === y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last === x && inFirst === y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first === "") first = inFirst; last = inLast; } else { if (last === x && ch === y) count += 1; if (first === "") first = ch; last = ch; } } return count;}const t = Number(lines[0]);const out: number[] = [];for (let i = 1; i <= t; i++) { const [pair, design] = lines[i].trim().split(" "); out.push(countPairs(pair[0], pair[1], design));}console.log(out.join("\n"));
JavaMain.java · 49 lines
import java.io.*;import java.util.*;public class Main { // 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 static long countPairs(char x, char y, String design) { // 바깥 묶음들을 쌓아 두는 스택. 구슬이 아직 없으면 첫 구슬과 끝 구슬은 0 ArrayDeque<long[]> stack = new ArrayDeque<>(); // {자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수} long count = 0, times = 0; char first = 0, last = 0; for (int i = 0; i < design.length(); i++) { char ch = design.charAt(i); if (Character.isDigit(ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.push(new long[]{count, first, last, times}); count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long inCount = count; char inFirst = first, inLast = last; long[] outer = stack.pop(); count = outer[0]; first = (char) outer[1]; last = (char) outer[2]; long k = outer[3]; long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == 0) first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < t; i++) { String[] parts = br.readLine().trim().split(" "); sb.append(countPairs(parts[0].charAt(0), parts[0].charAt(1), parts[1])).append('\n'); } System.out.print(sb); }}
C#Main.cs · 59 lines
using System;using System.Collections.Generic;using System.Text;class Program{ // 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 static long CountPairs(char x, char y, string design) { // 바깥 묶음들을 쌓아 두는 스택. 구슬이 아직 없으면 첫 구슬과 끝 구슬은 '\0' var stack = new Stack<(long count, char first, char last, long times)>(); long count = 0, times = 0; char first = '\0', last = '\0'; foreach (char ch in design) { if (char.IsDigit(ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.Push((count, first, last, times)); count = 0; first = '\0'; last = '\0'; times = 0; } else if (ch == ')') { long inCount = count; char inFirst = first, inLast = last; long k; (count, first, last, k) = stack.Pop(); long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == '\0') first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == '\0') first = ch; last = ch; } } return count; } static void Main() { int t = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int i = 0; i < t; i++) { string[] parts = Console.ReadLine()!.Trim().Split(' '); sb.Append(CountPairs(parts[0][0], parts[0][1], parts[1])).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 57 lines
#include <cctype>#include <iostream>#include <stack>#include <string>// 바깥 묶음 하나. 구슬이 아직 없으면 first와 last는 0struct Frame { long long count; char first, last; long long times;};// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수long long countPairs(char x, char y, const std::string& design) { std::stack<Frame> stack; long long count = 0, times = 0; char first = 0, last = 0; for (char ch : design) { if (std::isdigit(static_cast<unsigned char>(ch))) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.push({count, first, last, times}); count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long long inCount = count; char inFirst = first, inLast = last; Frame outer = stack.top(); // top()은 보기만 하고, 꺼내는 것은 pop()이다 stack.pop(); count = outer.count; first = outer.first; last = outer.last; long long k = outer.times; long long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == 0) first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; for (int i = 0; i < t; i++) { std::string pair, design; std::cin >> pair >> design; std::cout << countPairs(pair[0], pair[1], design) << "\n"; } return 0;}
Cmain.c · 59 lines
#include <stdio.h>#include <ctype.h>#define MAX_LEN 100000#define MAX_DEPTH 3000/* 바깥 묶음 하나. 구슬이 아직 없으면 first와 last는 0 */typedef struct { long long count; char first, last; long long times;} Frame;static char design[MAX_LEN + 2];static Frame stack[MAX_DEPTH];/* 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 */static long long count_pairs(char x, char y, const char *s) { int top = 0; long long count = 0, times = 0; char first = 0, last = 0; for (int i = 0; s[i] != '\0'; i++) { char ch = s[i]; if (isdigit((unsigned char)ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack[top++] = (Frame){count, first, last, times}; count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long long in_count = count; char in_first = first, in_last = last; Frame outer = stack[--top]; count = outer.count; first = outer.first; last = outer.last; long long k = outer.times; long long total = in_count * k; /* int로는 넘친다 */ if (in_last == x && in_first == y) total += k - 1; /* 되풀이 사이의 이음매 k - 1곳 */ if (last == x && in_first == y) total += 1; /* 묶음 앞 구슬과 묶음의 첫 구슬 사이 */ count += total; if (first == 0) first = in_first; last = in_last; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count;}int main(void) { int t; char pair[4]; if (scanf("%d", &t) != 1) return 1; for (int i = 0; i < t; i++) { if (scanf("%3s %100000s", pair, design) != 2) return 1; printf("%lld\n", count_pairs(pair[0], pair[1], design)); } return 0;}
Craykonmain.cray · 81 lines
// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수자리세기(x, y, 도안){ // 바깥 묶음들을 쌓아 두는 스택. 묶음마다 자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수 쌓은수 = []; 쌓은첫 = []; 쌓은끝 = []; 쌓은횟수 = []; 수 = 0; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 첫과 끝은 "" 첫 = ""; 끝 = ""; 횟수 = 0; foreach (ch in 도안) { if (ch >= "0" && ch <= "9") { 횟수 = 횟수 * 10 + ch.ToNumber(); } else if (ch == "(") { 쌓은수.Add(수); 쌓은첫.Add(첫); 쌓은끝.Add(끝); 쌓은횟수.Add(횟수); 수 = 0; 첫 = ""; 끝 = ""; 횟수 = 0; } else if (ch == ")") { 안수 = 수; 안첫 = 첫; 안끝 = 끝; 위 = 쌓은수.Count - 1; // 스택의 맨 위에서 바깥 묶음을 꺼낸다 수 = 쌓은수[위]; 첫 = 쌓은첫[위]; 끝 = 쌓은끝[위]; k = 쌓은횟수[위]; 쌓은수.RemoveAt(위); 쌓은첫.RemoveAt(위); 쌓은끝.RemoveAt(위); 쌓은횟수.RemoveAt(위); 모두 = 안수 * k; if (안끝 == x && 안첫 == y) { 모두 += k - 1; } if (끝 == x && 안첫 == y) { 모두 += 1; } 수 += 모두; if (첫 == "") { 첫 = 안첫; } 끝 = 안끝; } else { if (끝 == x && ch == y) { 수 += 1; } if (첫 == "") { 첫 = ch; } 끝 = ch; } } return 수;}t = Console.ReadLine().ToNumber();for (i = 0; i < t; i++){ parts = Console.ReadLine().Trim().Split(" "); Console.WriteLine(자리세기(parts[0][0], parts[0][1], parts[1]));}