fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #define MOD (100000)
  5.  
  6. int main(void)
  7. {
  8.     static int route[3][3000001];
  9.     int K, P;
  10.     int type, len;
  11.     int i;
  12.  
  13.     scanf("%d%d", &K, &P);
  14.  
  15.     memset(route, -1, sizeof(route));
  16.     route[0][0] = route[1][0] = 0; route[2][0] = 1;
  17.  
  18.     for (i = 0; i < P; i++){
  19.         scanf("%d%d", &type, &len);
  20.         route[--type][len] = route[2][len] = 0;
  21.     }
  22.  
  23.     for (i = 1; i <= K; i++){
  24.         route[0][i] = route[0][i] ? (route[1][i - 1] + route[2][i - 1]) % MOD : 0;
  25.         route[1][i] = route[1][i] ? (route[0][i - 1] + route[2][i - 1]) % MOD : 0;
  26.         route[2][i] = route[2][i] ? (route[0][i - 1] + route[1][i - 1] + route[2][i - 1]) % MOD : 0;
  27.     }
  28.  
  29.     printf("%d\n", route[2][K]);
  30.  
  31.     return (0);
  32. }
  33.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aTOWC
language:
C (gcc 8.3)
created:
11 years 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!