codeforces-scrape

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

177D2.md (2518B)


      1 Source: https://codeforces.com/problemset/problem/177/D2
      2 
      3 D2. Encrypting Messages
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 The Smart Beaver from ABBYY invented a new message encryption method and now wants to check its performance. Checking it manually is long and tiresome, so he decided to ask the ABBYY Cup contestants for help.
     22 
     23 A message is a sequence of *n* integers *a*1, *a*2, ..., *a**n*. Encryption uses a key which is a sequence of *m* integers *b*1, *b*2, ..., *b**m* (*m* ≤ *n*). All numbers from the message and from the key belong to the interval from 0 to *c* - 1, inclusive, and all the calculations are performed modulo *c*.
     24 
     25 Encryption is performed in *n* - *m* + 1 steps. On the first step we add to each number *a*1, *a*2, ..., *a**m* a corresponding number *b*1, *b*2, ..., *b**m*. On the second step we add to each number *a*2, *a*3, ..., *a**m* + 1 (changed on the previous step) a corresponding number *b*1, *b*2, ..., *b**m*. And so on: on step number *i* we add to each number *a**i*, *a**i* + 1, ..., *a**i* + *m* - 1 a corresponding number *b*1, *b*2, ..., *b**m*. The result of the encryption is the sequence *a*1, *a*2, ..., *a**n* after *n* - *m* + 1 steps.
     26 
     27 Help the Beaver to write a program that will encrypt messages in the described manner.
     28 
     29 Input
     30 
     31 The first input line contains three integers *n*, *m* and *c*, separated by single spaces.
     32 
     33 The second input line contains *n* integers *a**i* (0 ≤ *a**i* < *c*), separated by single spaces — the original message.
     34 
     35 The third input line contains *m* integers *b**i* (0 ≤ *b**i* < *c*), separated by single spaces — the encryption key.
     36 
     37 The input limitations for getting 30 points are:
     38 
     39 * 1 ≤ *m* ≤ *n* ≤ 103
     40 * 1 ≤ *c* ≤ 103
     41 
     42 The input limitations for getting 100 points are:
     43 
     44 * 1 ≤ *m* ≤ *n* ≤ 105
     45 * 1 ≤ *c* ≤ 103
     46 
     47 Output
     48 
     49 Print *n* space-separated integers — the result of encrypting the original message.
     50 
     51 Examples
     52 
     53 Input
     54 
     55 ```
     56 4 3 2  
     57 1 1 1 1  
     58 1 1 1
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0 1 1 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 3 1 5  
     71 1 2 3  
     72 4
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 0 1 2
     79 ```
     80 
     81 Note
     82 
     83 In the first sample the encryption is performed in two steps: after the first step *a* = (0, 0, 0, 1) (remember that the calculations are performed modulo 2), after the second step *a* = (0, 1, 1, 0), and that is the answer.