akhauriyash/Code-Regression huggingface dataset:
# abc103_b.py
# https://atcoder.jp/contests/abc103/tasks/abc103_b

# B - String Rotation /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# 英小文字からなる文字列 S, Tが与えられます。
# Sを回転させて Tに一致させられるか判定してください。
# すなわち、以下の操作を任意の回数繰り返して Sを Tに一致させられるか判定してください。

# 操作: S=S1S2...S|S|のとき、S を S|S|S1S2...S|S|−1に変更する
# ここで、|X|は文字列 Xの長さを表します。

# 制約
#     2≤|S|≤100
#     |S|=|T|S, Tは英小文字からなる

# 入力
# 入力は以下の形式で標準入力から与えられる。
# S
# T

# 出力
# Sを回転させて Tに一致させられる場合は Yes、一致させられない場合は No を出力せよ。

# 入力例 1
# kyoto
# tokyo

# 出力例 1
# Yes
#     1回目の操作で kyoto が okyot になります
#     2回目の操作で okyot が tokyo になります

# 入力例 2
# abc
# arc

# 出力例 2
# No

# 何度操作を行っても abc と arc を一致させられません。

# 入力例 3
# aaaaaaaaaaaaaaab
# aaaaaaaaaaaaaaab

# 出力例 3
# Yes


def calculation(lines):
    la = lines[0]
    lb = lines[1]
    flag = False
    for _ in range(len(la)):
        la = la[1:] + la[:1]
        if la == lb:
            return ['Yes']
    return ['No']


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['kyoto', 'tokyo']
        lines_export = ['Yes']
    if pattern == 2:
        lines_input = ['abc', 'arc']
        lines_export = ['No']
    if pattern == 3:
        lines_input = ['aaaaaaaaaaaaaaab', 'aaaaaaaaaaaaaaab']
        lines_export = ['Yes']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 1000000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main() {
    ll N;
    string S;
    cin >> N;
    cin >> S;
    ll count_R = 0;
    ll count_G = 0;
    ll count_B = 0;
    ll S_len = (int) (S.length());
    FOR(i,0,S_len-1) {
        if (S[i]=='R') count_R+=1;
        if (S[i]=='G') count_G+=1;
        if (S[i]=='B') count_B+=1;
    }

    ll count = 0;
    FOR(i,0,S_len-3) {
        FOR(j,i+1,S_len-2) {
            if (j+(j-i) >= N) continue;
            if (S[i]==S[j] || S[j]==S[j+(j-i)] || S[j+(j-i)]==S[i]) {
                continue;
            }
            count += 1;
        }
    }
    cout << count_R*count_G*count_B-count << endl;
}

Measured memory_bytes: 3564
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Practice
{
    class Program
    {
        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);


        }

        static void SolveA(string[] args)
        {
            int[] ab = ReadAndParseIntArr();
            int a = ab[0];
            int b = ab[1];
            List<int> list = new List<int>();
            list.Add(a + b);
            list.Add(a - b);
            list.Add(a * b);
            int max = list.Max();
            Console.WriteLine(max);
        }
    }
}


Measured memory_bytes: 13268
/*====Corycle====*/
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<map>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const int Mod=1e9+7;
const int M=(1<<17)+5;
const int N=42;
int read(){
	int s=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
	return s*f;
}
int n,x,y,z,Ans,Sta,Goal,f[N][M];
int mod(int x){return x>=Mod?x-Mod:x;}
int main(){
//	freopen("_.in","r",stdin);
//	freopen("_.out","w",stdout);
	n=read();x=read();y=read();z=read();
	Sta=(1<<(x+y+z))-1;
	Goal=(1<<(x+y+z-1))|(1<<(y+z-1))|(1<<(z-1));
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int S=0;S<=Sta;S++){
			for(int k=1;k<=10;k++){
				int T=((S<<k)|(1<<(k-1)))&Sta;
				if((Goal|T)==T)continue;
				f[i][T]=mod(f[i][T]+f[i-1][S]);
			}
		}
	}
	Ans=1;
	for(int i=1;i<=n;i++)Ans=1ll*Ans*10%Mod;
	for(int S=0;S<=Sta;S++)Ans=mod(Ans-f[n][S]+Mod);
	printf("%d\n",Ans);
	return 0;
}

Measured memory_bytes: 24056
R,G,B,N=map(int,input().split())
L=sorted([R,G,B])
M=N//L[2]
ans=0
for i in range(M+1):
  n=N-i*L[2]
  MM=n//L[1]
  for j in range(MM+1):
    ans+= 1 if (n-j*L[1])%L[0]==0 else 0
print(ans)

Measured memory_bytes: 40300
using System;

