Блог пользователя codepasta

Автор codepasta, 4 года назад, По-английски

hello, codeforce!!!1!

i have a hard question for you, can you please helpp me????

question is: how to find if a number called n is even or odd???? my code is:

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

if (n == 1) cout << "ODD";

if (n == 2) cout << "EVEN";

if (n == 3) cout << "ODD";

if (n == 4) cout << "EVEN";

if (n == 5) cout << "ODD";
if (n == 6) cout << "EVEN";
if (n == 7) cout << "ODD";
if (n == 8) cout << "EVEN";
if (n == 9) cout << "ODD";
if (n == 10) cout << "EVEN";
if (n == 11) cout << "ODD";
if (n == 12) cout << "EVEN";
if (n == 13) cout << "ODD";
if (n == 14) cout << "EVEN";
if (n == 15) cout << "ODD";
}

it works for example, but gives wrong answer for n = 100000, what is wrong???? please helppp

  • Проголосовать: нравится
  • -40
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Here is a dp approach, dp[i] denotes if the ith number is odd or even. Now, the recurrence relaion is dp[i]=dp[i-2]

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    I have a better idea : You can say dp[i] = 1 − dp[i − 1]

    :)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      another approach would be like this :

      we know that if x is odd then x + 2 is odd as well

      also if x is even x + 2 is even as well

      using that property we can initially start with every number in one component with size one and then merge x and x + 2 using a data structure like DSU.

      in the end we will end up with two components first one will contain all the odd numbers and the other one will contain all the even numbers.