Bài A - Codeforces Global Round 1

Bài A:

Đề bài: Bạn được cho một số nguyên n (n>=0) được biểu diễn với k chữ số ở cơ số b. Vì vậy,

$n=a_1.b^{k-1}+a_2.b^{k-2}+...+a_{k-1}.b+a_k$.

Ví dụ, nếu b=17,k=3 và a=[11,15,7] thì $n=11.17^2+15.17+7=3179+255+7=3441$.

Xác định liệu rằng n chẵn hay lẻ.

Đầu vào:

+ Dòng đầu tiên chứa hai số nguyên b và k (2<=b<=100,1<=k<=10^5) - là cơ số và số các chữ số.

+ Dòng thứ hai chứa k số nguyên a(1),a(2),...,a(k)(0<=a(i)<b)- số các chữ số của n.

Đầu ra:

+ In ra "even" nếu n chẵn, ngược lại in ra "odd"

Ví dụ:

Đầu vào:

13 3

3 2 7

Đầu ra:

even

/**/

Đầu vào:

10 9

1 2 3 4 5 6 7 8 9

Đầu ra:

odd

/**/

Đầu vào:

99 5

32 92 85 74 4

Đầu ra:

odd

Đầu vào:

2 2

1 0

Đầu ra:

even.

Chú thích:

Ở ví dụ đầu tiên, $n=3.13^2+2.13+7=540$, nó là số chẵn

Ở ví dụ thứ hai, $n=123456789$ là số lẻ.

Ở ví dụ thứ ba, $n=32.99^4+92.99^3+85.99^2+74.99+4=3164015155$ là số lẻ.

Ở ví dụ thứ tư, $n=2$ là số chẵn.

Hướng dẫn: 

Nếu b là số chẵn, vấn đề chỉ là chữ số cuối cùng.

Ngược lại, $b^k$ là số lẻ với mọi $k$, vì vậy mỗi chữ số là bội của một số lẻ. Do đó n chẵn khi và chỉ khi tổng các hệ số chẵn. Do đó chúng ta chỉ cần đếm số các số chẵn.

Lời giải:

/**
 *    author:  tourist
 *    created: 07.02.2019 16:34:54       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int b, k;
  cin >> b >> k;
  vector<int> a(k);
  for (int i = 0; i < k; i++) {
    cin >> a[i];
  }
  int p = 1, s = 0;
  for (int i = k - 1; i >= 0; i--) {
    s = (s + p * a[i]) % 2;
    p = p * b % 2;
  }
  cout << (s ? "odd" : "even") << '\n';
  return 0;
}