「 2018年10月 」一覧

AtCoder BC079 D: Wall

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

各数字を1に書き換えるコストが最小になるようにし、その合計を出せば良い。

「1に書き換える最小コスト」=「1への最短距離」と考えることが出来るので、事前にワーシャルフロイド法などで最短距離を求めておけば、あとは各Aijについて加算していけばよい。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdlib>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int H,W;

    cin >> H >> W;

    int c[10][10];

    REP(i,10)REP(j,10){
        int tmp;
        cin >> tmp;
        c[i][j] = tmp; 
    }

    REP(i,10)REP(j,10)REP(k,10){
        c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
    }

    int ans = 0;
    REP(i,H)REP(j,W){
        int a;
        cin >> a;
        if(a != -1 && a != 1){
            ans += c[a][1];
        }
    }

    cout << ans << endl;

}

AtCoder BC079 C: Train Ticket

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

演算子の場所は3カ所で+-の2通りしかない。そのため、全パターン試しても 通りで十分に速い。

全パターン試す実装はビット演算で実施。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    string str;
    int A,B,C,D;
    cin >> str;
    A = stoi(str) / 1000;
    B = stoi(str) / 100 % 10;
    C = stoi(str) / 10 % 10;
    D = stoi(str) % 10;
 
    REP(i,8){
        int tmp = A;
        char op1,op2,op3;
        if(i & 1){
            tmp += B;
            op1 = '+';
        }else{
            tmp -= B;
            op1 = '-';
        }
        if(i & 2){
            tmp += C;
            op2 = '+';
        }else{
            tmp -= C;
            op2 = '-';
        }
        if(i & 4){
            tmp += D;
            op3 = '+';
        }else{
            tmp -= D;
            op3 = '-';
        }
        if(tmp == 7){
            cout << A << op1 << B << op2 << C << op3 << D << "=7" << endl;
            return 0;
        }
    }
}

AtCoder Tenka1 Programmer Beginner Contest 参戦記

ABCやARCと違うコンテストに参加するのは今回が初でした。

KLabさん主催とのことですが、ほぼいつもの問題の感じと同じでしたね。

今度こそは水色に、と意気込んだのですが、Cの考察不足で最後までWAが残ってしまいまたもや撃沈でした。。。

A – Measure

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_a

解法

入力文字列の長さで分岐させるだけ

実装

s=gets.chomp
if s.size == 3
    puts s.reverse
else
    puts s
end

B – Exchange

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_b

解法

二人の操作を愚直にシミュレートしていくだけ

実装

a,b,k=gets.chomp.split.map(&:to_i)
k.times do |i|
    if i % 2 == 0
        if a%2 == 1
            a -= 1
        end
        b += a/2
        a /= 2
    else
        if b%2 == 1
            b -= 1
        end
        a += b/2
        b /= 2
    end
end

printf("%d %d\n",a,b)

C – Align

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

解法

整数の数Nはなので、全て列挙する方法だとぜんぜん間に合いません。

よってどういう並びが適切かを考えることになります。

例えば、1、3、5という3つの整数を並べる場合を考えます。

この場合、1 3 5 と3つを昇順に並べるのは、1 5 という並びと等価です。

なぜならば、1 3 5 は (5-3) + (3-1) = 4 であり、1 5は (5-1) = 4 となるため、真ん中に3を入れる意味が無くなります。これは降順についても同じです。

よって、並べ方のうち3つ以上が昇順(または降順)で現れるものは最適ではありません。

そのため、作る列をsで表すとすると、 のような凸凹の並びになります。

この際、整数の数が偶数か奇数かで分けて考える必要があります。

そこで実際にNが偶数の場合として6を考えてみます。

すると、 と が考えられます。

それぞれの計算結果は

となりますが、両者は並び順が異なるだけなので同じとみなせます。

前者を最大にすることを考えた場合、2倍で加算されるやにはなるべく大きい値、2倍で減算されるやにはなるべく小さい値を当てはめるべきです。

よって、事前に与えられた整数をソートしておき、大きい方の半分は2倍して加算、小さい方の半分は2倍して減算していけばよいことがわかります。ただし、中央値の2つの数については1倍のままにする必要があります。

次にNが奇数の場合として5を考えてみます。

今度は、 と が考えられます。

それぞれの計算結果は

