n fireflies sit in a row.
The row is written as a string of length n, where O (capital letter O) is a firefly whose light is on and . (a period) is a firefly whose light is off.
Every second, all fireflies look at the current state and change at the same time.
A firefly that is on now turns off.
A firefly that is off now turns on only if exactly one of its direct neighbours is on now.
If no neighbour is on, or both neighbours are on, it stays off.
The direct neighbours are the one on the left and the one on the right, and the fireflies at the two ends of the row have only one neighbour (the first and the last of the row are not neighbours).
Find the state of the row after t seconds, and the sum of the numbers of fireflies that were on at each moment from 1 second later to t seconds later.
The row of the example becomes O....O. after 1 second, .O..O.O after 2 seconds and O.OO... after 3 seconds.
The numbers that are on are 2, 3 and 3, so the sum is 8.
Input
The first line has n and t (1 ≤ n ≤ 200, 1 ≤ t ≤ 200) separated by one space, and the second line has a string of length n for the starting state. The string consists only of O and .
Output
On the first line, the state of the row after t seconds (a string of length n); on the second line, the sum of the numbers of fireflies that were on
Example 1 · stdin
7 3
.OO.O..
stdout
O.OO...
8
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
Everyone changes at once by looking at 'now', so the next state has to be written into a different array from the current one. How you make a new array differs by language: [0] * n in Python, new Array(n).fill(0) in JS and TS, new int[n] in Java and C#, vector<int> next(n, 0) in C++, and NewList(n, 0) in Craykon. In C you keep two arrays and move one with memcpy (a C array cannot be assigned with =). Trap one: nxt = cur is not a copy. For a Python list, a JS array, a Java or C# array and a Craykon list, = only gives the same array one more name, so writing the next state changes the current one and the firefly on the right sees a left neighbour that has already changed. The example then gives .O..... and 4. Only C++'s vector copies the whole content with cur = next. Trap two: at the ends of the row there is only one neighbour. If you read cur[i - 1] without asking whether i > 0, Python reads cur[-1] as the last cell, and the first and last of the row become neighbours. The example then gives ..OO... and 7. The same code stops with ArrayIndexOutOfBoundsException in Java and IndexOutOfRangeException in C#, and Craykon also stops, saying there is no such position. JS gives undefined, which becomes NaN when added, and in C and C++ the result is not defined. Trap three: if you read 'exactly one' as 'at least one', a firefly with both neighbours on turns on too. The example then gives O..O.O. and 10. This solution counts the neighbours that are on and asks whether near == 1.
Pythonmain.py · 16 lines
n, t = map(int, input().split())cur = [1 if c == "O" else 0 for c in input()]total = 0for _ in range(t): nxt = [0] * n # 다음 순간은 새 리스트에 적는다: 모두가 '지금'을 보고 한꺼번에 바뀐다 for i in range(n): near = 0 # 켜진 이웃의 수 if i > 0: near += cur[i - 1] if i < n - 1: near += cur[i + 1] nxt[i] = 1 if cur[i] == 0 and near == 1 else 0 cur = nxt total += sum(cur)print("".join("O" if x else "." for x in cur))print(total)
JavaScriptmain.js · 18 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, t] = lines[0].split(" ").map(Number);let cur = [];for (let i = 0; i < n; i++) cur.push(lines[1][i] === "O" ? 1 : 0);let total = 0;for (let s = 0; s < t; s++) { const next = new Array(n).fill(0); // 다음 순간은 새 배열에 적는다 for (let i = 0; i < n; i++) { let near = 0; // 켜진 이웃의 수 if (i > 0) near += cur[i - 1]; if (i < n - 1) near += cur[i + 1]; next[i] = cur[i] === 0 && near === 1 ? 1 : 0; total += next[i]; } cur = next;}console.log(cur.map((x) => (x ? "O" : ".")).join(""));console.log(total);
TypeScriptmain.ts · 20 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, t] = lines[0].split(" ").map(Number);let cur: number[] = [];for (let i = 0; i < n; i++) cur.push(lines[1][i] === "O" ? 1 : 0);let total = 0;for (let s = 0; s < t; s++) { const next: number[] = new Array<number>(n).fill(0); // 다음 순간은 새 배열에 적는다 for (let i = 0; i < n; i++) { let near = 0; // 켜진 이웃의 수 if (i > 0) near += cur[i - 1]; if (i < n - 1) near += cur[i + 1]; next[i] = cur[i] === 0 && near === 1 ? 1 : 0; total += next[i]; } cur = next;}console.log(cur.map((x) => (x ? "O" : ".")).join(""));console.log(total);
JavaMain.java · 30 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().split(" "); int n = Integer.parseInt(first[0]), t = Integer.parseInt(first[1]); String row = br.readLine(); int[] cur = new int[n]; for (int i = 0; i < n; i++) cur[i] = row.charAt(i) == 'O' ? 1 : 0; int total = 0; for (int s = 0; s < t; s++) { int[] next = new int[n]; // 다음 순간은 새 배열에 적는다 for (int i = 0; i < n; i++) { int near = 0; // 켜진 이웃의 수 if (i > 0) near += cur[i - 1]; if (i < n - 1) near += cur[i + 1]; next[i] = cur[i] == 0 && near == 1 ? 1 : 0; total += next[i]; } cur = next; } StringBuilder sb = new StringBuilder(); for (int x : cur) sb.append(x == 1 ? 'O' : '.'); System.out.println(sb); System.out.println(total); }}
C#Main.cs · 32 lines
using System;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine()!.Split(' '); int n = int.Parse(first[0]), t = int.Parse(first[1]); string row = Console.ReadLine()!; int[] cur = new int[n]; for (int i = 0; i < n; i++) cur[i] = row[i] == 'O' ? 1 : 0; int total = 0; for (int s = 0; s < t; s++) { int[] next = new int[n]; // 다음 순간은 새 배열에 적는다 for (int i = 0; i < n; i++) { int near = 0; // 켜진 이웃의 수 if (i > 0) near += cur[i - 1]; if (i < n - 1) near += cur[i + 1]; next[i] = cur[i] == 0 && near == 1 ? 1 : 0; total += next[i]; } cur = next; } var sb = new StringBuilder(); foreach (int x in cur) sb.Append(x == 1 ? 'O' : '.'); Console.WriteLine(sb); Console.WriteLine(total); }}
C++main.cpp · 27 lines
#include <iostream>#include <string>#include <vector>using namespace std;int main() { int n, t; string row; cin >> n >> t >> row; vector<int> cur(n); for (int i = 0; i < n; i++) cur[i] = row[i] == 'O'; int total = 0; for (int s = 0; s < t; s++) { vector<int> next(n, 0); // 다음 순간은 새 vector에 적는다 for (int i = 0; i < n; i++) { int near = 0; // 켜진 이웃의 수 if (i > 0) near += cur[i - 1]; if (i < n - 1) near += cur[i + 1]; next[i] = cur[i] == 0 && near == 1; total += next[i]; } cur = next; // vector의 = 는 내용을 통째로 복사한다 } for (int x : cur) cout << (x ? 'O' : '.'); cout << '\n' << total << '\n'; return 0;}
Cmain.c · 24 lines
#include <stdio.h>#include <string.h>int main(void) { int n, t; char row[201]; int cur[200], next[200]; if (scanf("%d %d %200s", &n, &t, row) != 3) return 0; for (int i = 0; i < n; i++) cur[i] = row[i] == 'O'; int total = 0; for (int s = 0; s < t; s++) { for (int i = 0; i < n; i++) { int near = 0; /* 켜진 이웃의 수 */ if (i > 0) near += cur[i - 1]; if (i < n - 1) near += cur[i + 1]; next[i] = cur[i] == 0 && near == 1; /* 다음 순간은 다른 배열에 적는다 */ total += next[i]; } memcpy(cur, next, sizeof(int) * n); /* C 배열은 = 로 옮길 수 없다 */ } for (int i = 0; i < n; i++) putchar(cur[i] ? 'O' : '.'); printf("\n%d\n", total); return 0;}
Craykonmain.cray · 53 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];t = 첫줄[1];row = Console.ReadLine();cur = [];for (i = 0; i < n; i++){ if (row[i] == "O") { cur.Add(1); } else { cur.Add(0); }}total = 0;for (s = 0; s < t; s++){ next = NewList(n, 0); // 다음 순간은 새 목록에 적는다 for (i = 0; i < n; i++) { near = 0; // 켜진 이웃의 수 if (i > 0) { near += cur[i - 1]; } if (i < n - 1) { near += cur[i + 1]; } if (cur[i] == 0 && near == 1) { next[i] = 1; total += 1; } } cur = next;}result = "";foreach (x in cur){ if (x == 1) { result += "O"; } else { result += "."; }}Console.WriteLine(result);Console.WriteLine(total);