akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e8
#define EPS 1e-9

#define rep2(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) rep2(i,0,n)
#define ll long long
#define P pair<double,int>
#define pb push_back

int n,m,s,g,D[30][30],C[30][30];
double d[30][30][31];

int main(){
	while(cin>>n>>m&&n){
		cin>>s>>g;
		s--;g--;
		rep(i,n){
			fill(D[i],D[i]+n,INF);
			fill(C[i],C[i]+n,0);
			rep(j,n)fill(d[i][j],d[i][j]+31,INF);
		}
		rep(i,m){
			int x,y,d,c;
			cin>>x>>y>>d>>c;
			x--;y--;
			D[x][y]=D[y][x]=d;
			C[x][y]=C[y][x]=c;
		}
		double ans=INF;
		multimap<double,int> Q;
		d[s][s][0]=0.0;
		Q.insert(P(0.0,s*930+s*31+0));
		while(Q.size()){
			P p=*(Q.begin());
			Q.erase(Q.begin());
			double t=p.first;
			int cur=p.second/930,prev=(p.second/31)%30,v=p.second%31;
			if(t>d[cur][prev][v])continue;
			if(cur==g&&v==1){ans=d[cur][prev][v];break;}
			rep(i,n){
				if(i!=prev&&D[cur][i]!=INF){
					rep2(j,-1,2){
						int nv=v+j;
						if(0<nv&&nv<=C[cur][i]){
							double nt=t+D[cur][i]*1.0/nv;
							if(nt<d[i][cur][nv]){
								d[i][cur][nv]=nt;
								Q.insert(P(nt,i*930+cur*31+nv));
							}
						}
					}
				}
			}
		}
		if(ans!=INF)cout<<setprecision(10)<<ans<<endl;
		else cout<<"unreachable"<<endl;
	}
}

Measured memory_bytes: 0
#include <stdio.h>

int main()
{
	int n, m;
	int MatA[100][100];
	int MatB[100];

	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < m; ++j)
		{
			scanf("%d", &MatA[i][j]);
		}
	}
	for(int j = 0; j < m; ++j)
	{
		scanf("%d", &MatB[j]);
	}

	for(int i = 0; i < n; ++i)
	{
		int c = 0;
		for(int j = 0; j < m; ++j)
		{
			c += MatA[i][j] * MatB[j];
		}
		printf("%d\n", c);
	}
	return 0;
}


Measured memory_bytes: 2104
#include <stdio.h>

int main(void)
{
	char no[100];
	
	scanf("%s",no);
	
	if(no[0]!='9'&&no[1]!='9'){
		printf("No\n");
	}else{
		printf("Yes\n");
	}
	
	return 0;
	
}
		

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 1;
		while(i <= n) {
			int x = i;
			if(x % 3 == 0)	System.out.printf(" %d", i);
			else {
				while(x != 0) {
					if(x % 10 == 3) {
						System.out.printf(" %d", i);
						break;
					}
					x /= 10;
				}
			}
			i++;
		}
			System.out.printf("\n");
	}
}



Measured memory_bytes: 38640
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<utility>
#include<array>
#include<set>
#include <numeric>
#include <stdio.h>
#include <map>
#include <iomanip>
#include <sstream>
//#include <boost/math/common_factor_rt.hpp>
#include<fstream>
#define EPS (1e-7)
using namespace std;
#define ll long long



class Employee {
public:
	int id;
	int parent;
	vector<int> children;
	int salary;

	Employee() {
		
	}

	Employee(int num, int nparent) {
		id = num;
		parent = nparent;
		salary = -1;
	}



};



template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}





pair<int, int> count_nonzero_cluster(vector<int>& vs) {

	int number = 0;
	int prev = 0;
	int vmax = -1;
	pair<int, int> re = make_pair(number, vmax);
	for (auto& v:vs)
	{
		if (prev <= 0 && v > 0) {
			re.first += 1;
		}
		if (re.second < v)re.second = v;
		prev = v;
	}


	return re;
}

int main() {
	
	int N, K;
	cin >> N >> K;
	int temp;
	for (auto i = 0; i < N; i++)
	{
		cin >> temp;
	}


	int ans;
	if (N == K) {
		ans = 1;
	}
	else {
		ans = ceil((N-1) / (double)(K - 1));
	}

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

Measured memory_bytes: 256
### LCS 
# dp[i][j]: s[i],t[j]までの最長部分文字列の長さ
# s[i]==t[j]だったらs[i-1][j-1]+1,
# それ以外の場合はmax(s[i-1][j],s[i][j-1])

s= input()
t= input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si==tj:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])

ans =""
n = dp[-1][-1]
i = len(s)
j =len(t)
while n >0:
    if dp[i][j]==dp[i-1][j]:
        i-= 1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
        ans = s[i-1]+ans
        n-=1
        i-=1
        j-=1

print(ans)



Measured memory_bytes: 112604
import copy

class Dice(object):
    def __init__(self, nums):
        self.top, self.front, self.right, self.left, self.back, self.bottom = nums

    def roll(self, directions):
        if directions == 'E':
            self.top, self.right, self.left, self.bottom = self.left, self.top, self.bottom, self.right
            return

        if directions == 'N':
            self.top, self.front, self.back, self.bottom = self.front, self.bottom, self.top, self.back
            return

        if directions == 'S':
            self.top, self.front, self.back, self.bottom = self.back, self.top, self.bottom, self.front
            return

        if directions == 'W':
            self.top, self.right, self.left, self.bottom = self.right, self.bottom, self.top, self.left
            return

        self.roll(directions[0])
        self.roll(directions[1:])

    def equal(self, dice):
        d = copy.copy(self)

        if(dice.front == d.top):
            d.roll('S')
        elif(dice.front == d.right):
            d.roll('WS')
        elif(dice.front == d.left):
            d.roll('ES')
        elif(dice.front == d.back):
            d.roll('SS')
        elif(dice.front == d.bottom):
            d.roll('N')

        if(dice.top == d.right):
            d.roll('W')
        elif(dice.top == d.left):
            d.roll('E')
        elif(dice.top == d.bottom):
            d.roll('WW')

        return not(dice.top != d.top or dice.front != d.front or dice.right != d.right or dice.left != d.left or dice.back != d.back or dice.bottom != d.bottom)

