# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3772 |

3 | tourist | 3706 |

4 | maroonrk | 3609 |

5 | Um_nik | 3591 |

6 | fantasy | 3526 |

7 | ko_osaga | 3500 |

8 | inaFSTream | 3477 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 183 |

2 | awoo | 181 |

3 | nor | 172 |

4 | -is-this-fft- | 170 |

4 | adamant | 170 |

6 | maroonrk | 165 |

7 | antontrygubO_o | 160 |

8 | SecondThread | 159 |

9 | dario2994 | 152 |

9 | kostka | 152 |

Hi,

I found this solution to tri-tiling problem, but I am not able to prove it.

```
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ways(int tile)
{
if (tile < 0) return 0;
if (tile == 0) return 1;
if (tile == 2) return 3;
return ways(tile - 2) * 4 - ways(tile - 4);
}
signed main()
{
int n;
while(true){
cin >> n;
if(n == -1) break;
if(n == 1){
cout << 0 << '\n';
continue;
}
cout << ways(n) << '\n';
}
return 0;
}
```

Can anyone please help me out.

**Note** : Graph doesn't contain multiple edges or self loops and it may be disconnected.

**Constraints :**

1 <= N, K, Q <= 1e5

1 <= M <= 2e6

**Sample Input:**

5 3 3 // N M K

1 2 // edge 1

2 3 // edge 2

1 3 // edge 3

1 3 5 // special vertices

5 // Q

1 // V for 1st query

2 // " " " 2nd " "

3 // " " " 3rd " "

4 // " " " 4th " "

5 // " " " 5th " "

**Sample Output:**

0

1

0

-1

0

**P.S. :** This problem was asked in Codechef's CCDSAP advanced contest on 22th Sept.,2019. Now it's over.

**Constraints:** 1<=n<=1000000, 0<=ai<=10000.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/23/2023 07:34:33 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|