abc 079 ワーシャルフロイド ダイクストラ

B
今、日本は 11 月 18 日ですが、11 と 18 は隣り合うリュカ数です。
整数 N が与えられるので、N 番目のリュカ数を求めてください。
ただし、リュカ数は i 番目のリュカ数を Li とすると、
L0=2
L1=1
Li=Li−1+Li−2(i≧2)
と定義される数とします。

```
#include<iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	long long L[90];
	L[0] = 2;
	L[1] = 1;
	for (int i = 2; i <= N; ++i) {
		L[i] = L[i - 1] + L[i - 2];
	}
	cout << L[N];
	return 0;
}
```

C
駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。
切符には 4 つの 0 以上 9 以下の整数 A,B,C,D が整理番号としてこの順に書かれています。
A op1 B op2 C op3 D = 7 となるように、op1,op2,op3 に + か - を入れて式を作って下さい。
なお、答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。
制約
0≦A,B,C,D≦9
入力は整数からなる
答えが存在しない入力は与えられない

```
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
int main() {
	int X;
	cin >> X;
	int D = X % 10;
	X /= 10;
	int C = X % 10;
	X /= 10;
	int B = X % 10;
	X /= 10;
	int A = X % 10;
	int Bi, Cj, Dk;;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				int sum = A;
				if (i == 0) {
					sum += B;
				}
				else {
					sum -= B;
				}
				if (j == 0) {
					sum += C;
				}
				else {
					sum -= C;
				}
				if (k == 0) {
					sum += D;
				}
				else {
					sum -= D;
				}
				if (sum == 7) {
					Bi = i;
					Cj = j;
					Dk = k;
				}
			}
		}
	}
	char y1, y2, y3;
	if (Bi == 0) {
		y1 = '+';
	}
	else {
		y1 = '-';
	}
	if (Cj == 0) {
		y2 = '+';
	}
	else {
		y2 = '-';
	}
	if (Dk == 0) {
		y3 = '+';
	}
	else {
		y3 = '-';
	}
	cout << A << y1 << B << y2 << C << y3 << D << "=7" << endl;
	return 0;
}
```
bitを使うと、

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
	int A[4], i;
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); ++i) {
		A[i] = s[i] - '0';
	}
	int j, sum;
	char op[3];
	for (int i = 0; i < 8; ++i) {
		sum = A[0];
		for (int j = 0; j < 3; ++j) {
			if (i & (1 << j)) {
				op[j] = '+';
				sum += A[j + 1];
			}
			else {
				op[j] = '-';
				sum -= A[j + 1];
			}
		}
		if (sum == 7)
			break;
	}
	for (int i = 0; i < 3; ++i) {
		cout << A[i] << op[i];
	}
	cout << A[3] << '=' << 7;
}
```
D
ワーシャルフロイドとダイクストラ

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
///////////////////////////////////////

//あらかじめ数xを数yに変換するための最小コストを計算しておく
int main() {
	int H, W;
	int C[10][10], A[202][202];
	cin >> H >> W;
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			cin >> C[i][j];
		}
	}
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			for (int k = 0; k < 10; ++k) {
				C[j][k]= min(C[j][k], C[j][i] + C[i][k]);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (0 <= A[i][j]) {
				ans += C[A[i][j]][1];
			}
		}
	}
	cout << ans << endl;
	return 0;
}
```