public class hello
{
    public const int MOD = 100000;
    public static void Main()
    {
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var w = int.Parse(line[0]);
            var h = int.Parse(line[1]);
            if (w == 0 && h == 0) break;
            var dp = new int[w, h, 2, 2];
            for (int i = 0; i < w; i++)
            {
                dp[i, 0, 1, 0] = 1;
                dp[i, 0, 0, 1] = 1;
            }
            for (int i = 0; i < h; i++)
            {
                dp[0, i, 0, 0] = 1;
                dp[0, i, 1, 1] = 1;
            }
            goDP(dp, h, w);
            var ans1 = dp[w - 2, h - 1, 1, 0] + dp[w - 2, h - 1, 1, 1];
            var ans2 = dp[w - 1, h - 2, 0, 0] + dp[w - 1, h - 2, 0, 1];
            var ans = (ans1 + ans2);
            ans %= MOD;
            Console.WriteLine(ans);
        }
    }
    static void goDP(int[,,,] dp, int h, int w)
    {
        for (int i = 1; i < w; i++)
            for (int j = 1; j < h; j++)
            {
                dp[i, j, 0, 0] = dp[i, j - 1, 0, 0] + dp[i, j - 1, 0, 1];
                dp[i, j, 0, 1] = dp[i - 1, j, 1, 0];
                dp[i, j, 1, 0] = dp[i - 1, j, 1, 0] + dp[i - 1, j, 1, 1];
                dp[i, j, 1, 1] = dp[i, j - 1, 0, 0];
                dp[i, j, 0, 0] %= MOD;
                dp[i, j, 0, 1] %= MOD;
                dp[i, j, 1, 0] %= MOD;
                dp[i, j, 1, 1] %= MOD;
            }
    }
}



Measured memory_bytes: 15784
import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] l = line.split(" ");
        int r = Integer.parseInt(l[0]);
        int c = Integer.parseInt(l[1]);

        int[] SUM = new int[c];
        for(int i = 0; i <= r; i++) {

          int sum = 0;

          if(i != r) {
            line = sc.nextLine();
            String[] L = line.split(" ");

            for(int j = 0; j < c; j++) {
              int C = Integer.parseInt(L[j]);
              System.out.print(C + " ");
              sum += C;
              SUM[j] += C;
            }
          }

          if(i == r) {
            for(int j = 0; j < c; j++) {
              int C = SUM[j];
              System.out.print(C + " ");
              sum += C;
            }
          }

          System.out.println(sum);
        }
    }
}

Measured memory_bytes: 31444
# include <iostream>


using namespace std;