if __name__ == '__main__':
    d1 = Dice([int(i) for i in input().split()])
    d2 = Dice([int(i) for i in input().split()])
    if d1.equal(d2):
        print('Yes')
    else:
        print("No")

Measured memory_bytes: 7356
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define MN 400005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,num,head[MN],dis[MN];
struct edge{int to,next,w;}g[MN<<1];
void ins(int u,int v,int w){g[++num].next=head[u];head[u]=num;g[num].to=v;g[num].w=w;}
set<int> now[MN];
map<int,vector<int> > co[MN]; 
queue<int> q;
void dfs(int u,int col,int d){
	now[u].insert(col);if(dis[u]==inf)dis[u]=d,q.push(u);
	for(int i=0;i<co[u][col].size();i++)if(!now[co[u][col][i]].count(col))if(dis[co[u][col][i]]>=d)dfs(co[u][col][i],col,d);
}
int main(){
	scanf("%d%d",&n,&m);memset(dis,0x3f,sizeof(dis));int x,y,v;
	for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&v),ins(x,y,v),ins(y,x,v),co[x][v].push_back(y),co[y][v].push_back(x);q.push(1);dis[1]=0;
	while(!q.empty()){
		int tmp=q.front();q.pop();
		for(int i=head[tmp];i;i=g[i].next)if(!now[tmp].count(g[i].w))dfs(tmp,g[i].w,dis[tmp]+1);
	}printf("%d\n",dis[n]==inf?-1:dis[n]);
}

Measured memory_bytes: 109824
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int A=sc.nextInt();
    int B=sc.nextInt();
    Long N=0L;
    
    for(int i=1;i<=B;i++){
      N=N+A;
      if(N%B==0){
        break;
      }
    }
    System.out.println(N);
  }
}

Measured memory_bytes: 24660
#include <iostream>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  int cnt_neg = 0;
  if (a < 0)
    cnt_neg = abs(a);
  if (b < 0)
    cnt_neg -= abs(b + 1);

  if (a <= 0 && b >= 0)
    cout << "Zero" << endl;
  else if (cnt_neg & 1)
    cout << "Negative" << endl;
  else
    cout << "Positive" << endl;

  return 0;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.format;

void main() {
  int n, q;
  string s;
  s = readln;
  formattedRead (s, " %d %d", &n, &q);
  s = readln;
  auto label = new char[q];
  auto go = new char[q];

  foreach (qid; 0 .. q) {
    string z = readln;
    auto spl = z.splitter.array;
    label[qid] = spl[0][0];
    go[qid] = spl[1][0];
  }

  bool checkL (int x) {
    if (x == 0) return true;
    if (x > n) return false;
    foreach (qid; 0 .. q) {
      if (s[x-1] == label[qid]) {
        if (go[qid] == 'L') { if (--x < 1) return true; }
        else if (++x > n) return false;
      }
    }
    return false;
  }
  
  bool checkR (int x) {
    debug stderr.writefln ("checkR %d\n", x);
    if (x == 0) return false;
    if (x > n) return true;
    foreach (qid; 0 .. q) {
      if (s[x-1] == label[qid]) {
        if (go[qid] == 'L') { if (--x < 1) return false; }
        else if (++x > n) return true;
      }
    }
    return false;
  }
  
  //[l, r)
  int l = 0, r = n + 1;
  while (r - l > 1) {
    int m = (l + r) >> 1;
    bool ch = checkL (m);
    debug stderr.writefln ("check(%d) = %s", m, ch);
    if (ch) l = m; else r = m;
  }
  immutable x1 = l + 1; 
  debug stderr.writefln ("x1 = %d", x1);
  
  l = 0; r = n + 1;
  while (r - l > 1) {
    int m = (l + r) >> 1;
    bool ch = checkR (m);
    debug stderr.writefln ("checkR(%d) = %s", m, ch);
    if (!ch) l = m; else r = m;
  }
  immutable x2 = l + 1;
  debug stderr.writefln ("x2 = %d", x2);
  writeln (max (0, abs (x2 - x1)));
}



Measured memory_bytes: 4092
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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


int main() {
    int A, B, C;
    cin >> A >> B >> C;

    int ans = (C / A) * B;

    cout << ans << endl;

    return 0;
}

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

int n;
vector<int> adj[100005];
long long memo[100005][2];

long long dp(int x,int p,int block){
	if(memo[x][block]!=-1)return memo[x][block];
	if(block){
		long long ans=1;
		for(int i=0;i<(int)adj[x].size();i++){
			if(adj[x][i]==p)continue;
			ans*=dp(adj[x][i],x,0);
			ans%=1000000007;
		}
		return memo[x][block]=ans;
	}else{
		long long ans=1,ans2=1;
		for(int i=0;i<(int)adj[x].size();i++){
			if(adj[x][i]==p)continue;
			ans*=dp(adj[x][i],x,1);
			ans2*=dp(adj[x][i],x,0);
			ans%=1000000007;
			ans2%=1000000007;
		}
		return memo[x][block]=(ans+ans2)%1000000007;
	}
}

int main() {
	scanf("%d",&n);
	int x,y;
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&x,&y); x--; y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	memset(memo,-1,sizeof(memo));
	printf("%lld",dp(0,-1,0));
}