となり、 両者は異なります。これは、並びの両端に大きい数を配置するか小さい数を配置するかの違いになります。(本番では2パターンあることに気づかずに片方だけ実装してしまい見事にWAをくらいました。。。)

よって、奇数の場合は両方のケースを計算してみて、結果が大きい方を解とすればよいです。

実装

n=gets.to_i
a = []
n.times do
    a << gets.to_i
end
a.sort!

ans = 0
if n % 2 == 0
    (n/2+1).upto(n-1) do |i|
        ans += a[i] * 2    
    end

    ans += a[n/2]
    (0).upto(n/2-2) do |i|
        ans -= a[i] * 2    
    end
    ans -= a[n/2-1]
else
    (n/2+1).upto(n-1) do |i|
        ans += a[i] * 2    
    end

    (0).upto(n/2-2) do |i|
        ans -= a[i] * 2    
    end
    ans -= a[n/2]
    ans -= a[n/2-1]

    tmp = ans
    ans = 0

    (n/2+2).upto(n-1) do |i|
        ans += a[i] * 2    
    end
    ans += a[n/2]
    ans += a[n/2+1]

    (0).upto(n/2-1) do |i|
        ans -= a[i] * 2    
    end

    ans = tmp if tmp > ans

end
puts ans

D – Crossing

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_d

解法

満たすべき条件の対称性や入力例1の結果を見る限り、部分集合に含まれる整数の数は全て等しいと予想されます。

そこで、試しに部分集合のサイズが3になるケースを考えてみます。

すると部分集合の組は {1, 2, 3} {1, 4, 5} {2, 4, 6} {3, 5, 6} となります。この場合、Nは6になります。

さらにサイズが4になるケースを考えてみます。

{1, 2, 3, 4} {1, 5, 6, 7} {2, 5, 8, 9} {3, 6, 8, 10} {4, 7, 9,10} となります。この場合、Nは10になります。

ここで、部分集合の組の数kは部分集合のサイズより1大きい点に気づくかどうかがポイントです。

例えば {1, 2, 3, 4}を基点に考えた場合、他の部分集合との積は必ず1つしかなく、かつ、各整数は各部分集合のうち2つにしか含まれないため、他の部分集合は4つしか作れません。

どの整数も部分集合の組の2つにしか含まれないため、 となります。

よって、この条件を満たさないNが与えられた場合は、解は NO となります。

では次に、具体的な組み合わせを列挙する方法ですが、本番ではここでつまずいてしまいました。。。

以下のように考えます。

を考えた場合、これは必ずユニークな値になります。

よって、iとjを2重ループでまわして組み合わせを列挙していき、そこに整数を1つずつ当てはめていきます。その際に、各部分集合にその整数を割り当てていき、最後に各部分集合に含まれる値を出力すればよいです。

実装

n=gets.to_i

k = 0
1.upto(1000) do |i|
    if i * (i-1) / 2 == n
        k = i
        break
    elsif i * (i-1) / 2 > n
        break
    end
end

if k == 0
    puts "No"
    exit
else
    puts "Yes"
end

s = 1
ans = []
1.upto(k-1) do |i|
    (i+1).upto(k) do |j|
        ans[i] = [] if ans[i] == nil
        ans[j] = [] if ans[j] == nil
        ans[i] << s
        ans[j] << s
        s += 1
    end
end
puts k
1.upto(k) do |i|
    printf("%d ", ans[i].size)
    puts ans[i].join(" ")
end

感想

400点のCはほぼ解法がわかっていたのに、もう一歩考察が足りずにWAとなってしまいました。

500点のDも考え方はあっていたのですが、組み合わせの列挙で躓いてしまった。

ということで、またしても水色手前で足踏み状態です。


AtCoder BC073 D: joisino’s travel

問題

https://beta.atcoder.jp/contests/abc073/tasks/abc073_d

解法

訪れる町の数が最大で8のため、訪れる順番の組み合わせは最大でも8!(=40320)通りです。

町の数は最大200であり、事前にワーシャルフロイド法(計算量はO(N3))等でそれぞれの町の間の最短距離を求めておけば、全ての組み合わせを試しても十分に間に合います。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

ll d[201][201];