int main() {
    int n, k, a; cin >> n >> k;
    for (int i=0; i<n; i++) cin >> a;

    int cur = k;
    int ans = 1;

    while (1) {
        if (cur >= n) break;
        cur += k-1;
        ans++;
    }

    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 504
#include <iostream>

using namespace std;
int gcd(int a, int b)
{
//	cout << a << " " << b << endl;
	if (!a) return b;
	if (!b) return a;
	if (a < b) return gcd(a, b % a);
	return gcd(a % b, b);
}

int main()
{
	int a, b;
	cin >> a >>b;
	cout << gcd(a, b) << endl;
	return 0;
}

Measured memory_bytes: 1160
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    std::ios::sync_with_stdio(false);

    int A,B;
    while (cin >> A >> B) {
        int ans = 0;
        FOR(i,1,10) FOR(j,0,10) FOR(k,0,10) {
            const int v = i*1e4 + j*1e3 + k*1e2 + j*10 + i;
            if (A <= v && v <= B)
                ans++;
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<long long> A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  long long dp[200010][3];
  if(N%2==1){
    for(int i=0;i<N;i++){
      if(i==0){dp[i][1]=A.at(0);}
      else if(i==1){dp[i][1]=max(A.at(0),A.at(1));}
      else{
        if(i%2==0){
          dp[i][0]=max(dp[i-2][0]+A.at(i),dp[i-1][1]);
          dp[i][1]=dp[i-2][1]+A.at(i);
        }
        else{
          dp[i][0]=max(dp[i-2][0]+A.at(i),dp[i-1][0]);
          dp[i][1]=max(dp[i-2][1]+A.at(i),dp[i-1][1]);
        }
      }
    }
    cout<<dp[N-1][0]<<endl;
  }
  else{
    for(int i=0;i<N;i++){
      if(i==0){dp[i][1]=A.at(0);}
      else if(i==1){dp[i][0]=max(A.at(0),A.at(1));}
      else{
        if(i%2==0){
          dp[i][0]=max(dp[i-2][0]+A.at(i),dp[i-1][0]);
          dp[i][1]=dp[i-2][1]+A.at(i);
        }
        else{
          dp[i][0]=max(dp[i-2][0]+A.at(i),dp[i-1][1]);
        }
      }
    }
    cout<<dp[N-1][0]<<endl;
  }
}

Measured memory_bytes: 9604
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>g[110000];
vector<int>v;
int color[110000];
bool ok=true;
int B,W;
void dfs(int a,int b){
	color[a]=b;
	//printf("%d %d\n",a,b);
	if(b)B++;
	else W++;
	for(int i=0;i<g[a].size();i++){
		if(!~color[g[a][i]]){
			dfs(g[a][i],!b);
		}else if(color[g[a][i]]==b){
			ok=false;
		}
	}
}
int sg[310];
int dp[2][110000];
int dp2[110000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	for(int i=0;i<a;i++)color[i]=-1;
	int now=0;
	for(int i=0;i<a;i++){
		if(!~color[i]){
			B=W=0;
			dfs(i,0);
			now+=min(B,W);
			if(max(B,W)-min(B,W)<300)sg[max(B,W)-min(B,W)]++;
			else v.push_back(max(B,W)-min(B,W));
		}
	}
	if(!ok){
		printf("-1\n");
		return 0;
	}
	for(int i=0;i<110000;i++)dp[0][i]=dp[1][i]=-1;
	dp[1][0]=0;
	for(int i=1;i<300;i++){
		int f=i%2;
		for(int j=0;j<110000;j++){
			if(~dp[f][j])dp[!f][j]=0;
			else dp[!f][j]=-1;
		}
		for(int j=0;j<110000;j++){
			if(j-i>=0&&~dp[!f][j-i]&&dp[!f][j-i]<sg[i]){
				if(!~dp[!f][j])dp[!f][j]=dp[!f][j-i]+1;
				else dp[!f][j]=min(dp[!f][j],dp[!f][j-i]+1);
			}
		}
	/*	if(i<5){
			for(int j=0;j<20;j++)printf("%d ",dp[!f][j]);
			printf("\n");
		}*/
	}
	for(int i=0;i<110000;i++)if(~dp[0][i])dp2[i]=1;
	for(int i=0;i<v.size();i++){
		for(int j=109999;j>=v[i];j--){
			dp2[j]|=dp2[j-v[i]];
		}
	}
	long long ret=0;
	for(int i=0;i<110000;i++){
		if(dp2[i]){
			ret=max(ret,(long long)(now+i)*(a-now-i)-b);
		}
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 9024
#include<bits/stdc++.h>
using namespace std;

typedef struct UnionFind{
    vector<int> par;
    vector<int> groups;
    UnionFind(int N) : par(N), groups(N){
        for(int i=0;i<N;++i){
            par[i] = i;
            groups[i] = 1;
        }
    }
    int root(int x){
        if(par[x]==x) return x;
        return par[x] = root(par[x]);
    }
    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx!=ry){
            par[rx] = ry;
            groups[ry] += groups[rx];
        }
    }
    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx==ry;
    }
    int size(int x){
        int rx = root(x);
        return groups[rx];
    }
}UF;

int main(void){
    long long n, m, a[100010], b[100010];
    cin >> n >> m;
    UF tree(n);
    for(int i=0;i<m;++i) cin >> a[i] >> b[i];
    long long ans[100010];
    ans[m] = n*(n-1)/2;
    for(int i=m-1;i>=0;--i){
        if(tree.same(a[i]-1,b[i]-1)){
            ans[i] = ans[i+1];
        }else{
            ans[i] = ans[i+1]-tree.size(a[i]-1)*tree.size(b[i]-1);
            tree.unite(a[i]-1, b[i]-1);
        }
    }
    for(int i=1;i<=m;++i){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 4480
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <utility>
#include <set>
#include <unordered_set>
#include <stack>
#include <iterator>
#include <random>
#include <fstream>
#include <chrono>
#include <math.h>
#include <cctype>
using namespace std;
#define int long long
#define forn(i, n) for (int i = 0; i < n; ++i)
int32_t main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int>a(1e5+10,0);
    int sum = 0;
    forn(i,n) {
        int tt;
        cin >> tt;
        a[tt]++;
        sum += tt;
    }
    int q;
    cin >> q;
    while(q--){
        int B,C;
        cin >> B >> C;
        a[C] += a[B];
        sum -= B * a[B];
        sum += a[B] * C;
        a[B]=0;
        cout << sum << "\n";
    }
    //int sum = 0;
    return 0;
}

Measured memory_bytes: 4008
#include <bits/stdc++.h>
using namespace std;

void fst()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
}
int nxt()
{
    int x;
    cin >> x;
    return x;
}
int nex_l()
{
    long long x;
    cin >> x;
    return x;
}

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define binary(n) cout << bitset<31>(n) << "\n";
#define FOR(i, n) for (int i = 0; i < n; i++)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define input_arr(a, n)         \
    for (int i = 0; i < n; i++) \
        cin >> a[i];
#define print_arr(a, n)         \
    for (int i = 0; i < n; i++) \
        cout << a[i] << " ";
#define deb(n) cerr << #n << "=" << n << "\n";

int main()
{
    int n,k;
    cin>>n>>k;
    vi a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(all(a));
    int sum=0;
    for(int i=0;i<k;i++){
        sum+=a[i];
    }
    cout<<sum;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;
const int INF = pow(2, 30) - 1;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N,K;
  cin >>N>>K;

  ll count = 1;

  while(N>=K){
    N = N/K;
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
from fractions import gcd
def lcm(a, b):
  return a * b // gcd (a, b)
A,B,C,D = map(int,input().split())
cnt_c = B // C - (A - 1) // C
cnt_d = B // D - (A - 1) // D
cnt_cd = B // lcm(C,D) - (A - 1) // lcm(C,D)
print(B - A + 1 - (cnt_c + cnt_d - cnt_cd))

Measured memory_bytes: 5076
//include----------------------------------------------------------------------------------------------------------------------
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cctype>
#include <vector>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <bitset>
#include <map>
#include <algorithm>
#include <memory>
#include <sstream>
#include <functional>
#include <iostream>
#include <fstream>
#include <set>

//using namespace--------------------------------------------------------------------------------------------------------------
using namespace std;

//define-----------------------------------------------------------------------------------------------------------------------
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, s, n) for(int i = s; i < n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define INF 1 << 25;
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//typedef----------------------------------------------------------------------------------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;

//const------------------------------------------------------------------------------------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

//global-----------------------------------------------------------------------------------------------------------------------
int n, m, repeet;
int ans;
char before[100000000];
char after[100000000];
char code[1000000000];
//function---------------------------------------------------------------------------------------------------------------------
int main(){
	while(scanf("%d", &n)){
		if (n == 0) return 0;
		rep(i, n)
			scanf("%s %s", &before[i], &after[i]);
		scanf("%d", &m);
		rep(i, m){
			scanf("%s", &code[i]);
			rep(j, n){
				if (code[i] == before[j]){
					code[i] = after[j];
					break;
				}
			}
		}
		printf("%s\n", code);
	}
	return 0;
}

Measured memory_bytes: 5372
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<int,int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int N,M;
vector<string> v;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
queue<P> Q;
int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++){
        string s;
        cin>>s;
        v.push_back(s);
    }
    vector<vector<int>> W(N,vector<int>(M,-1));
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
           if(v.at(i).at(j)=='#'){
               W.at(i).at(j)=0;
               Q.push(P(i,j));
           }
    }
    }
     while (!Q.empty()){
         P p=Q.front();
         Q.pop();
         for(int i=0;i<4;i++){
      int nx=p.first+dx.at(i);
      int ny=p.second+dy.at(i);
      if(nx<0||N<=nx||ny<0 ||ny>=M)continue;
      if(W.at(nx).at(ny)==-1){
            W.at(nx).at(ny)=W.at(p.first).at(p.second)+1;
            Q.push(P(nx,ny));
            }
         }
     }
     int res=0;
     for(int i=0;i<N;i++){
         for(int j=0;j<M;j++){
             chmax(res,W.at(i).at(j));
         }
     }
     cout<<res<<endl;
}


