SPOJ.com - Problem RGB7603

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RGB7603 - Супер жаал саад тойрон

Супер жаал 3 янзаар урагшилж чаддаг. Дараагийн гишгүүрт очихоос гадна 1 болон 2 гишгүүр алгасаж чадна. Замд нь нийтдээ k ширхэг цөмөрсөн шат байгаа бол хичнээн ялгаатай маршрутаар n-р гишгүүрт хүрэх вэ. Цөмөрсөн шатны дугаар өсөх эрэмбээр өгөгдөнө.

Жич : Надад ганган бодолт байгаа. Илүү ганган бодсон нь gipsymn@yahoo.com хаягаар бодолтоо илгээнэ үү.

Input

Эхний мөрөн шатны гишгүүрийн тоо. 3<n<100.

Хоёр дахь мөрөнд цөмөрсөн гишгүүрийн тоо. k<n.

Гурав дахь мөрөнд цөмөрсөн гишгүүрийн дугаарууд зайгаар тусгаарлагдан өгөгдөнө.

Output

Маршрутын тоо.

Example

Input:
10
3
4 7 8
Output:
10

Submit solution!

Нэмсэн:	Bataa
Огноо:	2013-01-24
Хугацааны хязгаарлалт:	1s
Эх кодын хэмжээний хязгаарлалт:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Програмчлалын хэлүүд:	ADA95 ASM32 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE

hide comments

2021-01-19 19:32:29
bi ene bodlogiig recursion ashiglaad bodloo .jaahan optimization ashiglasn shuu xD

#include <iostream>
#include <vector>

using namespace std;

vector<long long int> memo(10000, -1);

long long int find_step(long long n, vector<long long> steps){
if (n == 0) return 1;
if (steps[n] != -1){
if(memo[n] != -1) return memo[n];
if(n == 1) return 1;
if(n == 2) return find_step(0, steps) + find_step(1, steps);

long long int ans =
find_step(n - 1, steps) + find_step(n - 2, steps) + find_step(n - 3, steps);
memo[n] = ans;
return ans;
}
return 0;
}

int main(){
long long n, m;
cin >> n >> m;

vector<long long> steps(n + 1);
for(int i = 1; i <= m; i++){
long long tmp;
cin >> tmp;
steps[tmp] = -1;
}

long long int ans = find_step(n, steps);
cout << ans;

return 0;
}

2020-12-28 08:43:11
#include <cstdio>
#include <iostream>
using namespace std;
main(){
long long n,i,s,k,a[101],p[101];
cin>>n>>s;
for(i = 1 ; i <= s ; i++){
cin>>k;
p[k] = -1;}
p[0] = 1;
if(p[1]!=-1) p[1]=1;
else p[1]=0;
if(p[2]!=-1) p[2]=p[1]+p[0];
else p[2]=0;
for(int i = 3 ; i <= n ; i++){
if(p[i]!=-1){
p[i]=p[i-1]+p[i-2]+p[i-3];
}else{
p[i]=0;
}
}
cout<<p[n];
} //ez suguudaa

2020-11-07 02:51:26
90150454 zalga

2020-11-07 02:44:46
#include <cstdio>
int main(){
printf("huulhaa bolitsgoo");
long long a[101];
long long dp[101] = {0};
long long n , i ,s,k;
scanf("%lld%lld" , &n , &s);
for(i = 1 ; i <= s ; i++){
scanf("%lld" , &k);
dp[k] = -1;}
dp[0] = 1;
if(dp[1]!=-1) dp[1]=1;
else dp[1]=0;
if(dp[2]!=-1) dp[2]=dp[1]+dp[0];
else dp[2]=0;
for(int i = 3 ; i <= n ; i++){
if(dp[i]!=-1){
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}else{
dp[i]=0;
}
}
printf("%lld" , dp[n]);
}

2020-11-07 02:42:26
#include <cstdio>
int main(){
long long a[101];
long long dp[101] = {0};
long long n , i ,s,k;
scanf("%lld%lld" , &n , &s);
for(i = 1 ; i <= s ; i++){
scanf("%lld" , &k);
dp[k] = -1;}
dp[0] = 1;
if(dp[1]!=-1) dp[1]=1;
else dp[1]=0;
if(dp[2]!=-1) dp[2]=dp[1]+dp[0];
else dp[2]=0;
for(int i = 3 ; i <= n ; i++){
if(dp[i]!=-1){
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}else{
dp[i]=0;
}
}
printf("%lld" , dp[n]); ewakoda ich
}

2020-11-07 02:41:50
#include <cstdio>
int main(){
long long a[101];
long long dp[101] = {0};
long long n , i ,s,k;
scanf("%lld%lld" , &n , &s);
for(i = 1 ; i <= s ; i++){
scanf("%lld" , &k);
dp[k] = -1;}
dp[0] = 1;
if(dp[1]!=-1) dp[1]=1;
else dp[1]=0;
if(dp[2]!=-1) dp[2]=dp[1]+dp[0];
else dp[2]=0;
for(int i = 3 ; i <= n ; i++){
if(dp[i]!=-1){
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}else{
dp[i]=0;
}
}
printf("%lld" , dp[n]);
}

2020-10-21 11:45:33

2020-07-02 06:22:03
#include<bits/stdc++.h>
main(){
long long n,a[100]={0},k,x;
scanf ("%lld%lld",&n,&k);
for(int i=4; i<=k; i++){
scanf("%lld",&x);
a[x=1];
}
if(a[1]==1)a[1]=0;
else a[1]=1;
if(a[2]==1)a[2]=0;
else a[2]=a[1]+1;
if(a[3]==1)a[3]=0;
else a[3]=a[2]+a[1]+1;
for(int i=4; i<=n; i++){
if(a[i]==1)a[i]=0;
else a[i]=a[i-3]+a[i-2]+a[i-1];
}

printf("%d",a[n]);
}
hudal

2020-07-01 03:53:18

2020-07-01 03:47:23
sain uu

АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

RGB7603 - Супер жаал саад тойрон

Input

Output

Example