int main(){
    int N, M, R;
    cin >> N >> M >> R;
    vector<int> r;

    REP(i,R){
        int tmp;
        cin >> tmp;
        r.push_back(tmp);
    }
    
    sort(r.begin(),r.end());

    REP(i,N+1)REP(j,N+1)d[i][j] = INF;

    REP(i,M){
        int a,b,c;
        cin >> a >> b >>c;
        d[a][b] = c;
        d[b][a] = c;
    }


    REP(i,N+1)REP(j,N+1)REP(k,N+1){
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
    }

    ll ans = INF;
    do {
        ll tmp = 0;
        REP(i,R-1){
            tmp += d[r[i]][r[i+1]];
        }
        ans = min(ans,tmp);
    } while (std::next_permutation(r.begin(), r.end()));

    cout << ans << endl;

}

AtCoder BC073 C: Write and Erase

問題

https://beta.atcoder.jp/contests/abc073/tasks/abc073_c

解法

数字の出現回数が

・偶数回:消えている
・奇数回:書かれている

ので、mapを使って出現回数をカウントしておき、最後に奇数回のものを数えれば解けます。

これ以外にもsetを使って操作をシミュレートしても良い。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    map<ll,int> m;

    REP(i,N){
        ll a;
        cin >> a;
        m[a]++;
    }

    int ans=0;
    for(auto itr = m.begin(); itr != m.end(); itr++){
        if(itr->second % 2 != 0){
            ans++;
        }
    }

    cout << ans << endl;
}

radikoのエリアフリーを保存する方法

以前、radikoのタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。

radikoのタイムフリーを保存する方法
先日、MacBookのOSをクリーンインストールした際、それまでradikoのタイムフリーの保存に使っていたradikoroの最新版がタイム...

基本的な手順は同じですが、異なるのは最初にログイン処理を行ってCookieをローカルに保存し、以降はそのCookieを送信する点です。

環境

OS: Mac OS High Sierra
必要なソフト:swftools、ffmpeg (Homebrewより導入)

事前準備

myplayer-release.swfのダウンロード

認証のための事前準備としてswfファイルをダウンロードする

$ curl -O http://radiko.jp/apps/js/flash/myplayer-release.swf

swfファイルから画像ファイルを取り出す

認証にキーとなる画像ファイルをswfextractで取り出す

$ swfextract myplayer-release.swf -b 12 -o authkey.png
$ ls authkey.png
authkey.png

実行

ログイン処理

エリアフリーの番組を保存する場合、この手順が必要になります。

最後のmailとpassにプレミア会員登録しているメールアドレスとパスワードを設定します。

$ curl -c cookie.txt 'https://radiko.jp/ap/member/login/login' \
-XPOST \
-H 'Content-Type: application/x-www-form-urlencoded' \
-H 'Referer: http://radiko.jp/' \
-H 'Pragma: no-cache' \
-H 'User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.1 Safari/603.1.30' \
-H 'X-Radiko-Device: pc' \
-H 'X-Radiko-App-Version: 4.0.0' \
-H 'X-Radiko-User: test-stream' \
-H 'X-Radiko-App: pc_ts' \
--data 'mail=aaaa@example.com&pass=password'

実行すると、cookie.txtにクッキーが保存されます。

以降のcurlコマンドではこのファイルを-bオプションで指定します。

認証1

認証1のURLにアクセスし、HTTPのレスポンスヘッダーから以下の3つの値を取得する

・X-Radiko-AuthToken
・X-Radiko-KeyLength
・X-Radiko-KeyOffset

$ curl -b cookie.txt 'https://radiko.jp/v2/api/auth1_fms' \
> -XPOST \
> -H 'Content-Type: application/x-www-form-urlencoded' \
> -H 'Referer: http://radiko.jp/' \
> -H 'Pragma: no-cache' \
> -H 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1 Safari/605.1.15' \
> -H 'X-Radiko-Device: pc' \
> -H 'X-Radiko-App-Version: 4.0.0' \
> -H 'X-Radiko-User: test-stream' \
> -H 'X-Radiko-App: pc_ts' \
> --data $'\r\n'
X-Radiko-AppType=pc
X-Radiko-AppType2=pc
X-Radiko-AuthToken=AJReLqXV-Oo4ymYpgRlhow
X-Radiko-AuthWait=0
X-Radiko-Delay=15
X-Radiko-KeyLength=16
X-Radiko-KeyOffset=121394