Measured memory_bytes: 13456
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <string>
#include <vector>
#include <vector>

using namespace std;

#define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

signed main(void)
{

  int n; cin >> n;
  int l; cin >> l;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) a[i] = l + i;

  int sum = accumulate(a.begin(), a.end(), 0);
  if (l <= 0 && 0 <= l + n - 1) {
    cout << sum;
  } else if (l > 0) {
    cout << sum - a[0];
  } else { // L + N - 1 < 0
    cout << sum - a[n - 1];
  }
  cout << endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

int main(void){
    int n, a[100010];
    cin >> n;
    int odd = 0, even = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] % 2 == 0) even++;
        else odd++;
    }
    
    if (n == 1) {
        if (a[0] % 2 == 0) {
            cout << "second" << endl;
        }
        else cout << "first" << endl;
        return 0;
    }
    
    if (odd == 0) cout << "second" << endl;
    else cout << "first" << endl;
}


Measured memory_bytes: 640
package main

import (
	"fmt"
	"strconv"
)

func rec(n int) []string {
	if n == 0 {
		return []string{""}
	}

	ret := []string{}
	prev := rec(n - 1)
	for _, s := range filter(prev, func(s string) bool { return n-1 == len(s) }) {
		ret = append(ret, s+"7")
		ret = append(ret, s+"5")
		ret = append(ret, s+"3")
	}

	ret = append(ret, prev...)

	return ret
}

func filter(slice []string, f func(s string) bool) []string {
	ret := []string{}
	for _, s := range slice {
		if f(s) {
			ret = append(ret, s)
		}
	}
	return ret
}

func has753(s string) bool {
	var has7, has5, has3 bool
	for _, c := range s {
		if c == '7' {
			has7 = true
		} else if c == '5' {
			has5 = true
		} else if c == '3' {
			has3 = true
		}
	}
	return has7 && has5 && has3
}

func lessThan(n int) func(s string) bool {
	return func(s string) bool {
		val, _ := strconv.Atoi(s)
		return val <= n
	}
}

