codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2269B.md (2741B)


      1 Source: https://codeforces.com/problemset/problem/2269/B
      2 
      3 B. KiaKio and Squared Numbers
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Kia and Kio spent the summer at the port of Mehragan, where $n$ lighthouses stand on the cliffs facing the dark sea.
     22 
     23 The lighthouses of Mehragan do not give light. Every night a number is written in fire on each of them, and the sailors read their way from those numbers.
     24 
     25 The law of the lighthouses is this: if a lighthouse shows $x$ tonight, then tomorrow night it shows the sum of the squares of the decimal digits of $x$.
     26 
     27 For example, a lighthouse showing $23$ will show $2^2+3^2=13$ tomorrow, then $1^2+3^2=10$, and then $1$.
     28 
     29 On night $0$ of the season, lighthouse $i$ shows the number $a_i$. From that night on, the law is applied once every night, forever.
     30 
     31 Kio calls two lighthouses $i$ and $j$ in tune if there exists a night after which, forever, both of them show exactly the same number on every single night.
     32 
     33 Kia asks: how many pairs $(i, j)$ with $i \lt j$ are in tune?
     34 
     35 Input
     36 
     37 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
     38 
     39 Each test case consists of two lines.
     40 
     41 The first line of each test case contains a single integer $n$ ($1 \le n \le 1000$) — the number of lighthouses.
     42 
     43 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the number shown by each lighthouse on night $0$.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
     46 
     47 Output
     48 
     49 For each test case, print a single integer — the number of pairs $(i, j)$ with $i \lt j$ such that lighthouses $i$ and $j$ are in tune.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 4
     57 
     58 5
     59 
     60 7 4 16 4 2
     61 
     62 4
     63 
     64 1 7 10 100
     65 
     66 3
     67 
     68 4 16 37
     69 
     70 3
     71 
     72 2 20 4
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 1
     79 
     80 6
     81 
     82 0
     83 
     84 1
     85 ```
     86 
     87 Note
     88 
     89 In the first test case:
     90 
     91 * Lighthouse $1$ starts at $7$: $7 \to 49 \to 97 \to 130 \to 10 \to 1$, and it stays at $1$ forever.
     92 * Lighthouses $2$ and $4$ both start at $4$, so they show the same number on every night.
     93 * Lighthouse $3$ starts at $16$ and lighthouse $5$ starts at $2$; each of them is at a different point of the cycle Kio found, and never matches anybody.
     94 
     95 So the only pair in tune is $(2, 4)$, and the answer is $1$.
     96 
     97 In the second test case, every lighthouse sooner or later reaches $1$ and stays there, so all of them are pairwise in tune, which gives $6$ pairs.
     98 
     99 In the fourth test case, on night $1$, lighthouse $2$ shows $2^2+0^2 = 4$, and lighthouse $1$ shows $2^2 = 4$. From night $1$ on, they are identical forever. Lighthouse $3$ starts at $4$, so it is one night ahead of both of them and is in tune with neither.