please send a part of key

事前準備でダウンロードしたキーとなる画像ファイルから、X-Radiko-KeyOffsetがオフセット、X-Radiko-KeyLengthが長さとなるデータを抽出する。

UNIXのddコマンドを使って抽出する。なお、抽出したデータはBase64で文字列に変換する。

$ dd if=authkey.png ibs=1 skip=121394 count=16 | base64
16+0 records in
0+1 records out
16 bytes transferred in 0.000669 secs (23916 bytes/sec)
kwMYHYGpTwcgn8OlMjBjyQ==

「kwMYHYGpTwcgn8OlMjBjyQ==」が認証2で使うParticalkeyとなる

認証2

認証2のURLに対して、AuthTokenとParticalkeyをPOSTする

curl -b cookie.txt 'https://radiko.jp/v2/api/auth2_fms' \
-XPOST \
-H 'Content-Type: application/x-www-form-urlencoded' \
-H 'Referer: http://radiko.jp/' \
-H 'Pragma: no-cache' \
-H 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1 Safari/605.1.15' \
-H 'X-Radiko-Device: pc' \
-H 'X-Radiko-Authtoken: AJReLqXV-Oo4ymYpgRlhow' \
-H 'X-Radiko-App-Version: 4.0.0' \
-H 'X-Radiko-User: test-stream' \
-H 'X-Radiko-Partialkey: kwMYHYGpTwcgn8OlMjBjyQ==' \
-H 'X-Radiko-App: pc_ts'

JP13,東京都,tokyo Japan

応答として地域の情報が帰ってくると認証は成功。

プレイリストの取得と音声の保存

プレイリスト取得用のURL(https://radiko.jp/v2/api/ts/playlist.m3u8)に対して、クエリとして放送局IDと開始、終了時間を指定してするとプレイリストを取得できます。

なお、lというクエリには15を指定するらしいのですが、意味は不明です。

放送局IDについてはググると出てくると思います。

curl -b cookie.txt 'https://radiko.jp/v2/api/ts/playlist.m3u8?station_id=MBS&l=15&ft=20181013222500&to=20181013235500' \
-XPOST \
-H 'Content-Type: application/x-www-form-urlencoded' \
-H 'Referer: http://radiko.jp/' \
-H 'Pragma: no-cache' \
-H 'User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1 Safari/605.1.15' \
-H 'X-Radiko-Authtoken: AJReLqXV-Oo4ymYpgRlhow' \
--data 'flash=1'

#EXTM3U
#EXT-X-VERSION:3
#EXT-X-STREAM-INF:PROGRAM-ID=1,BANDWIDTH=52973,CODECS="mp4a.40.5"
https://radiko.jp/v2/api/ts/chunklist/GTgzFQEx.m3u8

これをffmpegの引数として渡すことで、音声の保存が可能です。

なお、ffmpegの実行時はCookieを送信する必要はありません。

ffmpeg \
> -content_type 'application/x-www-form-urlencoded' \
> -headers 'Referer: http://radiko.jp/' \
> -headers 'Pragma: no-cache' \
> -headers 'X-Radiko-AuthToken: AJReLqXV-Oo4ymYpgRlhow' \
-user_agent 'User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1 Safari/605.1.15' \
> -i 'https://radiko.jp/v2/api/ts/chunklist/GTgzFQEx.m3u8' \
> -vn -acodec copy -bsf aac_adtstoasc out.m4a

iTunes等で聴けるように、ffmpegのオプションでm4a形式で保存するようにしています。

まとめ

以上の手順によってradikoのエリアフリーを保存することが出来ます。


AtCoder BC072 D: Derangement

問題

https://beta.atcoder.jp/contests/abc072/tasks/arc082_b

解法

左から順にpiをみていきます。

・pi ≠ iの時
何もせずに、右に1つ進む

・pi = iの時
次の数と入れ替えて、右に2つ進む。このとき、次の数(pi+1)がi+1かどうかは特に意識する必要は無い。どちらの場合も、入れ替え後に条件を満たすため。

 なお、数列の右端がpi = iの場合は、一つ前の数と入れ替えればOK。

以上です。

ちょっと400点とは思えないほど簡単です。

実装

#include<iostream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    int p[N];

    REP(i,N)cin >> p[i];

    int i = 0;
    int ans = 0;
    while(i < N){
        if(p[i] == i + 1){
            ans += 1;
            i += 2;
        }else{
            i++;
        }
    }

    cout << ans << endl;
}