Measured memory_bytes: 14976
#include<iostream>
using namespace std;
int people[35];
int main(){
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int k;
		cin>>k;
		for(int j=1;j<=k;j++){
			int x;
			cin>>x;
			people[x]++;
		}
	}
	for(int i=1;i<=m;i++)
		ans+=(people[i]==n);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<tuple>
#include<string>
typedef unsigned long long ll;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repm(i,a,b) for(int i=(a);i>(b);i--)
#define F first
#define S second
using namespace std;
const ll INF = 1e12;
const int i_INF = 2147483647;
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 main() {
  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  int x = y1-y2;
  int y=x2-x1;
  cout<<x2+x<<" "<<y2+y<<" "<<x1+x<<" "<<y1+y<<endl;
    
  
}

Measured memory_bytes: 256
IDENTIFICATION DIVISION.
PROGRAM-ID. ABC110B.

DATA DIVISION.
WORKING-STORAGE SECTION.
77 N PIC 9(3).
77 M PIC 9(3).
77 X PIC S9(4).
77 Y PIC S9(4).
77 T PIC S9(4).
77 L PIC X(500).
77 PTR PIC 9(3).

PROCEDURE DIVISION.
ACCEPT L.
UNSTRING L DELIMITED ALL SPACE INTO N, M, X, Y.
ACCEPT L.
MOVE 1 TO PTR.
PERFORM N TIMES
UNSTRING L DELIMITED ALL SPACE INTO T POINTER PTR
IF X < T
  MOVE T TO X
END-IF
END-PERFORM.
ACCEPT L.
MOVE 1 TO PTR.
PERFORM M TIMES
UNSTRING L DELIMITED ALL SPACE INTO T POINTER PTR
IF T < Y
  MOVE T TO Y
END-IF
END-PERFORM.
IF X < Y
  DISPLAY "No War"
ELSE
  DISPLAY "War"
