fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     static long[][][] dp = new long[200005][3][3]; // Adjusted size for clarity
  5.  
  6.     public static void main(String[] args) {
  7.         Scanner scanner = new Scanner(System.in);
  8.  
  9.         long n = scanner.nextLong();
  10.         long v = scanner.nextLong();
  11.  
  12.         long[] a = new long[(int) n + 1];
  13.         long[] b = new long[(int) n + 1];
  14.  
  15.         for (int i = 1; i <= n; i++) {
  16.             a[i] = scanner.nextLong();
  17.             b[i] = scanner.nextLong();
  18.         }
  19.  
  20.         // Initialize dp for the first index
  21.         if (a[1] % 2 == 0) {
  22.             dp[1][1][1] = 1; // Even journeys ending at a[1]
  23.         } else {
  24.             dp[1][1][2] = 1; // Odd journeys ending at a[1]
  25.         }
  26.  
  27.         if (b[1] % 2 == 0) {
  28.             dp[1][2][1] = 1; // Even journeys ending at b[1]
  29.         } else {
  30.             dp[1][2][2] = 1; // Odd journeys ending at b[1]
  31.         }
  32.  
  33.         // Fill the dp table
  34.         for (int j = 2; j <= n; j++) {
  35.             // For array a
  36.             if (a[j] % 2 == 0) {
  37.                 dp[j][1][1] = dp[j - 1][1][1] + dp[j - 1][2][1]; // Even from a
  38.                 dp[j][1][2] = dp[j - 1][1][2] + dp[j - 1][2][2]; // Odd from a
  39.             } else {
  40.                 dp[j][1][1] = dp[j - 1][1][2] + dp[j - 1][2][2]; // Even from odd
  41.                 dp[j][1][2] = dp[j - 1][1][1] + dp[j - 1][2][1]; // Odd from even
  42.             }
  43.  
  44.             // For array b
  45.             if (b[j] % 2 == 0) {
  46.                 dp[j][2][1] = dp[j - 1][1][1] + dp[j - 1][2][1]; // Even from b
  47.                 dp[j][2][2] = dp[j - 1][1][2] + dp[j - 1][2][2]; // Odd from b
  48.             } else {
  49.                 dp[j][2][1] = dp[j - 1][1][2] + dp[j - 1][2][2]; // Even from odd
  50.                 dp[j][2][2] = dp[j - 1][1][1] + dp[j - 1][2][1]; // Odd from even
  51.             }
  52.         }
  53.  
  54.         // Output the total number of journeys
  55.         long totalOddJourneys = dp[(int) n][1][2] + dp[(int) n][2][2];
  56.         long totalEvenJourneys = dp[(int) n][1][1] + dp[(int) n][2][1];
  57.  
  58.         System.out.println("ODD Journeys: " + totalOddJourneys);
  59.         System.out.println("EVEN Journeys: " + totalEvenJourneys);
  60.  
  61.         scanner.close();
  62.     }
  63. }
  64.  
Success #stdin #stdout 0.22s 86344KB
comments (?)
stdin
copy 
3 0
1 3
2 1
1 1
stdout
copy 
ODD Journeys: 4
EVEN Journeys: 4
https://ideone.com/rd8Y9D
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!