func main() {
	var N int
	fmt.Scan(&N)

	n := len(strconv.Itoa(N))
	ans := filter(filter(rec(n), lessThan(N)), has753)
	fmt.Println(len(ans))
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 800;
int gr[N][N];
int cgr[N][N];
bool bprt = 0;
int col[N];
int n;
int dp[N][N];
int c1, c2;

void dfs(int v, int c) {
    col[v] = c;
    c1 += (c == 0) ? 1 : 0;
    c2 += (c) ? 1 : 0;
    for(int i = 1; i <= n; ++i) {
        if(cgr[v][i]) {
            if(col[i] == -1)
                dfs(i, c ^ 1);
            else if(col[i] != (c ^ 1))
                bprt = 0;
        }
    }
}


int main() {
    int m;
    cin>>n>>m;
    for(int i = 0; i < m; ++i) {
        int u, v;
        cin>>u>>v;
        gr[u][v] = 1;
        gr[v][u] = 1;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(i == j) continue;
            if(!gr[i][j]) cgr[i][j] = 1;
        }
    }
    
    memset(col, -1, sizeof(col));
    bprt = 1;
    vector<pair<int, int> > comp;
    for(int i = 1; i <= n; ++i) {
        if(col[i] == -1) {
            c1 = c2 = 0;
            dfs(i, 0);
            comp.push_back({c1, c2});
        }
    }
    if(bprt == 0) {
        cout<<-1<<endl;
    }
    else {
        int ans = INT_MAX;
        dp[0][0] = 1;
        for(int i = 0; i < comp.size(); ++i) {
            int c1 = comp[i].first;
            int c2 = comp[i].second;
            for(int j = 0; j <= n; ++j) {
                if(j >= c1 && dp[i][j - c1])
                    dp[i+1][j] = 1;
                if(j >= c2 && dp[i][j-c2])
                    dp[i+1][j] = 1;
            }
        }
        int sz = comp.size();
        for(int i = 1; i <= n; ++i) {
            if(dp[sz][i]) {
                ans = min(ans, i * (i-1) + (n - i)*(n - i - 1));
            }
        }
        cout<<ans/2<<endl;
    }

    return 0;
}

Measured memory_bytes: 7424
import math

n, d = map(int, input().split())

x = [list(map(int, input().split())) for i in range(n)]


def calc_length(d, p, q):
    sqr_length = 0
    for i in range(d):
        sqr_length += (p[i] - q[i]) ** 2

    return math.sqrt(sqr_length)


lengthes = list()

for i in range(n-1):
    p = x[i]
    for j in range(i+1, n):
        q = x[j]

        lengthes.append(calc_length(d, p, q))

ans = 0
for i in range(len(lengthes)):
    if isinstance(lengthes[i], int):
        ans += 1
    else:
        if lengthes[i].is_integer():
            ans += 1


print(ans)






Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;

// (n, m) @ (m, k) = (n, k)のとき、スカラー乗算の回数はn*m*k回
// 最適な分割を探していく

struct matrix
{
    int r, c;
};

int min_chain_mul(vector<matrix> M) {
    int c[M.size() + 1][M.size() + 1];
    for (int i = 1; i <= M.size(); i++) {
        c[i][i] = 0;
    }

    for (int l = 2; l <= M.size(); l++) { // span
        for (int i = 1; i <= M.size() - l + 1; i++) {
            int j = i + l -1;
            c[i][j] = (1 << 21);
            for (int k = i; k <= j - 1; k++) {
                c[i][j] = min(c[i][j], c[i][k]+c[k+1][j] + M.at(i-1).r * M.at(k-1).c * M.at(j-1).c);
            }
        }
    }
    // for (int i = 1; i <= M.size(); i++)
    //     cout << c[i][i+1] << endl;
    return c[1][M.size()];
}

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

    vector<matrix> M;
    for (int i = 0; i < n; i++)
    {
        matrix m;
        cin >> m.r >> m.c;
        M.push_back(m);
    }

    cout<< min_chain_mul(M) << endl;
}


Measured memory_bytes: 3176
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int a, b, c, k, m;
  cin >> a >> b >> c >> k;

  m=max({a, b, c});
  int sum=a+b+c-m;

  for (int i=1; i<=k; i++) m*=2;

  cout << m+sum;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
int_dic = {}
for ai in a:
    if ai in int_dic:
        int_dic[ai] += 1
    else:
        int_dic [ai] = 1
num_int = len(int_dic.keys())
if num_int <= k:
    print(0)
else:
    rpl = num_int - k
    value_ls = list(int_dic.values())
    value_ls.sort()
    print(sum(value_ls[:rpl]))