END-IF.
STOP RUN.


Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    for (int i = n; i <= 100003; i++){
        for (int j = 2; j*j <= i; j++){
            if (i % j == 0) goto done;
        }
        printf("%d",i);
        break;
        done:;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
  int a[4];
  for(int i=0; i<4; i++) {
    cin >> a[i];
  }
  sort(a,a+4);
  if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n;
    while(cin >> n, n){
        vector<int> v(n);
        for (auto &&i : v) scanf("%d", &i);
        array<int, 3> ans{}; long double a = INF<int>;
        for (int S = 0; S < 16; ++S) {
            for (int A = 0; A < 16; ++A) {
                for (int C = 0; C < 16; ++C) {
                    vector<int> R(n+1);
                    R[0] = S;
                    long double ent = 0;
                    for (int i = 1; i <= n; ++i) {
                        R[i] = (A*R[i-1]+C)%256;
                    }
                    map<int, int> m;
                    for (int i = 0; i < n; ++i) {
                        m[(v[i]+R[i+1])%256]++;
                    }
                    for (auto &&j : m) {
                        ent += -1.0*j.second/n*log(1.0*j.second/n);
                    }
                    if(ent < a){
                        a = ent;
                        ans = {S, A, C};

                    }

                }
            }
        }
        for (int i = 0; i < 3; ++i) {
            if(i) cout << " ";
            cout << ans[i];
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 3400
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define FORD(x,y,z) for(int x=y;x>=z;x--)
#define MSET(x,y) memset(x,y,sizeof(x))
#define FOR(x,y) for(__typeof(y.begin()) x=y.begin();x!=y.end();x++)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 1005
void RI(){}
template<typename... T>
void RI( int& head, T&... tail ) {
  scanf("%d",&head);
  RI(tail...);
}
using namespace std;
int x, y, z, k;
typedef long long LL;
LL inx[M], iny[M], inz[M];
map<LL,bool> vis;

class Node {
	public:
		int x, y, z;
		LL sum;
		Node(int _x, int _y, int _z, LL _sum){
			this->x = _x, this->y = _y, this->z = _z, this->sum = _sum;
		}
};
class compare{
	public:
		bool operator () (Node* lhs, Node* rhs) {
			return lhs->sum < rhs->sum;
		}
};

void dijkstra() {
	priority_queue<Node*, vector<Node*>, compare> q;
	q.push(new Node(0,0,0,inx[0]+iny[0]+inz[0]) );
	while(!q.empty() && k) {
		Node* cur = q.top();
		q.pop();
		LL index = cur->x*100000000 + cur->y*10000 + cur->z;
		if(vis.find(index) != vis.end() ) continue;
		vis.insert(pair<LL,bool>(index, true));
		cout << cur->sum << endl;
		k--;
		if(cur->x+1 < x && vis.find((cur->x+1)*100000000 + (cur->y)*10000 + cur->z) == vis.end()) 
			q.push(new Node(cur->x+1, cur->y, cur->z, cur->sum-inx[cur->x]+inx[cur->x+1]) );
		if(cur->y+1 < y && vis.find((cur->x)*100000000 + (cur->y+1)*10000 + cur->z) == vis.end()) 
			q.push(new Node(cur->x, cur->y+1, cur->z, cur->sum-iny[cur->y]+iny[cur->y+1]) );
		if(cur->z+1 < z && vis.find((cur->x)*100000000 + (cur->y)*10000 + cur->z+1) == vis.end())
			q.push(new Node(cur->x, cur->y, cur->z+1, cur->sum-inz[cur->z]+inz[cur->z+1]) );
	}
}

int main()
{ 
	cin >> x >> y >> z >> k;
	for(int j = 0; j < x; j++) cin >> inx[j];
	for(int j = 0; j < y; j++) cin >> iny[j];
	for(int j = 0; j < z; j++) cin >> inz[j];
	sort(inx, inx+x, greater<LL>());
	sort(iny, iny+y, greater<LL>());
	sort(inz, inz+z, greater<LL>());
	dijkstra();
  return 0;
}


Measured memory_bytes: 768
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end

a,b=get_i
if a<=b
  puts a
else
  puts a-1
end

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main() {
    int N,L;
    cin >> N >> L;
    int syokou, makkou;
    syokou = L;
    makkou = L + N -1;
    int eat;
    if (syokou < 0) {
        if(makkou < 0) {
            eat = makkou;
        }else{
            eat = 0;
        }
    }else{
        eat = syokou;
    }
    int sum = N*(syokou+makkou)/2;
    cout << sum - eat;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=210;
long long n,a[N],sum;
int main()
{
	cin>>n;
	n=n*2;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<n;i+=2)
	{
		sum+=a[i]; 
	}
	cout<<sum<<endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const ll inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

struct Edge {
    ll to, cost;
};
vector< vector<Edge> > G;

struct Node {
    ll v, speed;
    bool f;
    ll cost;
};
bool operator>(const Node& n1, const Node& n2) {
    return n1.cost > n2.cost;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll n, m; cin >> n >> m;
    G.resize(n);
    REP(i, m) {
        ll x, y, t; cin >> x >> y >> t; --x, --y;
        G[x].pb({y, t});
        G[y].pb({x, t});
    }
    ll v0; cin >> v0;
    ll A, B, C; cin >> A >> B >> C;
    vector<vector<vector<ll>>> dist(n, vector<vector<ll>>(C, vector<ll>(2, linf)));
    dist[0][v0][0] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> Q;
    Q.push({0, v0, false, 0});
    while ( !Q.empty() ) {
        Node node = Q.top(); Q.pop();
        ll v = node.v;
        ll speed = node.speed;
        bool f = node.f;
        ll cost = node.cost;
        if (cost > dist[v][speed][f]) continue;
        EACH(e, G[v]) {
            ll nd = cost + speed * e.cost;
            ll ns = (A * speed + B) % C;
            bool nf = f || e.to == n-1;
            if (nd < dist[e.to][ns][nf]) {
                dist[e.to][ns][nf] = nd;
                Q.push({e.to, ns, nf, nd});
            }
        }
    }
    ll ans = linf;
    REP(i, C) {
        ans = min(ans, dist[0][i][1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 11992
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define forn(i,a,n) for(int i =a;i < n; i++)
#define __ ios_base::sync_with_stdio(0);cin.tie(0);
#define fi first
#define se second
#define pb push_back
typedef long long int lli;
typedef pair<int,int> pii;
typedef vector<lli> vi;
#define MAXN 200005
lli dp[MAXN][3];
vi pref[MAXN],suf[MAXN];
vi adj[MAXN];
lli ans[MAXN];
int m;

lli gpref(int u, int i){
	if(i-1 >= 0)
		return pref[u][i-1]%m;
	return 1ll;
}

lli gsuf(int u, int i){
	if(i+1 < suf[u].size())
		return suf[u][i+1]%m;
	return 1ll;
}

int dfs(int u, int p, int c){
	if(dp[u][c]  != -1) return dp[u][c]%m;
	dp[u][c] = 1;
	pref[u].resize(adj[u].size());
	suf[u].resize(adj[u].size());
	for(int i =0; i < adj[u].size(); i++){
		int v = adj[u][i];
		if(v == p){
			pref[u][i] = 1ll;
			suf[u][i] = 1ll;
			continue;
		}
		lli res = 0;
		
		if(c == 0){//negro
			res = (dfs(v,u,0) + dfs(v,u,1)) % m;
			dp[u][c] = (dp[u][c] * res) % m;
		}
		else{
			res = dfs(v,u,1) % m;
			dp[u][c] = (dp[u][c] * res)%m;
		}
		pref[u][i] = res;
		suf[u][i] = res;
	}
	//pref
	for(int i =1; i < pref[u].size(); i++){
		pref[u][i] = (pref[u][i] * pref[u][i-1])%m;
	}
	for(int i = suf[u].size()-2; i >=0; i--){
		suf[u][i] = (suf[u][i] * suf[u][i+1])%m;
	}
	return dp[u][c] % m;
}

void dfs2(int u, int p){
	//if(u!= 1){
	dp[u][0] = (dp[u][0] * (dp[p][0]+1) % m) %m;
	ans[u] = dp[u][0]%m;
	//}
	for(int i =0; i < adj[u].size(); i++){
		int v = adj[u][i];
		if(v == p) continue;
		lli og = dp[u][0];
		lli poner = (gpref(u,i) * gsuf(u,i))%m;
		poner = (poner * (dp[p][0]+1)%m ) %m;
		dp[u][0] = poner;
		dfs2(v,u);
		dp[u][0] = og;
	}
}

int main(){__
	int n;
	cin >> n >> m;
	for(int i =0;i < MAXN; i++) dp[i][0] = dp[i][1] = -1;
	dp[0][0] = dp[0][1] = 0;
	for(int i = 1; i < MAXN; i++) dp[i][1] = 1;
	for(int i =0; i < n-1;i++){
		int u,v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	cout <<  dfs(1,0,0)%m << endl;
	//dfs(1,1,1);
	dfs2(1,0);
	for(int i =2;i <=n; i++) cout << ans[i]%m << endl;
}


Measured memory_bytes: 40448
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)   for(signed i=0; i<n; i++)
#define FOR(i, k, n)    for(signed i=k; i<n; i++)
#define yn(b)   cout << ((b)?"Yes":"No") << endl
#define YN(b)   cout << ((b)?"YES":"No") << endl
#define pr(r)   cout << r << endl
#define min(x,y)    (x<y)?x:y
#define max(x,y)    (x>y)?x:y
#define ll  long long
int main(void){
    ll n, k, a, b, c, i, j;
    string s;
    ll r=0;
    cin >> n >> k >> a >> b;
    r = n*k - a*k - b*n + a*b;
    pr(r);
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;

int main(void) {
	int a, b;
	cin >> a >> b;
	if (a + b >= 10) {
		cout << "error";
	}
	else {
		cout << a + b;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int s[100], n, i;
  int max, min, sum, ave;

  while(1) {
    max = 0;
    min = 1000;
    sum = 0;
    scanf("%d", &n);
    if(n == 0)
      break;
    else if(n < 3  || n > 100)
      scanf("%d", &n);
    for(i = 0; i < n; i++) {
      scanf("%d", &s[i]);
      if(s[i] < 0 || s[i] > 1000)
        scanf("%d", &s[i]);
      if(min > s[i])
        min = s[i];
      if(max < s[i])
        max = s[i];
      sum += s[i];
    }
    sum  = sum - max - min;
    ave = sum / (n-2);
    printf("%d\n", ave);
    /*s[i]???????¨?????±???????*/
    /*max??¨min?????????*/
  }

  return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N, count = 0;
    cin >> N;
    for(int i = 1; i <= N; i+=2){
       int K = 0;
        for(int j = 1; j <= N; j++){
            if(i%j == 0)
            K++;
        
        }
        if(K == 8) count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

vector<long long> divisor_enumeration(long long n){
    vector<long long> ret;
    for(long long i=1; i*i<=n; i++){
        if(n%i == 0){
            ret.push_back(i);
            if(i*i != n) ret.push_back(n/i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}

ll N;

signed main(){
    cin >> N;
    auto v = divisor_enumeration(N);
    ll ans = LLONG_MAX;
    rep(i, v.size()){
        ans = min(ans, v[i]+N/v[i]-2);
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define vcout(v) rep(i,v.size()) cout << v[i] << " "; cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}
const ll MOD = 1e9 + 7;

void mainsolve(){

	ll n;
	cin >> n;
	vector<ll> x(n), y(n), h(n);
	rep(i,n) cin >> x[i] >> y[i] >> h[i];

	ll resx=0,resy=0,resh=0;
	rep(i,101){
		rep(j,101){
			// resx,resy固定
			resx = i; resy = j;

			// 一個条件だけ試してresh固定
			rep(k,n){
				ll z = abs(resx - x[k]) + abs(resy - y[k]);
				if(h[k] > 0){
					resh = h[k] + z;
					break;
				}
				else if(z == 1){
					resh = 1;
					break;
				}
			}
			// 全条件に矛盾がないかチェック
			bool isOK = true;
			rep(k,n){
				ll z = abs(resx - x[k]) + abs(resy - y[k]);
				if(h[k] > 0 && resh != h[k] + z) isOK = false;
				else if(h[k] == 0 && resh > z) isOK = false;
				if(!isOK) break;
			}
			if(isOK){
				printf("%lld %lld %lld \n", resx,resy,resh);
				return;
			}
		}
	}


}

int main(){
	
	//ll TC;cin>>TC;rep(I,TC){cout<<"case:"<<I+1<<"---"<<endl; // comment out!
		mainsolve();
	//} // comment out!
	return 0;
}

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

#define F first    
#define S second
#define mp make_pair
#define pii pair<int,int>         
// mikty prikoldar
#define ll long long  
#define pb push_back
#define sz(a) (int)(a.size())
#define Accepted 0
#define endl '\n'
//everything goes according to the plan
#define y1 		 NOT
#define left   NEEDED
#define right  THINGS  
//countdown BEGAN. 10 , 9 , 8 ...
const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4611686018427387903;
const int Sz = 1110111;
// ai dyn dyn dyn dirindai ai dyn dyn dirindai
using namespace std;
// skr skr skr v chernih naikah
inline void Read_rap () {	// smoke weed everyday
  ios_base :: sync_with_stdio(0);
	cin.tie(0);      
}
string a, b;
       
int main() 
{
	Read_rap ();
	cin >> a;

	b = a;
            
  reverse (b.begin(), b.end());

  for (char &c : b) {
  	if (c == 'p')	c = 'q';
  		else
  			if (c == 'q')	c = 'p';
  				else
  					if (c == 'b')	c = 'd';
  						else
  							if (c == 'd')	c = 'b';
 	}
 	cout << (a == b ? "Yes" : "No");



	return Accepted;
}	









// Coded by Z...

Measured memory_bytes: 512
N = int(input())
yesterday = [0, 0, 0]

for i in range(N):
    if i == 0:
        yesterday = list(map(int, input().split()))
    else:
        tmp = [0, 0, 0]
        today = list(map(int, input().split()))

        tmp[0] = max([
            yesterday[1] + today[0],
            yesterday[2] + today[0]
        ])

        tmp[1] = max([
            yesterday[0] + today[1],
            yesterday[2] + today[1]
        ])

        tmp[2] = max([
            yesterday[0] + today[2],
            yesterday[1] + today[2]
        ])

        yesterday = tmp

print(max(yesterday))

Measured memory_bytes: 46680
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner (System.in);
        int A =sc.nextInt();
        int B = sc.nextInt();

        if(B%A==0) System.out.println(A+B);
        else System.out.println(B-A);
    }
}


Measured memory_bytes: 21844
#include <stdio.h>
int main()
{
  int a,b,s,m;
  scanf("%d%d",&a,&b);
  if(a>=1 && a<=100 && b>=1 && b<=100)
    {
    s=a*b;
    m=2*(a+b);
    printf("%d %d\n",s,m);
    }
  return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
  string n; cin>>n;
  int m = n.size();
  ll ans = 0;
  rep(i,m){
    ans += n[i]-'0';
  }
  if(ans==1) ans*=10;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node {
	int key;
	Node *next, *prev;
};

Node *nil;

Node* listSearch(int key){
	Node *cur = nil->next;
	while (cur != nil && cur->key != key){
		cur = cur->next;
	}
	return cur;
}

void init(){
	nil = (Node *)malloc(sizeof(Node));
	nil->next = nil;
	nil->prev = nil;
}
	
void printList(){
	Node *cur = nil->next;
	int isf = 0;
	while(1){
		if (cur == nil) break;
		if (isf++ > 0 ) printf(" ");
		printf("%d", cur->key);
		cur = cur->next;
	}
	printf("\n");
}

void deleteNode(Node *t){
	if(t ==  nil) return;
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t);
}

void deleteFirst(){
	deleteNode(nil->next);
}

void deleteLast(){
	deleteNode(nil->prev);
}

void deleteKey(int key){
	deleteNode(listSearch(key));
}

void insert(int key){
	Node *x = (Node *)malloc(sizeof(Node));
	x->key = key;
	x->next = nil->next;
	nil->next->prev= x;
	x->prev = nil;
	nil->next= x;
}

int main(){
	int key, n, i;
	int size = 0;
	char com[20];
	int np = 0,nd = 0;
	scanf("%d", &n);
	init();
	for(i = 0; i < n; i++){
		scanf("%s%d", com, &key);
		if(com[0] == 'i'){insert(key);np++; size++;}
		else if (com[0] == 'd'){
			if (strlen(com) > 6){
				if (com[6] == 'F') deleteFirst();
				else if (com[6] == 'L') deleteLast();
			} else{
				deleteKey(key); nd++;
			}
			size--;
		}
	}
	printList();
	return 0;
}

Measured memory_bytes: 33912
#include "bits/stdc++.h"

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int>A(N);
	for (int i = 0;i<N;++i) {
		cin >> A[i];
	}
	vector<int>B(N);
	for (int i = 0; i < N; ++i) {
		cin >> B[i];
	}
	vector<int>C(N);
	for (int i = 0; i < N; ++i) {
		cin >> C[i];
	}
	sort(A.begin(), A.end());
	sort(B.begin(), B.end()); 
	sort(C.begin(), C.end());
	long long ans = 0;	
	for (int i = 0; i < N; ++i) {
		long long x = lower_bound(A.begin(), A.end(), B[i])- A.begin();
		long long y = C.end()- lower_bound(C.begin(), C.end(), B[i]+1); 
		//cout << x <<"_"<< y << endl;
		ans += x * y;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4496
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int x = Integer.parseInt(br.readLine().trim());
		System.out.println(""+x*x*x);
	}
}

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

int main() {
    // 例 1: 2 つの整数 a, b を入力し、a と b の最大公約数と最小公倍数を出力する
    int64_t a, b;
    cin >> a >> b;
    cout << a / __gcd(a, b) * b << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
s = [input() for _ in range(n)]
st = dict()
for o in s:
    if "".join(sorted(o)) in st:
        st["".join(sorted(o))] += 1
    else:
        st["".join(sorted(o))] =  1
ans = 0
for i in st.values():
    ans += i*(i-1)//2
print(ans)

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

int main(){
  int a[40]={},n;
  for(int i=0;i<28;i++){
    cin>>n;
    a[n]+=1;
  }
  for(int i=1;i<=30;i++){
    if(a[i]==0){
      cout<<i<<endl;
    }
  }
  return 0;
}

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

int perm[100001];
int clr[100001];

int fnd(int x){
    if(x != clr[x]){
        clr[x] = fnd(clr[x]);
    }
    return clr[x];
}
int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&perm[i]);
        clr[i] = i;
    }
    for(int i=0;i<m;i++){
        int aa, bb;
        scanf("%d%d",&aa,&bb);
        if(fnd(aa) == fnd(bb)) continue;
        clr[clr[bb]] = clr[aa];
    }
    for(int i=1;i<=n;i++) fnd(i);
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(clr[i] == clr[perm[i]]) ans++;
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[]args){
	Scanner sc =new Scanner(System.in);
int a=sc.nextInt();
int b=sc.nextInt();


int x=a/b;
int y=a%b;
double f2;
f2=1.0*a/b;
System.out.println(x+" "+y+" "+String.format("%8f",f2));
sc.close();
	}
}



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

typedef long long ll;
const int INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, p;
	cin>>p>>n;
	vector<int> a(n);

	for (int i = 0; i < n; i++) {
		cin>>a[i];
	}
	int maxGap = 0;
	for (int i = 0; i < n-1; i++) {
		maxGap = max(maxGap, a[i+1]-a[i]);
	}
	maxGap = max(p-a[n-1]+a[0], maxGap);
	cout<<p-maxGap<<'\n';
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long li;
#define minimize(a,b) (a>(b)?a=(b),1:0)
#define maximize(a,b) (a<(b)?a=(b),1:0)
#define ceil(a,b) (((a)+(b)-1)/(b))
#define yn(i) print((i)?"Yes":"No")
#define chmin(a,b) (a>(b)?a=(b),1:0)
#define abs(n) max((n),-(n))
#define dist(a,b) max((a)-(b),(b)-(a))
#define chmax(a,b) (a<(b)?a=(b),1:0)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define MOD 1000000000
#define rep(i,n) for(int i=0;i<(n);i++)

#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

// Container コンテナ型, map以外
template< template<class ...> class Ctn,class T>
std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
  auto itr=v.begin();
  while(itr!=v.end()){
    if(itr!=v.begin())cout << " ";
    cout << *(itr++);
  }
  return os;
}



string key="keyence";

void add(char m,string s,set<string> st){
  int n=s.size();
  rep(i,n){
    if(s[i]!=m) continue;
    string t;
    repa(j,i,n){
      t.push_back(s[j]);
      st.insert(t);
    }
  }
}

int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}

int legal(string s,string t,int k){
  int n=s.size();
  repa(i,k,n){
    if(s[i]!=t[i-k]) return 0;
  }
  return 1;
}

string merge(string s,string t,int k){
  int n=s.size();
  string ret;
  rep(i,k) ret.push_back(s[i]);
  rep(i,n) ret.push_back(t[i]);
  return ret;
}


int main(){
  string t,s; cin >>s >>t;
  int sn=s.size(),tn=t.size(); // tn <= sn
  int ans=sn+tn;
  rep(i,sn-tn+1){
    int cnt=0;
    rep(j,tn){
      if(t[j]!=s[i+j]) cnt++;
    }
    ans=min(ans,cnt);
  }
  print(ans);
}





Measured memory_bytes: 3600
#pragma GCC optimize("O3")
//#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#define io_init cin.tie(0);ios::sync_with_stdio(0);cout<<setprecision(20)
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

typedef complex<double> P;
 
 bool comp_x(const P &a, const P &b) {
     return a.real() < b.real();
 }
 
 bool comp_y(const P &a, const P &b) {
     return a.imag() < b.imag();
 }
 
 double getClosePair(vector<P> &a, int l, int r) {
     if (r - l <= 1) return 1e20;
     int mid = (l + r) / 2;
     double X = a[mid].real();
     double d = min(getClosePair(a, l, mid), getClosePair(a, mid, r));
     inplace_merge(a.begin() + l, a.begin() + mid, a.begin() + r, comp_y);
 
     vector<P> b;
     for (int i = l; i < r; i++) {
         if (abs(a[i].real() - X) >= d) continue;
         for (int j = b.size() - 1; j >= 0; j--) {
             if (abs((a[i] - b[j]).imag()) >= d) break;
             d = min(d, abs(a[i] - b[j]));
         }
         b.push_back(a[i]);
     }
     return d;
 }
 
 int main() {
 
     int N;
     cin >> N;
 
     vector<P> p(N);
     for (int i = 0; i < N; i++) {
         double x, y;
         cin >> x >> y;
         p[i] = P(x, y);
     }
 
     sort(p.begin(), p.end(), comp_x);
 
     double ans = getClosePair(p, 0, N);
     cout << fixed << setprecision(20) << ans << endl;
 
 }


Measured memory_bytes: 7788
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e18 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  int n; cin >> n;
  vector<double> p(n+1);
  vector<vector<double> > dp(n+1, vector<double>(n+1,0));
  rep(i,n) cin >> p[i+1];
  dp[0][0] = 1.0;

  for (int i = 1; i <= n; ++i) {
    double pi = p[i];
    rep(j,n) {
      dp[i][j] += dp[i-1][j] * (1.0 - pi);
      dp[i][j+1] += dp[i-1][j] * pi;
    }
  }

  double ans = 0;
  int h = (n+1) / 2;
  for (int i = h; i <= n; ++i) ans += dp[n][i];
  printf("%.9f\n", ans);
}


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int s; cin >> s;
  int count=0;
  if(s==1 || s==2){ 
    cout << 4 << endl;
    return 0;
  }
  while (true){
    count++;
    if(s==4){ break;}
    if(s%2==1){s=3*s+1;}
    else s=s/2;
  }
  cout << count+3 << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  char in[8][9]={0};
  int i,j;

  while(scanf("%s",in[0])!=EOF){
    int kosu=0;
    char d;
    char x[4]={0};
    char y[4]={0};
    for(i=1;i<8;i++)
	scanf("%s",in[i]);
    for(i=0;i<8;i++){
      for(j=0;j<8;j++){
	if(in[i][j]==49){
	  x[kosu]=j+49;
	  y[kosu]=i+49;
	  kosu++;
	  in[i][j]=0;
	}
      }
    }
    if(x[0]-x[1]==1 && y[0]-y[1]==-1)
      puts("D");
    else if(x[0]-x[2]==1 && y[0]-y[2]==-1)
      puts("G");
    else if(x[0]==x[3])
      puts("B");
    else if(y[0]==y[3])
      puts("C");
    else if(x[0]==x[1])
      puts("F");
    else if(x[0]==x[2])
      puts("A");
    else
      puts("E");
  }
  return 0;
}

Measured memory_bytes: 524
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct city_info {
  int P;
  long long Y;
  int i;
  int x;
};

int main(int argc, char const *argv[]) {
  int N, M;
  cin >> N >> M;

  vector<struct city_info> city(M);

  for (int i = 0; i < M; i++) {
    int p;
    long long y;
    cin >> p >> y;
    city[i].P = p;
    city[i].Y = y;
    city[i].i = i + 1;
    city[i].x = 0;
  }

  sort(city.begin(), city.end(),
       [](struct city_info &lhs, struct city_info &rhs) {
         return lhs.Y < rhs.Y;
       });

  map<int, int> mp;

  for (int i = 0; i < M; i++) {
    city[i].x = mp[city[i].P] + 1;
    mp[city[i].P]++;
  }

  sort(city.begin(), city.end(),
       [](struct city_info &lhs, struct city_info &rhs) {
         return lhs.i < rhs.i;
       });

  for (int i = 0; i < M; i++) {
    cout << setfill('0') << std::right << setw(6) << city[i].P;
    cout << setfill('0') << std::right << setw(6) << city[i].x << "\n";
  }
  return 0;
}


Measured memory_bytes: 8576
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

int main()
{
    int t;
    
    // scanf("%d",&t);
    
    t=1;
    
    while(t--)
    {
        int n,m;
        
        scanf("%d%d",&n,&m);
        
        char A[n][n],B[m][m];
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                scanf(" %c",&A[i][j]);
        }
        
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<m;j++)
                scanf(" %c",&B[i][j]);
        }
        
        bool poss=false;
        
        for(int i=0;i<=n-m;i++)
        {
            for(int j=0;j<=n-m;j++)
            {
                bool match=true;
                
                for(int k=0;k<m;k++)
                {
                    for(int l=0;l<m;l++)
                    {
                        if(A[i+k][j+l]!=B[k][l])
                            match=false;
                    }
                }
                
                if(match)
                    poss=true;
            }
        }
        
        poss?printf("Yes"):printf("No");
    }

    return 0;
}

Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define MOD (long long)(1E9+7)
#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;

int main(){
	int a,b;
	cin >> a >> b;
	cout << (a-1)/(2*b+1) + 1 << endl;
}


Measured memory_bytes: 256
N = int(input())
s = sorted(sorted(input()) for _ in range(N))
ans = 0
cnt = 1
for i in range(1, N):
    if s[i-1] == s[i]:
        cnt += 1
    else:
        if cnt > 1:
            ans += (cnt * (cnt - 1) // 2)
        cnt = 1
if cnt > 1:
    ans += (cnt * (cnt - 1) // 2)
print(ans)

Measured memory_bytes: 24652
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>



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

  string s[3];
  rep(i,3){
    cin>>s[i];
  }

  int t=0;
  while(true){
    //cout<<t<<endl;
    //cout<<s[t]<<endl;
    if(s[t].empty()){
      cout<<(char)('A'+t)<<endl;
      return 0;
    }
    int tt=s[t][0]-'a';
    s[t].erase(s[t].begin());
    t=tt;
  }


}

Measured memory_bytes: 256
formula = input().split(" ")
n = len(formula)

stack = []

for i in range(n):
    if formula[i] == '+':
        operand1 = stack.pop()
        operand2 = stack.pop()
        stack.append(operand2 + operand1)
    elif formula[i] == '-':
        operand1 = stack.pop()
        operand2 = stack.pop()
        stack.append(operand2 - operand1)
    elif formula[i] == '*':
        operand1 = stack.pop()
        operand2 = stack.pop()
        stack.append(operand2 * operand1)
    else:
        stack.append(int(formula[i]))

print(stack.pop())


Measured memory_bytes: 5604
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <utility>
#include <functional>

using namespace std;

int main() {
	int a[3];
	for (int i = 0; i < 3; ++i) {
		cin >> a[i];
	}
	sort(a, a + 3);
	cout << a[0] + a[1] << endl;

	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

type data struct {
	num   int
	count int
}
type datas []data

func (d datas) Len() int           { return len(d) }
func (d datas) Less(i, j int) bool { return d[i].num > d[j].num }
func (d datas) Swap(i, j int)      { d[i], d[j] = d[j], d[i] }

func main() {
	var n int
	fmt.Scan(&n)
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Scan(&tmp)
		m[tmp]++
	}
	li := make(datas, len(m))
	i := 0
	for k, v := range m {
		li[i] = data{k, v}
		i++
	}
	sort.Sort(li)
	long := 0
	ans := 0
	for _, v := range li {
		if v.count >= 4 && long == 0 {
			ans = v.num * v.num
			break
		}
		if v.count >= 2 && long == 0 {
			long = v.num
		} else if v.count >= 2 {
			ans = long * v.num
			break
		}
	}
	fmt.Println(ans)

}


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

int ctoi(char c) {
	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}

int main(){
    string s;
    vector<int> S(4);
    cin >> s;
    for(int i=0;i<4;i++){
        S.at(i) = ctoi(s.at(i));
    }
    if(S.at(0)*10+S.at(1) <= 12 && S.at(0)*10+S.at(1) > 0){
        if(S.at(2)*10+S.at(3) > 12 || S.at(2)*10+S.at(3) == 0){
            cout << "MMYY" << endl;
        }else{
            cout << "AMBIGUOUS" << endl;
        }
    }else{
        if(S.at(2)*10+S.at(3) > 12 || S.at(2)*10+S.at(3) == 0){
            cout << "NA" << endl;
        }else{
            cout << "YYMM" << endl;
        }
    }
    
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
#[allow(dead_code)]
struct Main {}

#[allow(dead_code)]
impl Main {}

fn main() {
    let s = read::<usize>();
    let w = read::<usize>();
    if w >= s {
        println!("unsafe");
    } else {
        println!("safe");
    }
}


Measured memory_bytes: 2164
#include <stdio.h>
#include <string.h>
int main(void)
{
    int a[1100],b,m,n,i,j=0,k=0,l=0,p=0,x=0,y=0,z=0;
    char s[1000],ss[1000],c;

    scanf("%d%d%d",&x,&y,&z);
    scanf("%d",&l);

        if(x<y){
            k=x;
            x=y;
            y=k;
        }
        if(x<z){
            k=x;
            x=z;
            z=k;
        }
        for(i=0; i<l; i++)
            x=x*2;
        printf("%d\n",x+y+z);
    return 0;
}

Measured memory_bytes: 128
n, k = map(int, input().split())
s = input()
l = [0] * (k * 2 + 1)
c = '1'
p = 0
ret = 0
for i in range(len(s)):
    if s[i] != c:
        ret = max(ret, i - l[p])
        l.append(i)
        if c == '1':
            l.pop(0)
            l.pop(0)
        c = s[i]
ret = max(ret, n - l[p])
print(ret)


Measured memory_bytes: 5364