DP문제이다. index 5까지만 반복해서 보면 dp[i] = di[i-2] + dp[i-3]이 점화식이 되는 것을 쉽게 알 수 있다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
static StringBuilder sb;
static long[] dp;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(sb);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
int N = in.nextInt();
sb = new StringBuilder();
dp = new long[101];
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
Solve(in, N);
}
private static void Solve(InputReader in, int N) {
for(int i = 4; i < 101; i++)
dp[i] = dp[i-2] + dp[i-3];
for(int i = 0; i< N; i++)
sb.append(dp[in.nextInt()]).append("\n");
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
입력한 문자열을 n-2까지 보면서 현재 index 값이 E이면서 index+1값이 W이면 value값, i값을 증가
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
static int answer;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
int N = in.nextInt();
String s = in.nextLine();
answer = 0;
Solve(N, s);
}
private static void Solve(int N, String s) {
for (int i = 0; i < N - 1; i++) {
if (s.charAt(i) != 'E' || s.charAt(i+1) != 'W')
continue;
answer++;
i++;
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
public class Main {
static StringBuilder sb;
public static void main(String[] args) throws Exception {
SetData();
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int num = in.nextInt();
sb = new StringBuilder();
for (int i = 0; i < num; i++) {
Solve(in, out);
}
out.print(sb);
out.close();
}
private static void Solve(InputReader in, PrintWriter out) {
int country = in.nextInt();
int plane = in.nextInt();
for (int j = 0; j < plane; j++) {
in.nextInt();
in.nextInt();
}
sb.append(country - 1 + "\n");
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
1. 일단 입력 받은 배열을 오름차순 정렬을 통해 왼쪽부터 오른쪽으로 점점 수가 커지게 정렬시킨다.
2. 용액 배열 양쪽에서 다가오면서, 두 개의 합이 0에 가장 가까울 경우 저장해준다.
3. 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 왼쪽에서 다가오는 index를 하나 늘려준다.
4. 두 개의 합이 0보다 클 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 오른쪽에서 다가오는 index를 하나 줄여준다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Main {
static int[] array;
static int N, answer1, answer2;
public static void main(String[] args) throws Exception {
SetData();
TwoPointer();
System.out.println(answer1 + " " + answer2);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
array = new int[N];
answer1 = answer2 = 0;
for (int i = 0; i < N; ++i) {
array[i] = in.nextInt();
}
Arrays.sort(array);
}
private static void TwoPointer() {
int min = Integer.MAX_VALUE;
int left = 0, right = N - 1;
// 투 포인터
while (left < right) {
int sum = array[left] + array[right];
// v가 최소일 때 특성값 갱신
if (min > Math.abs(sum)) {
min = Math.abs(sum);
answer1 = array[left];
answer2 = array[right];
}
if (sum > 0)
right--;
else
left++;
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
bfs 방식을 통해 배열을 돌릴때 배열 값을 +1, check 해주면서 돌리면 될 것 같다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int[][] array;
static boolean[][] check;
static int N,M;
static int[] x = {-1,1,0,0};
static int[] y = {0,0,-1,1};
public static void main(String[] args) throws Exception {
SetData();
bfs();
System.out.println(array[N-1][M-1]);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
array = new int[N][M];
check = new boolean[N][M];
check[0][0] = true;
for (int i = 0; i < N; i++) {
String s = in.readString();
for (int j = 0; j < M; j++) {
array[i][j] = s.charAt(j) - '0';
}
}
}
public static void bfs(){
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {0,0});
while(!queue.isEmpty()){
int location[] = queue.poll();
for(int direction = 0; direction<4; direction++){
int r = location[0] + x[direction];
int c = location[1] + y[direction];
if(r >= 0 && c >= 0 && r < N && c < M){
if(array[r][c] != 0 && !check[r][c]){
queue.offer(new int[] {r,c});
check[r][c] = true;
array[r][c] = array[location[0]][location[1]] + 1;
}
}
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int N, M;
private static int[][] array;
private static int count;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
array = new int[M][N];
count = 0;
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < N; j++)
array[i][j] = Integer.parseInt(st.nextToken());
}
bfs();
System.out.println(count);
}
private static int[][] xy = {
{1, 0}, {0, 1},
{-1, 0}, {0, -1}
};
private static void bfs() {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {0,0});
while(!queue.isEmpty()){
int location[] = queue.poll();
// 마지막에 도달하면 count++
if(location[0] == M-1 && location[1] == N-1) {
count++;
continue;
}
for (int[] direction : xy) {
int r = location[0] + direction[0];
int c = location[1] + direction[1];
if(r >= 0 && c >= 0 && r < M && c < N) {
// 값이 작아질때만 queue에 추가
if(array[location[0]][location[1]] > array[r][c]) {
queue.add(new int[] {r,c});
}
}
}
}
}
}
실패 코드2 : queue를 이용하여 돌린 bfs를 재귀형식으로 바꿔줌. 시간 초과
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int N, M;
private static int[][] array;
private static int count;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
array = new int[M][N];
count = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
array[i][j] = Integer.parseInt(st.nextToken());
}
bfs(0, 0);
System.out.println(count);
}
// 메모리 초과때문에 메모리 줄이기 위함
private static int[][] xy = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
// 메모리 초과 때문에 bfs를 queue에서 재귀로 바꿈
private static void bfs(int a, int b) {
// base case
if (a == M - 1 && b == N - 1) {
count++;
return;
}
for (int[] direction : xy) {
int r = a + direction[0];
int c = b + direction[1];
if (r >= 0 && c >= 0 && r < M && c < N) {
// 값이 작아질때만 queue에 추가
if (array[a][b] > array[r][c]) {
bfs(r, c);
}
}
}
}
}
성공 코드 : dp배열을 하나 더 만들어서 이미 지나온 길을 가려고 할 시 끝까지 가지않고 전에 저장해 놓은 값을 return 해준다.
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
private static int N, M;
private static int[][] array, dp;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(bfs(0,0));
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
M = in.nextInt();
N = in.nextInt();
array = new int[M][N];
dp = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
array[i][j] = in.nextInt();
dp[i][j] = -1;
}
}
}
// 메모리 초과때문에 메모리 줄이기 위함
private static int[][] xy = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
// 메모리 초과 때문에 bfs를 queue에서 재귀로 바꿈
private static int bfs(int a, int b) {
// base case
if (a == M - 1 && b == N - 1) return 1;
// 이미 지나온 길이면 return으로 해당 index의 값을 리턴해준다. 이렇게 함으로써 왔던길을 가지않아도 됌.
if(dp[a][b] != -1) return dp[a][b];
dp[a][b] = 0;
for (int[] direction : xy) {
int r = a + direction[0];
int c = b + direction[1];
if (r >= 0 && c >= 0 && r < M && c < N) {
// 작아질 때만 재귀로 들어감
if (array[a][b] > array[r][c]) {
// 재귀를 돌면서 해당 index 방향에서 끝까지 도달한 횟수를 누적해서 index에 더 해줌
dp[a][b] += bfs(r, c);
}
}
}
return dp[a][b];
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
BFS를 돌리는데 입력받을 때, 1입력받으면 queue에 넣어놓는다. BFS를 돌면서 0을 1로 바꿀 수 있는 곳은 다 바꾼다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N, M, max;
static int[][] array;
static int[] x = { -1, 1, 0, 0 };
static int[] y = { 0, 0, -1, 1 };
static Queue<int[]> queue;
public static void main(String[] args) throws Exception {
SetData();
bfs();
if (!check()) {
System.out.println(-1);
} else if(max==0){
System.out.println(max);
}else{
System.out.println(max-1);
}
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.readInt();
M = in.readInt();
array = new int[M][N];
max = 0;
queue = new LinkedList<>();
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
int M = in.readInt();
array[i][j] = M;
if (M == 1) {
queue.offer(new int[]{i, j});
}
}
}
}
static public void bfs() {
while (!queue.isEmpty()) {
int[] location = queue.poll();
for (int direction = 0; direction < 4; direction++) {
int r = location[0] + x[direction];
int c = location[1] + y[direction];
if (0 > r || r >= M || 0 > c || c >= N) continue;
if (array[r][c] == 0) {
array[r][c] = array[location[0]][location[1]] + 1;
queue.offer(new int[]{r, c});
if (array[r][c] > max) {
max = array[r][c];
}
}
}
}
}
static public boolean check() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (array[i][j] == 0) {
return false;
}
}
}
return true;
}
private static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
1. 한 방향으로 최대 14번 움직일 수 있기 때문에 (15, 15)에서 시작하고 판은 적어도 29*29여야 한다.
2. 한번 움직일 때마다 4방향 다 움직이면서 브루트 포스 알고리즘을 적용하여 답을 탐색한다.
3. N번 움직였을 경우 누적 확률을 더해주면 됩니다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
static int N;
static double percentage;
static double[] percent; // 각 방향으로 이동할 확률
static boolean[][] check; // 단순 경로인지 아닌지 체크
static int[] x = { -1, 1, 0, 0 };
static int[] y = { 0, 0, -1, 1 };
public static void main(String[] args) throws Exception {
SetData();
dfs(14, 14, 0, 1.0);
System.out.println(percentage);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
percent = new double[4];
check = new boolean[30][30];
percentage = 0.0;
check[14][14] = true;
N = in.readInt();
// 입력값을 확률로 바꿈
for (int i = 0; i < 4; i++)
percent[i] = in.readInt() * 0.01;
}
private static void dfs(int a, int b, int count, double per) {
// basecase
if (count == N) {
percentage += per;
return;
}
// 4방향 이동
for (int i = 0; i < 4; i++) {
int r = a + x[i];
int c = b + y[i];
if (!check[r][c]) {
check[r][c] = true;
dfs(r, c, count + 1, per * percent[i]);
check[r][c] = false;
}
}
}
private static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