Measured memory_bytes: 34784
#include <iostream>
#include <complex>
using namespace std;
int main(){
    int x;
    cin >> x;
    int ex;
    int l[40];
    int max = 1;
    int maxi;
    int maxj;
    for(int i=1;i<=sqrt(x);i++){
        for(int j=2;j<=11;j++){
            ex = pow(i,j);
            if(ex > x) break;
            else if(ex >= max){
                max = ex;
                maxi = i;
                maxj = j;
                //cout << i <<' '<< j <<' '<< max << endl;
                //cout << maxi <<' '<< maxj <<' '<< pow(maxi,maxj) << endl;
            }
        }
    }
    //cout << max << endl;
    cout << pow(maxi,maxj) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int n;

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		string a,b;
		cin >> a;
		cin >> b;
		for(int j=a.size();j>=0;j--){
			if(a[j]=='C'){
				string c=b.substr(1)+b[0];
				b=c;
			}
			if(a[j]=='J'){
				string c=b[b.size()-1]+b.substr(0,b.size()-1);
				b=c;
			}
			if(a[j]=='E'){
				for(int k=0;k<b.size()/2;k++){
					swap(b[k],b[k+(b.size()+1)/2]);
				}
			}
			if(a[j]=='M'){
				for(int k=0;k<b.size();k++){
					if(b[k]>='0' && b[k]<='9'){
						if(b[k]=='9')b[k]='0';
						else b[k]++;
					}
				}
			}
			if(a[j]=='P'){
				for(int k=0;k<b.size();k++){
					if(b[k]>='0' && b[k]<='9'){
						if(b[k]=='0')b[k]='9';
						else b[k]--;
					}
				}
			}
			if(a[j]=='A'){
				reverse(b.begin(),b.end());
			}
		}
		cout << b << endl;
	}
	return 0;
}

Measured memory_bytes: 1236
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n>>m;
  cout<<n*m-(n*1+m*1-1)<<endl;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 892
N, C = map(int, input().split())

f = [[0] * 100000 for _ in range(C)]

for i in range(N):
    s, t, c = map(int, input().split())
    f[c-1][s-1:t] = [1] * (t-s+1)

print(max(map(sum, zip(*f))))


Measured memory_bytes: 26484
#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vi col;
vector<vi> ed;
bool dfs(int at, int co) {
	if (col[at])
		return (col[at] == co);
	col[at] = co;
	bool r = true;
	trav(e, ed[at]) {
		if (!dfs(e, 3-co)) r = false;
	}
	return r;
}

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N, M;
	cin >> N >> M;
	col.resize(N);
	ed.resize(N);
	rep(i,0,M) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		ed[a].push_back(b);
		ed[b].push_back(a);
	}

	ll lone = 0, bip = 0, nonb = 0, tot = 0;
	rep(i,0,N) if (!col[i]) {
		if (dfs(i, 1)) {
			if (ed[i].empty()) lone++;
			else bip++;
		} else {
			nonb++;
		}
		tot++;
	}

	cerr << lone << ' ' << bip << ' ' << nonb << endl;
	cout << nonb*nonb + 2*nonb*bip + 2*bip*bip + 2*lone*N - lone*lone << endl;
	exit(0);
}


Measured memory_bytes: 9984
#include <iostream>

#define MIN_N 1
#define MAX_N 100000
#define MIN_Q 1
#define MAX_Q 1000
#define MAX_TIME 50000
#define MAX_SUM_TIME 1000000

#define QUEUE_SIZE MAX_N+1

using namespace std;

struct Process {
  string name;
  int time;
  Process() {}
  Process(string& name, int time)
    : name(name)
    , time(time){}
};

class ProcessQueue {
public:
  ProcessQueue()
    : len(0)
    , headPos(0)
    , tailPos(0) {
  }

  void Enqueue(Process& proc) {
    len++;
    procs[tailPos++] = proc;
    if(tailPos >= QUEUE_SIZE) {
      tailPos = 0;
    }
  }
  Process Dequeue(){
    len--;
    Process proc = procs[headPos++];
    if(headPos >= QUEUE_SIZE) {
      headPos = 0;
    }
    return proc;
  }
  int Length() {
    return len;
  }
private:
  int len;
  int headPos;
  int tailPos;
  Process procs[QUEUE_SIZE];
};

int main() {
  int n, q;
  cin >> n >> q;

  ProcessQueue queue;
  for(int i=0; i<n; i++) {
    string name;
    int time;
    cin >> name >> time;
    Process proc(name, time);
    queue.Enqueue(proc);
  }

  int time = 0;
  while(queue.Length() > 0) {
    Process proc = queue.Dequeue();
    if(proc.time <= q) {
      time += proc.time;
      cout << proc.name << " " << time << endl;
    } else {
      time += q;
      proc.time -= q;
      queue.Enqueue(proc);
    }
  }

  return 0;
}

