codeforces-scrape

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

1118B.md (3194B)


      1 Source: https://codeforces.com/problemset/problem/1118/B
      2 
      3 B. Tanya and Candies
      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 Tanya has $n$ candies numbered from $1$ to $n$. The $i$-th candy has the weight $a_i$.
     22 
     23 She plans to eat exactly $n-1$ candies and give the remaining candy to her dad. Tanya eats candies in order of increasing their numbers, exactly one candy per day.
     24 
     25 Your task is to find the number of such candies $i$ (let's call these candies good) that if dad gets the $i$-th candy then the sum of weights of candies Tanya eats in even days will be equal to the sum of weights of candies Tanya eats in odd days. Note that at first, she will give the candy, after it she will eat the remaining candies one by one.
     26 
     27 For example, $n=4$ and weights are $[1, 4, 3, 3]$. Consider all possible cases to give a candy to dad:
     28 
     29 * Tanya gives the $1$-st candy to dad ($a_1=1$), the remaining candies are $[4, 3, 3]$. She will eat $a_2=4$ in the first day, $a_3=3$ in the second day, $a_4=3$ in the third day. So in odd days she will eat $4+3=7$ and in even days she will eat $3$. Since $7 \ne 3$ this case shouldn't be counted to the answer (this candy isn't good).
     30 * Tanya gives the $2$-nd candy to dad ($a_2=4$), the remaining candies are $[1, 3, 3]$. She will eat $a_1=1$ in the first day, $a_3=3$ in the second day, $a_4=3$ in the third day. So in odd days she will eat $1+3=4$ and in even days she will eat $3$. Since $4 \ne 3$ this case shouldn't be counted to the answer (this candy isn't good).
     31 * Tanya gives the $3$-rd candy to dad ($a_3=3$), the remaining candies are $[1, 4, 3]$. She will eat $a_1=1$ in the first day, $a_2=4$ in the second day, $a_4=3$ in the third day. So in odd days she will eat $1+3=4$ and in even days she will eat $4$. Since $4 = 4$ this case should be counted to the answer (this candy is good).
     32 * Tanya gives the $4$-th candy to dad ($a_4=3$), the remaining candies are $[1, 4, 3]$. She will eat $a_1=1$ in the first day, $a_2=4$ in the second day, $a_3=3$ in the third day. So in odd days she will eat $1+3=4$ and in even days she will eat $4$. Since $4 = 4$ this case should be counted to the answer (this candy is good).
     33 
     34 In total there $2$ cases which should counted (these candies are good), so the answer is $2$.
     35 
     36 Input
     37 
     38 The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of candies.
     39 
     40 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the weight of the $i$-th candy.
     41 
     42 Output
     43 
     44 Print one integer — the number of such candies $i$ (good candies) that if dad gets the $i$-th candy then the sum of weights of candies Tanya eats in even days will be equal to the sum of weights of candies Tanya eats in odd days.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 7
     52 5 5 4 5 5 5 6
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 2
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 8
     65 4 8 8 7 8 4 4 5
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 2
     72 ```
     73 
     74 Input
     75 
     76 ```
     77 9
     78 2 3 4 2 2 3 2 2 4
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 3
     85 ```
     86 
     87 Note
     88 
     89 In the first example indices of good candies are $[1, 2]$.
     90 
     91 In the second example indices of good candies are $[2, 3]$.
     92 
     93 In the third example indices of good candies are $[4, 5, 9]$.