AtCoder BC072 C: Together

問題

https://beta.atcoder.jp/contests/abc072/tasks/arc082_a

解法

aiがとりうる値は、ai-1、ai、ai+1の3つです。

なのでとりうる値の数をカウントする配列を用意しておき、各aiについてai-1、ai、ai+1の3カ所を1ずつ加算していけば、その最大値が解となります。

実装

aiが0となる場合の扱いを簡略化するため、aiと+1、+2の箇所を加算している。最終的な解は「個数の最大値」であるためこのままでも問題無い。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007
 
using namespace std;
 
typedef long long int ll;
 
const ll INF=(ll)1e18;
 
#define MAX 99999
 
int s[MAX+3];
 
int main(){
    int N;
    cin >> N;
 
    REP(i,MAX+3)s[i]=0;
 
    REP(i,N){
        int a;
        cin >> a;
 
 
        s[a]++;
        s[a+1]++;
        s[a+2]++;
 
    }
 
    int ans = 0;
 
    REP(i,MAX+3)ans = max(ans, s[i]);
 
    cout << ans << endl;
}

AtCoder BC 071 D: Coloring Dominoes

問題

https://beta.atcoder.jp/contests/abc071/tasks/arc081_b

解法

左から順にドミノの並びを見ていく場合、並び方は

・縦に1つ置く
・横に2つ重ねる

の2パターンです。

そこで、直前の並びに対する次の並びでの塗り方のパターンを考えます。

・「縦に1つ」→ 「縦に1つ」
 直前の色以外の2色が選べる = 2通り

・「縦に1つ」→ 「横に2つ」
 直前の色以外の2色について、どちらかを上、どちらかを下にする = 2通り

・「横に2つ」→ 「縦に1つ」
 必ず直前の色以外の1色を選ぶことになる = 1通り

・「横に2つ」→ 「横に2つ」
 上に直前の上下の2色以外を選ぶ場合、下は必ず直前の上の色になる = 1通り
 上に直前の下の色を選ぶ場合、下は残りの2色を選べる = 2通り
 合わせて3通りとなる

また、一番左側のドミノについては、

・「縦に1つ」= 3通り
・「横に2つ」= 3 x 2 = 6通り

となる。

よって、左側から順番にドミノの並びを検査していき、上記のパターンをかけていくと解ける。(毎回MODをとることを忘れない)

実装

#include<iostream>
#include<algorithm>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    string s1, s2;

    cin >> s1 >> s2;

    int i = 0;

    ll ans = 0;
    int flag;
    if(s1[i] == s2[i]){
        ans = 3;
        i += 1;
        flag = 1;
    }else{
        ans = 6;
        i += 2;
        flag = 2;
    }

    while(i < N){
        if(s1[i] == s2[i]){
            if(flag == 1){
                ans *= 2;
                ans %= MOD;
            }
            i += 1;
            flag = 1;
        }else{
            if(flag == 1){
                ans *= 2;
                ans %= MOD;
            }else{
                ans *= 3;
                ans %= MOD;
            }
            i += 2;
            flag = 2;
        }
    }

    cout << ans << endl;
}

AtCoder BC071 C : Make a Rectangle

問題

https://beta.atcoder.jp/contests/abc071/tasks/arc081_a

解法

長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます(正方形は長方形に含まれる)

 よって、同じ棒が2本現れる毎に辺の候補に追加し、その中から1番目に長いものと2番目に長いもので長方形を作れば解となります。

 なお、辺の候補が2つ以上無ければ解無しとして0を出力します。

実装

実装としては、同じ長さの棒のカウントにはmap、辺の候補の管理はvectorで行います。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    map<ll, int> m;
    vector<ll> a;

    REP(i,N){
        ll tmp;
        cin >> tmp;
        m[tmp]++;
        if(m[tmp] % 2 == 0){
            a.push_back(tmp);
        }
    }
    if(a.size() > 1){
        sort(a.begin(),a.end());
        cout << a[a.size()-1] * a[a.size()-2] << endl;
    }else{
        cout << 0 << endl;
    }

}