Measured memory_bytes: 7032
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
 int x;
  cin>>x;
  if(x==0){
    cout<<'1'<<endl;
  }
  else{
cout<<'0'<<endl;
  }
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int n=s.length(),m=t.length();
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0 || j==0)
                dp[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i-1]==t[j-1])
            {
                dp[i][j]=1+dp[i-1][j-1];
            }
            else

                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    string ans="";
    while(n>0 && m>0)
    {
        if(s[n-1]==t[m-1])
        {
            ans.push_back(s[n-1]);
            n--;
            m--;
        }
        else
        {
            if(dp[n-1][m]>dp[n][m-1])
                n--;
            else
                m--;
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
    return 0;

}


Measured memory_bytes: 38628
#include <stdio.h>
#include <string.h>
struct word {
	char s[33];
	int count;
};
int main() {
	struct word ws[1000];
	memset (ws, 0, sizeof(struct word) * 1000);
	int i, exist, num = 0;
	while (scanf(" %32s", ws[num].s) != EOF) {
		exist = 0;
		for (i = 0; i < num; i++) {
			if (!strcmp(ws[i].s, ws[num].s)) {
				ws[i].count += 1;
				exist = 1;
				break;
			}
		}
		if (!exist) {
			ws[num].count += 1;
			++num;
		}
	}
	int len = 0;
	int longlen = 0;
	int longidx;
	int times = 0;
	int timesidx;
	for (i = 0; i < num; i++) {
		len = strlen(ws[i].s);
		if (longlen < len) {
			longlen = len;
			longidx = i;
		}
		if (times < ws[i].count) {
			times = ws[i].count;
			timesidx = i;
		}
	}
	printf("%s %s\n", ws[timesidx].s, ws[longidx].s);
	return 0;
}

Measured memory_bytes: 592
debug = True

def insertionSort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        if debug: print(*A)

n = int(input())
arr = list(map(int, input().split()))

print(*arr)
insertionSort(arr, n)

Measured memory_bytes: 8116
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<queue>
using namespace std;


long long int slime[2500][2500]={};

int main() {
	long long int n,x,k,t[5500],a[5500],res;
	queue<int>que;
	priority_queue< long long int,vector<long long int>,greater<long long int> >pq;
	priority_queue<pair<long long int,pair<long long int ,long long int> > >pq2;
	
	cin>>n>>x;
	for(int i=0;i<=n-1;i++)
	{
		cin>>a[i];
		slime[i][0]=a[i];
	}
	for(int i=0;i<=n-1;i++)
	{
		for(int j=1;j<=n-1;j++)
		{
			slime[i][j]=min(slime[i][j-1],a[(i-j+n)%n]);
		}
	}
	
	for(int i=0;i<=n-1;i++)
	{
		res=x*i;
		for(int j=0;j<=n-1;j++)
		{
			res+=slime[j][i];
		}
		pq.push(res);
	}
	cout<<pq.top();
}


Measured memory_bytes: 41216
#include <bits/stdc++.h>

using namespace std;

int main()
{
  int W,H = 0;
  
  while(1)
    {
      
      cin >> H >> W;

      if(W == 0 && H == 0)
	{
	  break;
	}
  
      for(int n = 0;n < H;n++)
	{
	  for(int k = 0;k < W;k++)
	    {
	      cout << "#";
	    }
	  cout << endl;
	}
      
      cout << endl;
  
    }
    return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;

typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;

#define _  %  MOD
#define __ %= MOD

#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))

#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define fbo find_by_order
#define ook order_of_key

ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;} // modular exponent

int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
    ll n;
    cin>>n;
    vector<ll> a(n+1);
    repA(i,1,n) cin>>a[i];
    map<ll,ll> cnt;
    ll ans=0;
    repD(i,n,1)
    {
        if(cnt.find(i+a[i]) !=cnt.end())
        {
            ans+=cnt[i+a[i]];
        }
        cnt[i-a[i]]++;
    }
    cout<<ans<<'\n';
    return 0;
}
// JUST ASK YOURSELF DID YOU GIVE YOUR BEST ? ISSE ZYADA
// KUCH KAR BHI NAHI SAKTE !! ENJOY AND GIVE YOUR BEST!!


Measured memory_bytes: 16280
#include <bits/stdc++.h>
using namespace std;


const int S = 3e3 + 3;
double dp[S][S];

int main() {
int n;
	scanf("%d", &n);
	vector<double> H(n + 1), T(n + 1);
	for(int i = 1; i <= n; ++i) {
		cin >> H[i];
		T[i] = (1 - H[i]);
	}
	dp[0][0] = 1;
	for(int i = 1; i <= n; ++i) {
		dp[i][0] = (double)dp[i - 1][0] * T[i];
		for(int j = 1; j <= n; ++j) {
			dp[i][j] = (double)H[i] * dp[i - 1][j - 1] + (double)T[i] * dp[i - 1][j];
		}
	}
	double ans = 0;
	for(int j = n; j > n / 2; --j) {
		ans += dp[n][j];
	}
  	printf("%0.10f", ans);
}


Measured memory_bytes: 74128
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func solve() {
	a, b, c := getInt(), getInt(), getInt()

	ans := b + c
	if d := a + b + 1; d < c {
		ans = b + d
	}

	fmt.Fprintln(wr, ans)
}

// -----------------------------------------

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7+1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n,m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

/*--------------------template--------------------*/


