Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip
問題
解法
dp[pos] = [左端がposの時の最大値]とするdpで解いた。
あらかじめ各Aの要素に対して、出現する左端と右端のindexを記録をしておく。
posの値が保存されている要素の左端なら右端の区間まで覆うことができる。
但し同一要素は同一区間に必ず含めるという制約があるため、区間を覆う時に以下の点で注意が必要である。
区間のある要素の左端のindexが覆う区間の左端より小さいなら、同一要素は同一区間に必ず含めるという条件に矛盾
例) 1,[2,3,1,2] は条件に矛盾 何故なら1が同じ区間に含まれなくなってしまうため同一要素は同一区間に必ず含めるため、出現した要素の右端のindexまで覆う区間を伸ばす必要がある
例) [2,1,3,2],1なら、[2,1,3,2,1]まで遷移をする時に右端を伸ばす
提出コード
Submission #27384664 - Codeforces
コード
#include <algorithm> #include <bitset> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <memory> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> // c++11 #include <array> #include <tuple> #include <unordered_map> #include <unordered_set> #define mp make_pair #define mt make_tuple #define rep(i, n) for (int i = 0; i < (n); i++) using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; const int INF = 1 << 29; const double EPS = 1e-9; const ll MOD = 1000000007; const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}; const int MAX_N = 6010; int N; int dp[MAX_N]; bool check[MAX_N]; vector<int> A; int right_idx[MAX_N]; int left_idx[MAX_N]; int memo(int pos) { if (pos >= N) { return 0; } int &res = dp[pos]; if (res >= 0) { return res; } res = 0; res = max(res, memo(pos + 1)); int val = A[pos]; int left = left_idx[val]; int right = right_idx[val]; // match if (pos == left) { int xor_val = 0; memset(check, false, sizeof(check)); bool ok = true; for (int i = pos; i <= right; i++) { if (val != A[i]) { int tmp_left = left_idx[A[i]]; int tmp_right = right_idx[A[i]]; if (tmp_left < pos) { ok = false; break; } right = max(right, tmp_right); } if (not check[A[i]]) { xor_val ^= A[i]; check[A[i]] = true; } } if (ok) { res = max(res, memo(right + 1) + xor_val); } } return res; } int main() { cin >> N; A.resize(N); for (auto &val : A) { cin >> val; } for (int i = 0; i < MAX_N; i++) { left_idx[i] = INF; right_idx[i] = -INF; } for (int i = 0; i < N; i++) { left_idx[A[i]] = min(left_idx[A[i]], i); right_idx[A[i]] = max(right_idx[A[i]], i); } memset(dp, -1, sizeof(dp)); cout << memo(0) << endl; return 0; }
CODEFESTIVAL 2015参加記
参加記
去年の本戦は予選落ち去年のThanksの参加記togatogah.hatenablog.com
予選
・予選A 3完(落ちる)・予選B 3完 + 部分点(通る)
1日目
・興奮して目が覚める。・研究室で身支度を整えて、会場までの経路を調べる。
・品川のバスを予約していたことに気づきメールを送る(すいませんでした)
・会場に到着したが30分前のため会場に入れず、コンビニで時間を潰そうと思ったら研究室の先輩と出くわす。(今年僕がこどふぇすの事を伝えて誘ってあっさりと本戦出場を決めた強い人)
・会場入りしてさっそくスタッフの人と軽くおしゃべり、受付してた人も某ツアーの時にスマブラ一緒にやった人だった。
・134番のふだを渡されて、Tシャツなど受け取り席につく。
・本戦開始までに、時間があり適当にぶらつきながらお菓子をつまむ。
コンテスト
・5問以上がパーカーと発表され、去年の難易度ならワンちゃん・ネットワークトラブルで開始時間が45分伸びる。
・遅延までは天空のmacを眺めたり、twitterの眺めて時間を潰す。
以下本戦
All submissions - CODE FESTIVAL 2015 決勝 | AtCoder
・A invalidとvalidをミスり1WA(ペナルティなし最高)→AC
・B 色々悩んでdpを考えたがB問題からdpはないだろうと思ってサンプルから察して3.5 * Nのfloorで投げてみる。AC(ペナルティなし最高)
・C greedyに寿司を載せられるなら載せて駄目なら分解してのせる→AC
・D sortして累積和かなあと思ったが全然思い浮かばず、そういえばsegtreeで区間和でRMQあったようなと思いぐぐる→あった→コピペして少し直す→AC
・E --は消えるよなあとぼんやり思い、取り敢えず-1,0,1のサンプルを作り手で色々とシミュレーションをする。途中!*!*!なら!にできることがわかり、一つでも変更できたならば、また全て試すという適当な実装でだす→AC
・ここでパーカーゲットして興奮する。
・順位表を確認したところ70番ぐらいで、上位陣はGを解いてる人が多かったためGを読む→DPっぽいなあ→わからず
・Fを読む。→無理だ
・Hを読む。→3つ以上は重なるとアウトだよなあとぼんやり思う→無理
・Gに戻って適当にdpっぽいのを書く→終了
ooooo----- 500 87位 / 200位で終了
・G問題を区間を持つDPで解けることが判明
・解説まで去年のThanks勢で一緒だった人と話して取り敢えず、お互いにパーカーが取れたことを喜ぶ。
・解説を聞く→F問題無理ゲーだった→G問題やはりよくわかんねー
取り敢えず、最低限自分が解けなければいけなかった問題を解けたのでそこそこ満足でしたが、やはりあと1問解きたかった。
コンテンツ
・ICFPCのお話、ガチガチのCSの知識がないととてもじゃないけど太刀打ちできず年によってはもし参加しても全く歯がたたなそう・秋葉さんのペアプロ オイラーツアーの性質を学んだだけでも良かった。
・LayCurseさんの作問の話、良問について語った時にchokudaiさんがひたすらうなずいてた。作問は興味はあるけど時間が取られそうだし、まず問題が思い浮かばない。
・フードタイムで適当に食事を済ませてエキシビションマッチまで時間を潰す。
・本戦塾で、G問題の解説を聞くなるほどなあと関心、必ずしも解けない問題じゃなかったなあと思う。
エキシビション
・yosupoさんのエンターテイメント性が素晴らしかった。・Misawaさんのvimがカスタマイズされていて、すごかった(小並感)
ホテル
・hadroriさんがご飯のツイートをふぁぼってご飯についていく(blue_jamさんponyoさんとhadroriさんと僕)・ラーメン美味しかった。
・hadroriさんと僕がホテルのカードキーを忘れて一緒にフロントで手続きをする。
・風呂に入って寝る
2日目
・目覚ましをかけたがその前に目が覚める・バスに乗り本選会場へ
あさプロ
・あさプロmiddleで参戦・A K - 1個とってくるみたいなことをしたがN=1の時にはまってた、最後の1個は二分探索で求めて提出→AC
・B いろいろと悩み、適当に分割してLCS求めればいいじゃん→LCSコピペ→提出→AC
・C 小さい方でマージしてけばよくね→dequeで実装→バグらせる→何とかAC
・D 残り10分のため適当にお菓子を食べて時間を潰す
ooo- 400 58位 / 119位
まあ、まさしく本戦の順位通りだなあと思う。
コンテンツ
・タンブラー欲しさに音ゲーをやる久しぶりに太鼓の達人をやったが難しすぎ・・・・ライトニングトークで坂本さんのゲームAIの話を聞く、やはりゲームのルールは複雑すぎると大変だよなあ、あとビジュアライザーがしっかりしてると面白そうだなあと思う。
チーム対抗リレー
・RGB_colorで参加・F問題を担当 N個の頂点かつN本の連結無向グラフの数がいくつかを数え上げる問題→適当にグラフ列挙してもいいけど手で数え上げられるよなあと思い手で数え上げる方針にする。→他の人と協力して数え上げた→CATで提出(WA)→数え間違い→WA→WA→
WA→WA→WA→WA・・・・・→数え間違いが発覚→これで絶対あってるだろ→WA→C++で提出→AC(17WA)
CATの提出で改行してなくてくっそハマってた本当にこれはチームメイトに申し訳なかった。
・そして30秒後にG問題AC全完
・あとは他のチームを眺めながら、みんなでどう解いたか簡単に話しながら待つ
初めてのチーム戦だったが最高に楽しかった。ACした時の興奮は個人戦で味わえないような喜びだった。あとズバズバと問題を解いていく、チームメイトが凄かった。
ハッピーアワー
・みんなで適当におしゃべりしながらコードを見て、どう解いたか掘り下げていった。・各賞の発表でモニョ先輩が書道で受賞する。ヤバイ漢字が一瞬頭をよぎったが普通の漢字を書いてほっとする?
閉会式
・ドローンで記念撮影して終了・帰宅
今年最後のチャンスなので参加できて良かったです。
最高のコンテストでした。スタッフの方々ありがとうございました。
SRM 648 div2
SRM648 div2の参加記
結果
ooo 4th 1072-> 1237最近はいい感じにレートが上がっていたが、まさかdiv1に上がれるとは思わなかった。
CodeFestivalの予選に落ちたり、SRMの過去最低レートをとったりしてプロコンのモチベーションがだだ下がりだったが、CodeThanksから徐々にモチベーションを取り戻して、真面目に問題を解くようになってようやくdiv1に上がれて正直ほっとしてます。
SRMを始めた頃にはすぐに大学院に入る頃までにはdiv1に上がるだろうと軽く考えてたが結局一年ぐらいかかってしまった。
Easy KitayutaMart2
問題
kitayutaはT円持っていて、それぞれの商品は購入するごとにK*2^i円となる。kitayutaが購入した商品の数は?
解法
実際にシミュレーションコード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; class KitayutaMart2 { public: int numBought(int K, int T) { int result; ll sum = K; if (sum > T)return 0; ll tmp = K; for (int i = 2; ; i++){ tmp *= 2; sum += tmp; if (sum > T){ return i - 1; } } return result; } };
焦りすぎて問題分を勘違いして再提出をしてしまった。
Medium Fragile2
問題
グラフの隣接行列が与えられるので、ある2つの頂点を消すことによって連結成分が増加するペアの数を求めよ。解法
最初に深さ優先探索を行い、連結成分の個数を求め。実際に、全部の消去するペアに対して再び深さ優先探索を行い連結成分の個数を求め増加したならば+1
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; class Fragile2 { public: int V; vector<vector<int> > g; bool visit[30]; void dfs(int pos, int a, int b){ visit[pos] = true; for (int i = 0; i < g[pos].size(); i++){ if (!visit[g[pos][i]] && g[pos][i] != a && g[pos][i] != b){ dfs(g[pos][i], a, b); } } return ; } void dfs1(int pos){ visit[pos] = true; for (int i = 0; i < g[pos].size(); i++){ if (!visit[g[pos][i]]){ dfs1(g[pos][i]); } } return ; } int countPairs(vector<string> graph) { int result; result = 0; V = graph.size(); g.resize(V); for (int i = 0; i < 30; i++){ visit[i] = false; } for (int i = 0; i < graph.size(); i++){ for (int j = i + 1; j < graph.size(); j++){ if (graph[i][j] == 'Y'){ g[i].push_back(j); g[j].push_back(i); } } } int ini = 0; for (int i = 0; i < graph.size(); i++){ if (!visit[i]){ dfs1(i); ini++; } } for (int i = 0; i < graph.size(); i++){ for (int j = i + 1; j < graph.size(); j++){ int res = 0; for (int k = 0; k < 30; k++){ visit[k] = false; } for (int k = 0; k < graph.size(); k++){ if (k != i && k != j && !visit[k]){ dfs(k, i, j); res++; } if (res > ini){ result++; } } } return result; } };
単純だけどちょっと実装が面倒くさい
Hard ABC
問題
以下の条件を満たす文字列を一つ返せ・A,B,Cの3つから構成されるN文字
・S[i] < S[j](0 <= i < j <= N - 1)のペアがちょうどK個
解法
bool dp[今なん文字目か][Aの個数][Bの個数][ペアの個数]を探索済みかどうかのメモ化再帰で解いた。例えば
Aを追加したならばペアの個数は増加せず
Bを追加したならばペアの個数は(現在のペアの個数) + (Aの個数)
Cを追加したならばペアの個数は(現在のペアの個数) + (Aの個数) + (Bの個数)
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; class ABC { public: bool dp[33][33][33][500]; int KK; int NN; string ans; bool ok; void memo(int pos, int a, int b, int cnt, string str){ if (ok)return ; if (pos > NN)return ; if (cnt > KK)return ; if (dp[pos][a][b][cnt] == true){ return ; } if (pos == NN && cnt == KK){ ok = true; ans = str; return; } for (int i = 0; i < 3; i++){ int sum = cnt; if (i == 0){ if (sum > KK)continue; memo(pos + 1, a + 1, b, sum, str + 'A'); } else if (i == 1){ sum += a; if (sum > KK)continue; memo(pos + 1, a, b + 1, sum, str + 'B'); } else { sum += a + b; if (sum > KK)continue; memo(pos + 1, a, b, sum , str + 'C'); } } dp[pos][a][b][cnt] = true; } string createString(int N, int K) { string result; rep(i, 33){ rep(j, 33){ rep(k, 33){ rep(l, 500){ dp[i][j][k][l] = false; } } } } result = ""; ans = ""; NN = N; KK = K; memo(0, 0, 0, 0, ""); result = ans; return result; } };
こういうDPは結構典型な気がするので、落とさず取って行きたい。
個人的には
G: 通勤電車と気分 - code thanks festival 2014 A日程(オープンコンテスト) | AtCoder
を解いてからDPの考え方がちょっとつかめた気がします。
CodeThanksFestival A日程参加記
予選落ちたので参加してきました。
参加までの流れ
festival予選A
部分点を狙わず解いたら三完
festival予選B
C問題が解けずに撃沈二完部分点
SRMで過去最低レートを取ったりして荒れる。
リクルートからCodeThanksFestivalのメールが来る
リクルートからCODE THANKS FESTIVALのメールが来た時の僕の気持ち pic.twitter.com/83gjapdLa9
— togatoga_感謝 (@kado_m) 2014, 11月 14
以下本戦
場所はCodeFormula以来のテレコムセンター
風邪気味で、近くのコンビニでティシュを買おうと思ったがどこのコンビニも閉まってた。
Tシャツと弁当を貰って待機
叙々苑の焼肉弁当最高!!
5問正解でトートバッグで上位十名が焼き肉会が発表される。
5問正解できればいいやと思う。
FA賞とかあったけど、狙わずにひたすら前から解く方針にする。
問題A カメツル算
やるだけ
12:00:45 AC
問題B バッジ
大きい方から加算するだけのはずが、2WA(ペナルティ無し最高)
12:04:10 AC
問題C コンテスト
足すだけ
12:09:14 AC
問題D 定期券
オーバラップする部分をうまく考えるだろうなとぼんやりと思うが、愚直に境界条件を書く。めちゃくちゃバグらせる。30分ぐらい使って今回も駄目だと思う、結局ひたすら紙でシミュレートして提出
12:41:01 AC
問題E 儀式
問題文が長い、読み気が起こらずオープンと本戦の順位を確認する。ちまちまF問題を解いてる人がいたのでF問題に移る。
問題F 順位表
問題を読む。グラフにしてトポロジカルソート?と思い色々と考えるが上手い解放が思い浮かばずトートバッグはダメかと思った。
サンプルを図に書いて色々と考えてみると順位が下の人から上の人にエッジを張り、高橋くんから辿れる頂点数を数えればいいと思い実装
13:09:57 AC
五完してほっとするここで順位表を確認するとそこそこの位置についていたはず
問題E 儀式
なぜか明らか通らない計算量でひたすら書いて提出してた。焼き肉会ラインは厳しい順位になってきて駄目かと思ってが色々とデバッグ用のコードを書いていると、手順をすべてシミュレートした後に一手戻してカウントを数えればいいことに気づき実装
14:10:30 AC
問題G 通勤電車と気分
問題を読むとdpぽいなあと思ったが今から僕の実力で満点をとる自信がないので部分点を狙いに行く。
14:47:03 WA 30
順位表を確認すると焼き肉ラインだったのでテンションが上がる。
問題H 模様替え
部分点を狙いに行くが実装が終わらずコンテスト終了
6完部分点の630点で8位
オープンのコンテスト順位表を除くとG問題を解いてる人が大量にいたので通したかった。
懇談会
風邪の症状が酷くなり熱っぽいがご飯のために参加(面倒くさくなって交通費の精算をしなかったので元を取ろうと思った)
普段プロコンやってる人はそこまでいなかった印象。
上位陣は日程が合わずに本線不参加の人もちらほら、太鼓の達人とDDRが置いてあるがひたすらご飯を食べる(ぼっち最高)
書道コーディングをするがn年ぶりの書道で恐ろしく字が汚い
CodeRunnerの話をしたり、普段どんなことしてるなど話してた。圧倒的学部生率が高くて羨ましいと思った。リクルートの中の人に僕の女々しい本戦落ちツイートを補足されていたり、僕のtwitterを特定してる人が何人かいたり帰りに研究内容について話したりした。
来年は本戦に出場できるように頑張ります(小並感)
AtCoder Beginner Contest #010 D - 浮気予防
蟻本のフローを写経する所までだった。
本番では通せなかった問題だが、冷静に考えれば写経(蟻本)するだけだった。
詳しい事は蟻本を読もう。
問題
http://abc010.contest.atcoder.jp/tasks/abc010_4解法
新たに終点(N)を作成してマークされてる女の子から終点に辺を張り、高橋君(始点)からフローを流す。コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; const int MAX_V = 110; struct edge { int to,cap,rev; }; vector<edge> G[MAX_V]; bool used[MAX_V]; void add_edge(int from,int to,int cap){ G[from].push_back((edge){to,cap,G[to].size()}); G[to].push_back((edge){from,0,G[from].size() - 1}); } int dfs(int v,int t,int f){ if(v == t)return f; used[v] = true; for(int i = 0;i < G[v].size();i++){ edge &e = G[v][i]; if(!used[e.to] && e.cap > 0){ int d = dfs(e.to,t,min(f,e.cap)); if(d > 0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s,int t){ int flow = 0; for(;;){ memset(used, 0, sizeof(used)); int f = dfs(s,t,INF); if(f == 0)return flow; flow += f; } } int N,V,E; int main(){ cin>>N>>V>>E; for(int i = 0;i < V;i++){ int x; cin>>x; add_edge(x, N, 1); } for(int i = 0;i < E;i++){ int x,y; cin>>x>>y; add_edge(x, y, 1); add_edge(y, x, 1); } cout <<max_flow(0, N)<<endl; return 0; }
AtCoder Beginner Contest #010 C - 浮気調査
問題
http://abc010.contest.atcoder.jp/tasks/abc010_3解法
一人の女の子だけ訪れて目的地に向かうと考えて全通り試した。誤差死が怖かったが通った。
EPSを足した方が安全である。
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; int main(){ int sx,sy,tx,ty,T,V; cin>>sx>>sy>>tx>>ty>>T>>V; int n; int x,y; vector<pii> data; cin>>n; for(int i = 0;i < n;i++){ cin>>x>>y; data.push_back(mp(x,y)); } bool flag =false; for(int i = 0;i < data.size();i++){ double sum1 =sqrt((data[i].first - sx)*(data[i].first - sx) + (data[i].second - sy)*(data[i].second - sy)); double sum2 =sqrt((data[i].first - tx)*(data[i].first - tx) +(data[i].second - ty)*(data[i].second - ty)); int walk = T*V; // cout <<"sum = "<<sum1+sum2<<endl; if(walk >=sum1 + sum2){ flag =true; break; } } if(flag){ cout <<"YES"<<endl; }else{ cout <<"NO"<<endl; } return 0; }
AtCoder Beginner Contest #010 B - 花占い
問題
与えられる数列にそれぞれ花びらの枚数が書かれている。以下2つの方法で花占いが行われて、どちらの方法でも結果が『嫌い』にならないように事前に毟る最小の花びらの枚数を返せ
1『好き』『嫌い』『好き』『嫌い』・・・
2『好き』『嫌い』『大好き』『好き』『嫌い』『大好き』・・・
解法
与えられる花びらの枚数は高々9枚までなので単純に場合分けした。コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; int n; int main(){ cin>>n; vector<int > data; int sum = 0; for(int i = 0;i < n;i++){ int x; cin>>x; if(x == 1 || x == 3 || x == 7 || x == 9)continue; else if (x == 5){ sum +=2; }else if(x ==6){ sum +=3; }else{ sum +=1; } } cout <<sum<<endl; return 0; }