int main(void)
{
	ll y[150], m[150], d[150];

	cin >> n;
	REP(i, n)
	{
		cin >> y[i] >> m[i] >> d[i];
	}

	REP(i, n)
	{
		ll day = 0;

		if (y[i] % 3 == 0) {
			day += ((20 - d[i] + 1) + ((10 - m[i]) * 20));
		} else {
			if (m[i] % 2 == 1) {
				day += (20 - d[i] + 1);
				day += ((10 - m[i]) / 2 + 1) * 19 + ((10 - m[i]) / 2) * 20;
				day += 5;
			} else {
				day += (19 - d[i] + 1);
				day += ((10 - m[i]) / 2) * 20 + ((10 - m[i]) / 2) * 19;
				day += 5;
			}
		}
		ll year = (1000 - y[i] - 1);
		day += (((year / 3) * 200) + ((year - year / 3) * 195));

		cout << day << endl;
	}
}

Measured memory_bytes: 3052
#include<bits/stdc++.h>
using namespace std;
char s[100005];
int len, mid, ans;
 
int main()
{
    scanf("%s", s + 1); len = strlen(s + 1); mid = (len) >> 1;
    for(int i = 1; i <= mid; ++i) if(s[i] == 'p') ans--;
    if(mid * 2 != len){
        if(s[mid + 1] == 'p') ans--;
    }
    for(int i = 1; i <= mid; ++i)
        if(s[len - i + 1] == 'g') ans++;
    cout << ans;
}

Measured memory_bytes: 384
A = int(input())
B = int(input())
C = int(input())
X = int(input())
list = []
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            list.append(500*a + 100*b + 50*c)
print(list.count(X))

Measured memory_bytes: 14060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vp;
typedef map<ll, ll> mll;
typedef map<string, ll> mstrll;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define indent() cout << '\n'
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
ll a, b, c, n, m, x, y, z, w, h, ans, cnt, mx, mn;
string s, t;
ll dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
//vll dx = {-1, 0, 1, -1, 1, -1, 0, 1}, dy = {-1, -1, -1, 0, 0, 1, 1, 1};
string alphabet = "abcdefghijklmnopqrstuvwxyz";

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> s){
        ans = 0;
        rep(i, 1, s.size()){
            if(s[i] != s[i - 1]){
                ans++;
            }
        }
        print(ans);
    }
}


Measured memory_bytes: 512
#include<stdio.h>
#include<math.h>

typedef struct Point{
  double x,y;
}Point;

void koch(int n,Point a,Point b){
  if(n == 0) return;
  Point s,t,u;
  double th = M_PI * 60.0/180.0;

  s.x = (2.0*a.x + 1.0 * b.x) /3.0;
  s.y = (2.0*a.y + 1.0 * b.y) /3.0;
  t.x = (1.0*a.x + 2.0 * b.x) /3.0;
  t.y = (1.0*a.y + 2.0 * b.y) /3.0;
  u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
  u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

  koch(n - 1,a,s);
  printf("%.8f %.8f\n",s.x,s.y);
  koch(n - 1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);
  koch(n - 1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  koch(n - 1,t,b);
}

int main(){
  Point a,b;
  int n;

  scanf("%d",&n);

  a.x = 0;
  a.y = 0;
  b.x = 100;
  b.y = 0;

  printf("%.8f %.8f\n",a.x,a.y);
  koch(n,a,b);
  printf("%.8f %.8f\n",b.x,b.y);
  return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N, M;
    while (cin >> N >> M, N) {
        int x;
        for (int i = 0; i < M; i++) {
            cin >> x;
            if (x == 1) N = 0;
        }
        printf("%.10f\n", N/2.0);
    }
    return 0;
}

Measured memory_bytes: 3200
n, d = map(int, input().split())

x = []

for i in range(n):
  x.append(list(map(int,input().split())))

import itertools

ans = 0

for v in itertools.combinations(x, 2):
  a, b = v
  n = 0
  for i in range(d):
    n += (a[i] - b[i]) ** 2
  n = n ** 0.5
  if str(n)[-1] == "0":
    ans += 1

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int main() {
  string s, t;
  cin >> s >> t;
  bool b = 1;
  vector<char> sv(s.size()), tv(t.size());
  rep(i, s.size()) sv[i] = s[i];
  rep(i, t.size()) tv[i] = t[i];
  sort(sv.begin(), sv.end());
  sort(tv.begin(), tv.end());
  reverse(tv.begin(), tv.end());
  rep(i, s.size()){
    if(sv[i] < tv[i]) break;
    else if(sv[i] > tv[i]){
      b = 0;
      break;
    }
    else if(i == t.size() - 1){
      b = 0;
      break;
    }
    else if(i == s.size() - 1) break;
  }
  if(b) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String c = sc.next();
    int l = c.length();
    String g = c.substring(0,l-1);
    if(s.equals(g))
      System.out.println("Yes");
      else
            System.out.println("No");
       }
       }

Measured memory_bytes: 35628