akhauriyash/Code-Regression huggingface dataset:
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 C = sc.nextInt();
		int X = sc.nextInt();
		int counter = 0;

		for (int i = 0; i <= A; i++) {
			for (int j = 0; j <= B; j++) {
				for (int k = 0; k <= C; k++) {
					if (500 * i + 100 * j + 50 * k == X) counter++;
				}
			}
		}
		System.out.println(counter);
	}
}


Measured memory_bytes: 21844
class WeightedUnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.weight = [0 for _ in range(n)]
    def find(self,x):
        root = x
        stack = [root]
        while self.parents[root] != root:
            root = self.parents[root]
            stack.append(root)
        while stack:
            s = stack.pop()
            self.weight[s] += self.weight[self.parents[s]]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y,w):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.weight[xroot] = w-self.weight[x]+self.weight[y]
        else:
            self.parents[yroot] = xroot
            self.weight[yroot] = -w+self.weight[x]-self.weight[y]
            if xrank == yrank:
                self.rank[xroot] += 1

    def diff(self,x,y):
        return self.weight[x]-self.weight[y]

N,Q = map(int,input().split())
uf = WeightedUnionFind(N)
ans = []

for _ in range(Q):
    q = list(map(int,input().split()))
    if q[0] == 0:
        uf.unite(q[1],q[2],q[3])
    else:
        if uf.find(q[1]) == uf.find(q[2]):
            ans.append(uf.diff(q[1],q[2]))
        else:
            ans.append('?')

print('\n'.join(map(str,ans)))


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

using namespace std;
string s;
int l;
int ans, k = 1;

int main () {
	cin >> s;
	l = s.size();
	for (int i = 1; i < l; i++) {
		if (s[i] == s[i - 1]) {
			if (k == 1) {
				if (i != l - 1) {
					k = 2;
					ans++;
					i++;
				}
			}
			else {
				k = 1;
				ans++;
			}		
		}
		else {
			k = 1;
			ans++;
		}
	}
	cout << ans + 1;
	return 0;
}



Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int count = 0;
		if (x >= 500) {
			count += 1000 * (x / 500);
		}
		if (x % 500 >= 5) {
			count += 5 * ((x % 500) / 5);
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 23764
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>


int main(void)
{
	long int i, j;
	long int a, b;
	long int sum;
	long int max;
	long int count;
	long int r;
	long int work;
	
	scanf("%ld%ld", &a, &b);
	
	if(a < b) {
		work = a;
		a = b;
		b = work;
	}
	
	r = a % b;
	while(r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	
	max = b;
	
	//bが最大公約数
	/*
	printf("%ld\n", b);
	
	return 0;
	*/
	
	if(b % 2 == 0) {
		count = 2;
		while(b % 2 == 0) {
			b /= 2;
		}
	} else {
		count = 1;
	}
	/*
	printf("%ld\n", b);
	
	return 0;
	*/
	for(i = 3; i <= sqrt(max); i = i + 2) {
		if(b == 1) {
			break;
		}
		if(b % i == 0) {
			count++;
			while(b % i == 0) {
				b /= i;
			}
		}
	}
	
	if(b != 1) {
		count++;
	}
	
	printf("%ld\n", count);
	
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin >> N;
    string S; cin >> S;
    vector<vector<int>> G(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b; cin >> a >> b; a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    auto recur = [&](auto& recur, int node, int prev) -> tuple<int, int, int> {
        vector<int> nodes, ns, mas, mis;
        for (int next : G[node]) if (next != prev) {
            int n, ma, mi;
            tie(n, ma, mi) = recur(recur, next, node);
            nodes.push_back(next);
            ns.push_back(n), mas.push_back(ma), mis.push_back(mi);
        }
        int n = accumulate(begin(ns), end(ns), 0);
        int ma = accumulate(begin(mas), end(mas), 0);
        int mi = 0;
        for (int i = 0; i < nodes.size(); i++) {
            int ans = mis[i] + ns[i] - (ma + n - mas[i] - ns[i]);
            mi = max(mi, ans);
        }
        ma += n;
        mi = max(ma % 2, mi);
        n += (S[node] == '1');
        return make_tuple(n, ma, mi);
    };
    int ans = 1e9;
    for (int root = 0; root < N; root++) {
        int n, ma, mi; tie(n, ma, mi) = recur(recur, root, -1);
        if (mi == 0) {
            ans = min(ans, ma / 2);
        }
    }
    cout << (ans == 1e9 ? -1 : ans) << endl;
    return 0;
}

Measured memory_bytes: 768
import math


def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    operations = sum(b) - sum(a)
    o1, o2 = 0, 0
    for ai, bi in zip(a, b):
        if ai >= bi:
            o1 += ai - bi
        else:
            if (bi - ai) / 2 % 1 == 0:
                o2 += (bi - ai) // 2
            else:
                o2 += (bi - ai) // 2 + 1

    print("Yes" if o1 <= operations and o2 <= operations else "No")


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 4596
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int h = sc.nextInt();
            int w = sc.nextInt();

            if ((h!=0)&&(w!=0))
            {
                for (int i=1; i<=h; i++) {
                    for (int j=1; j<=w; j++) {
                        if (j!=w) {
                            if (i%2!=0 && j%2!=0)
                                System.out.printf("#");
                            else if (i%2!=0 && j%2==0)
                                System.out.printf(".");
                            else if (i%2==0 && j%2!=0)
                                System.out.printf(".");
                            else if (i%2==0 && j%2==0)
                                System.out.printf("#");
                        }
                        else
                        if (i%2!=0 && j%2!=0)
                            System.out.printf("#\n");
                        else if (i%2!=0 && j%2==0)
                            System.out.printf(".\n");
                        else if (i%2==0 && j%2!=0)
                            System.out.printf(".\n");
                        else if (i%2==0 && j%2==0)
                            System.out.printf("#\n");

                    }
                }
            }
            else
                break;

            System.out.println();
        }
    }

}



Measured memory_bytes: 59920
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;
long long int mod = 1e9 + 7;
template <class T>
void inputV(vector<T> &x, int n){
  for(int i=0; i<n; i++) cin >> x[i];
}

const int maxsize = 500001;
long long int fac[maxsize], finv[maxsize], inv[maxsize];
void init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i=2; i<maxsize; i++){
    fac[i] = fac[i-1] * i % mod;
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}

long long int nCk(int n, int k, int mod){
  if( n < k ) return 0;
  if(n<0 || k<0) return 0;
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

int main() {
  int n, m;
  cin >> n >> m;
  map<int, int> mp;
  int mm = sqrt(m) + 1;
  for(int i=2; i<=mm; i++) {
    while(m%i==0) {
      m /= i;
      mp[i]++;
    }
  }
  if(m != 1) mp[m]++;
  init();
  long long int ans = 1;
  for(auto i = mp.begin(); i!=mp.end(); i++){
    int tmp = i->second;
    ans *= nCk(tmp + n - 1, tmp, mod);
    ans %= mod;
  }
  cout << ans << endl;

  return 0;
}

//


Measured memory_bytes: 11904
#include <iostream>

using namespace std;

int main(int argc, char const* argv[])
{
	double a;
	double sum;

	while( cin >> a ){
		sum = a;
		for( int i = 2;i <= 10;i++ ){
			if( i % 2 ){
				a /= 3;
			} else {
				a *= 2;
			}
			sum += a;
		}

		printf("%.8f\n", sum );
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>

using namespace std;

int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n,m;
struct DT
 {

    int x;
	int y;
	int step;
};
char map[100][100];
bool vis[100][100];
queue<DT>q;
int bfs(int qx,int qy)
{
	memset(vis,0,sizeof(vis));
	vis[qx][qy]=1;
	DT kai,xia,xian;
	kai.x=qx;
	kai.y=qy;
	kai.step=1;
	q.push(kai);
	while(!q.empty())
	{
		xian=q.front();
		q.pop();
		if(xian.x==(n-1)&&xian.y==(m-1))
			return xian.step;
	         for(int i=0;i<4;i++)
	        {
	        	xia.x=xian.x+dir[i][0];
	        	xia.y=xian.y+dir[i][1];
	        	if(xia.x<0||xia.y<0||xia.x>=n||xia.y>=m||vis[xia.x][xia.y]||map[xia.x][xia.y]=='#')
	        	continue;
					vis[xia.x][xia.y]=1;
					xia.step=xian.step+1;
	        	    q.push(xia);	
				}
	}
	return -1;
}
int main()
{
	int ans,num;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		num=0;
		
		for(int i=0;i<n;i++)
		{
			scanf("%s",&map[i]);
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map[i][j]=='.')
				num++;
			}
		}
		ans=bfs (0,0);
		if(ans==-1)
		printf("-1\n");
		else
		printf("%d\n",num-ans);
		}
		return 0;
	}

Measured memory_bytes: 256
/**
 *    author:  nasimnoob
**/

#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<math.h>
using namespace std;

typedef long long int                        ll;
typedef unsigned long long int              ull;
typedef long double                          ld;


#define      PI                         3.141592654


int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int d = (a+b)*(c/2);
    cout<<d<<endl;
    //cout<<"March 29, 2013 Friday"<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

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

using namespace std;

const int INF = 1 << 30;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100;

struct Node {
	int key;
	Node *parent, *left, *right;
};
Node *root;

void insertKey(int k) {
	Node *z = (Node*)malloc(sizeof(Node));
	z->key = k;
	z->left = NULL;
	z->right = NULL;
	Node *y = NULL;
	Node *x = root;
	while (x) {
		y = x;
		if (z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	z->parent = y;

	if (y == NULL)
		root = z;
	else if (z->key < y->key)
		y->left = z;
	else
		y->right = z;
}


void inParse(Node *n) {
	if (n == NULL) return;
	inParse(n->left);
	cout << ' ' << n->key;
	inParse(n->right);
}

void preParse(Node *n) {
	if (n == NULL) return;
	cout << ' ' << n->key;
	preParse(n->left);
	preParse(n->right);
}	

void printKey() {
	inParse(root);
	cout << endl;
	preParse(root);
	cout << endl;
}

int main() {
	int n; cin >> n;
	string com;
	rep(i, n) {
		cin >> com;
		if (com == "insert") {
			int k; cin >> k;
			insertKey(k);
		}
		else if (com == "print")
			printKey();
	}
}



Measured memory_bytes: 26592
import java.util.Scanner;
 
public class Main {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
     
        //String[] ALFA = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};
        //String[] alfa = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
        
        String S = sc.nextLine();
        
        //Sに大文字が含まれるとき
        if(S.toUpperCase() == S) { 
          System.out.println("A");
        } else {
          System.out.println("a");
        }
   }
}

Measured memory_bytes: 35664
n, k = map(int, input().split())
S = list(input())

if "0" not in S:
    print(n)
    exit()

# 1の個数、0の個数、1の個数、、、
cnt = []

# 先頭が0なら1が0個とみなす
if S[0] == "0":
    cnt.append(0)

# 個数勘定
i = 0
while i < n:
    j = i
    while j < n and S[i] == S[j]:
        j += 1
    cnt.append(j-i)
    i = j

# 最後尾が0なら1が0個とみなす
if S[-1] == "0":
    cnt.append(0)

# cnt の累積和
cumCnt = [0]
for c in cnt:
    cumCnt.append(cumCnt[-1] + c)

# print(cnt)
# print(cumCnt)

lenCnt = len(cnt)
lenCumCnt = len(cumCnt)
ans = 0

for left in range(0, lenCumCnt, 2):
    right = min(left + 2*k+1, lenCumCnt-1)
    ans = max(ans, cumCnt[right] - cumCnt[left])
print(ans)

Measured memory_bytes: 14348
package main

import (
	"fmt"
	"strconv"
)

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

	ss := make([]string, n)
	ns := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&ss[i])
		ns[i], _ = strconv.Atoi(string(ss[i][1]))
	}

	ss2 := make([]string, n)
	ns2 := make([]int, n)
	copy(ss2, ss)
	copy(ns2, ns)

	for i := 0; i < n; i++ {
		for j := n - 1; j >= i+1; j-- {
			if ns[j] < ns[j-1] {
				ns[j-1], ns[j] = ns[j], ns[j-1]
				ss[j-1], ss[j] = ss[j], ss[j-1]
			}
		}
	}

	for i := 0; i < n; i++ {
		mini := i
		for j := i; j < n; j++ {
			if ns2[j] < ns2[mini] {
				mini = j
			}
		}
		if mini != i {
			ns2[mini], ns2[i] = ns2[i], ns2[mini]
			ss2[mini], ss2[i] = ss2[i], ss2[mini]
		}
	}

	for i := range ss {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(ss[i])
	}
	fmt.Println()
	fmt.Println("Stable")

	stable := true
	for i := range ss2 {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(ss2[i])

		if ss2[i] != ss[i] {
			stable = false
		}
	}
	fmt.Println()

	if stable {
		fmt.Println("Stable")
	} else {
		fmt.Println("Not stable")
	}
}



Measured memory_bytes: 1128
#include<iostream>
using namespace std;
int main(){
  int c[4][4];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin >> c[j][i];
    }
  }
  for(int i=0;i<3;i++){
    c[3][i]=c[0][i];
    c[i][3]=c[i][0];
  }
  c[3][3]=c[0][0];
  int cnt=0;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(c[i][j]-c[i+1][j]!=c[i][j+1]-c[i+1][j+1]) break;
      else cnt++;
    }
  }
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(c[j][i]-c[j+1][i]!=c[j][i+1]-c[j+1][i+1]) break;
      else cnt++;
    }
  }
   if(cnt==18) cout << "Yes" << "\n";
  else cout << "No" << "\n";
  
  return 0;
}


Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

std::string N;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;

	auto s = N;
	std::reverse(s.begin(), s.end());
	out << (s == N ? "Yes" : "No") << endl;

	return 0;
}
#endif

Measured memory_bytes: 888
#include <iostream>
#include <string>

using namespace std;

char cmap[100][100];
int h,w;
int vx[] = {0, -1, 1, 0}, vy[] = {-1, 0, 0, 1};

void search(int y, int x, char ch){
	if(y < 0 || h <= y || x < 0 || w <= x || cmap[y][x] != ch) return;
	cmap[y][x] = '\0';
	for (int i = 0; i < 4; i++) {
		search(y + vy[i], x + vx[i], ch);
	}
	return;
}

int main(){
	int c;
	string buf;
	while(cin >> h >> w,h != 0, w != 0){
		c = 0;
		for (int i = 0; i < h; i++) {
			cin >> buf;
			for (int j = 0; j < w; j++) {
				cmap[i][j] = buf[j];
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (cmap[i][j] != '\0') {
					search(i, j, cmap[i][j]);
					++c;				
				}
			}
		}
		cout << c << endl;
	}
	return 0;
}

Measured memory_bytes: 1680
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ 110000
vector<int> prime;
bool unprime[SZ];
int main(){
  for(int i = 2; i < SZ; i++){
    if(!unprime[i]){
      for(int k = i*2; k < SZ; k+=i){
        unprime[k] = true;
      }
      prime.push_back(i);
    }
  }
  int N,P;
  while(cin>>N>>P){
    if(N==-1) break;
    vector<int>::iterator it = upper_bound(prime.begin(),prime.end(), N);
    vector<int> subprime;
    for(int i = 0; i<=P; i++){
      subprime.push_back(*it++);
    }
    vector<int> sumof2;
    REP(i,subprime.size())FOR(j,i,subprime.size())
      sumof2.push_back(subprime[i]+subprime[j]);
    sort(sumof2.begin(),sumof2.end());
    cout<<sumof2[P-1]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>

int main(void) {
	// your code goes here]
	int a;
	int b;
	scanf("%d",&a);
	scanf("%d",&b);
	if(a == b){
		printf("%d",a);
		}else if(a>b){
			printf("%d",a-1);
		}else{
			printf("%d",a);
		}
	return 0;
}

Measured memory_bytes: 128
a,b,c,d = gets.chomp.split("").map(&:to_i)
arr = ""
all = 0
["+","-"].each do |i|
    ["+","-"].each do |o|
        ["+","-"].each do |l|
        arr = "#{a}"+ "," + i + "#{b}"+ "," + o + "#{c}"+ "," + l + "#{d}"
        all += arr.split(",").map(&:to_i).inject(:+)
            if all == 7
                puts "#{a}" + i + "#{b}"+ o + "#{c}"+ l + "#{d}" + "=7"
                exit
            end
            all = 0
        end        
    end
end

Measured memory_bytes: 14348
n=int(input())
a=list(map(int,input().split()))
p=[0,0,0]
mod=10**9+7
r=1
for i in range(n):
  c=0
  for j in range(3):
    if p[j]==a[i]:
      if c==0:
        p[j]+=1
      c+=1
  r=(r*c)%mod
print(r)

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < n; i++)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll D, G;
    cin >> D >> G;

    vector<ll> p(D), c(D);
    rep (i, D) {
        cin >> p[i] >> c[i];
    }

    ll ans = INF;
    for (ll bit = 0; bit < (1<<D); bit++) {
        ll point = 0;
        ll count = 0;
        vector<ll> index;
        vector<ll> memo;

        for (ll i = 0; i < D; i++) {
            if (bit & (1<<i)) {
                point += (i+1)*100*p[i] + c[i]; 
                count += p[i];
            }
        }

        if (point >= G) {
            ans = min(ans, count);
        } else {
            for (ll i = D-1; i >= 0; i--) {
                if (bit & (1 << i)) {
                    continue;
                }
                for (ll j = 0; j < p[i]; j++) {
                    if (point >= G) {
                        break;
                    }
                    point += (i+1)*100;
                    count++;
                }
            }
            ans = min(ans, count);
        }
    }

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

Measured memory_bytes: 256
n = int(input())

a = list(map(int, input().split()))
set_a = set(a)
nums = {}
cnt = 0

for i in range(n):
    nums[a[i]] = nums.get(a[i], 0) + 1


for i in set_a:
    if nums[i] % 2 == 0:
        cnt += 1
    elif nums[i] != 1:
        cnt += 2

print(len(set_a) - cnt%2)

Measured memory_bytes: 23676
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<stack>
#include<cstring>
#include<string.h>
#include<cmath>
using namespace std;
typedef long long ll;

int main(){
  int n;
  stack<int>s;
  queue<int>q;

  scanf("%d",&n);
  for(int i=0;i<n;i++){
    int a;
    scanf("%d",&a);
    if((n+i)%2==0) q.push(a);
    else s.push(a);
  }

  while(!s.empty()){
    printf("%d ",s.top());
    s.pop();
  }
  while(!q.empty()){
    printf("%d",q.front());
    q.pop();
    if(q.empty()) printf("\n");
    else printf(" ");
  }
  
  return 0;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
  ll n, k;
  cin >> n >> k;
  if (n == 1) {
    cout << k << endl;
    return;
  }
  ll ans = k * pow((k - 1), (n - 1));
  cout << ans << endl;
}

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

Measured memory_bytes: 4020
from datetime import datetime

S = input()
S = list(map(int, S.split('/')))

datetime_20190430 = datetime(2019, 4, 30)
datetime_S = datetime(S[0], S[1], S[2])

answer = 'Heisei' if datetime_S <= datetime_20190430 else 'TBD'

print(answer)


Measured memory_bytes: 3440
#include<stdio.h>
int main(){
    int i, j, n, x, k, ans;
    
    while(true){
        scanf("%d%d", &n, &x);
        if(n==0 && x==0) break;
        ans=0;
        for(i=1;i<=n-2;i++){
            for(j=i+1;j<=n-1;j++){
                for(k=j+1;k<=n;k++){
                   // printf("%d %d %d\n", i, j, k);
                    if(i+j+k==x) ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    
}



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

int main(){
  int i,j,cnt=0;
  int h,w;
  cin>>h>>w;
  ll s[3];
  if(h%3==0 || w%3==0){
    cout<<0<<endl;
    return 0;
  }
  cnt=min(h,w);
  cnt=min(cnt,max((int)round(abs((h+1)/3*w-(h-(h+1)/3)*(w/2))),(int)round(abs((h+1)/3*w-(h-(h+1)/3)*((w+1)/2)))));
  cnt=min(cnt,max((int)round(abs((w+1)/3*h-(w-(w+1)/3)*(h/2))),(int)round(abs((w+1)/3*h-(w-(w+1)/3)*((h+1)/2)))));
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
#define ll long long

const int mod = 1e9+7, maxn = 1e5+10;
int N, M, K;
double p[3030], dp[3030][2];

int main()
{
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%lf", &p[i]);
    dp[0][0] = dp[0][1] = 1;
    int x = 0;
    for(int i = 1; i <= N; i++) {
        x ^= 1;
        for(int j = i; j > 0; j--)
            dp[j][x] = dp[j-1][x^1]*p[i] + dp[j][x^1]*(1-p[i]);
        dp[0][x] = dp[0][x^1]*(1-p[i]);
    }
//    x ^= 1;
    double sum = 0;
    for(int i = N; i > -1 && i*2 > N; i--)
        sum += dp[i][x];
    printf("%.10lf\n", sum);
    return 0;
}


Measured memory_bytes: 3260
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int n = s.size() - 1;
    vector<int> o1 = {2, 4, 5, 7, 9},o2={0,1,6,8},o3={3};

    for(auto x:o1)
    if(s[n]-'0'==x)
    {
        cout << "hon";
        return 0;
    }

    for (auto x : o2)
        if (s[n] - '0' == x)
        {
            cout << "pon";
            return 0;
        }

    cout << "bon";
    return 0;
}

Measured memory_bytes: 3628
import sys
sys.setrecursionlimit(2000000)

n=int(input())
a=[]*n
a=list(map(int,input().split()))
num=1
bre=0
no=True
def search(pos):
    spos=pos
    global num,bre,no
    end=True
    while end:
        if spos >= n:
            break
        if a[spos]==num:
            no=False
            num+=1
            search(spos+1)
            end=False
        else:
            spos+=1
            bre+=1

search(0)
if no:
    bre=-1
print(bre)

Measured memory_bytes: 185384
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 2000000
#define INFTY (1<<30)

int H, A[MAX+1];
void maxHeapify(int i) {
	int l, r, largest;
	l = 2 * i;
	r = 2 * i + 1;

	if(l <= H && A[l] > A[i])
		largest = l;
	else
		largest = i;
	if(r <= H && A[r] > A[largest])
		largest = r;

	if(largest != i){
		swap(A[i], A[largest]);
		maxHeapify(largest);
	}
}

int extract() {
	int maxv;
	if (H< 1 ) return - INFTY;
	maxv = A[1];
	A[1] = A[H--];
	maxHeapify(1);
	return maxv;
}

void increaseKey(int i, int key) {
	if ( key <A[i] ) return;
	A[i] = key;
	while (i > 1 && A[i / 2] <A[i] ) {
		swap(A[i], A[i / 2]);
		i = i / 2;
	}
}

void insert(int key) {
	H++;
	A[H] = - INFTY;
	increaseKey(H, key);
}

int main() {
	int key;
	char com[10];

	while ( 1 ) {
		scanf("%s", com);
		if ( com[0] == 'e' && com[1] == 'n' ) break;
		if ( com[0] == 'i' ) {
			scanf("%d", &key);
			insert(key);
		} else {
			printf("%d\n", extract());
		}
	}

	return 0;
}


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

#define inf (1<<30)-1
#define INF (1LL<<62)-1
#define MOD 1000000007LL
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define PI acos(-1)
#define MEM(x,y) memset(x,y,sizeof (x))
#define debug cout<<"A"<<'\n'
#define REP(i,a,b) for (int i=(a); i<=(b); i++)
#define PER(i,a,b) for (int i=(a); i>=(b); i--)
#define REPL(i,a,b) for (LL i=(a); i<=(b); i++)
#define PERL(i,a,b) for (LL i=(a); i>=(b); i--)
#define print(x) cout<<x<<'\n'
#define dprint(a,x) cout<<setprecision(x)<<fixed<<a<<'\n'
#define itrALL(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int>PII;
typedef pair<LL,LL>PLL;
typedef set<int> SI;
typedef set<LL> SL;
typedef set<string> SS;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef map<int,int> MII;
typedef map<LL,LL> MLL;
typedef queue<int> QI;

/* Direction Array */

// int fx[]={1,-1,0,0};
// int fy[]={0,0,1,-1};
// int fx[]={0,0,1,-1,-1,1,-1,1};
// int fy[]={-1,1,0,0,1,1,-1,-1};

template <class T> inline T bigmod(T p,T e,T M)
{
    T ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}

template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T> inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
template <class T, class X> inline bool getbit(T a, X i) { T t=1; return ((a&(t<<i))>0);}
template <class T, class X> inline T setbit(T a, X i) { T t=1;return (a|(t<<i)); }
template <class T, class X> inline T resetbit(T a, X i) { T t=1;return (a&(~(t<<i)));}

inline LL power(LL a, LL b)
{
	LL multiply=1;
	REP(i,1,b)
	{
		multiply*=a;
	}
	return multiply;
}
inline LL ABS(LL a){return (a>=0)?a:-a;}

/*end of header*/
int main()
{
    //freopen("input_file_name.in","r",stdin);
    //freopen("output_file_name.out","w",stdout);
    string s;
    cin>>s;
    int N=0,S=0,E=0,W=0;
    REP(i,0,s.size()-1)
    {
        if(s[i]=='S')S=1;
        else if(s[i]=='E')E=1;
        else if(s[i]=='W')W=1;
        else N=1;
    }
    if(N^S==0 && E^W==0)print("Yes");
    else print("No");
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,k;
  cin >> n >> k;
  double ans = 0.0;
  if(n>k) ans += (double)(n-k)/(double)n;
  for(int i=1;i<=min(n,k);i++){
    ans += 1.0/((double)n*pow(2,ceil(log2((double)k/(double)i))));
  }
  cout << fixed ;
  cout << setprecision(9) << ans <<endl;
}
              
       

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  int n;cin>>n;
  map<string,int> m;
  rep(i,n){
    string s;cin>>s;
    m[s]++;
  }
  for(string s:{"AC","WA","TLE","RE"}){
    cout<<s<<" x "<<m[s]<<endl;
  }
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	ll b[100010];
	vector<ll>a;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		a.push_back(now);
	}
	sort(a.begin(),a.end());
	b[0]=a[0];
	for(ll j=1;j<n;j++){
		b[j]=b[j-1]+a[j];
	}
	ll ans=1;
	for(ll i=1;i<n;i++){
		if(b[i-1]*2>=a[i]){
			ans++;
		}
		else{
			ans=1;
		}
	}
	cout <<ans;
	// your code goes here
	return 0;
}

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

#define repo(i,n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;

int main(){
    double L;
    cin >> L;
//     double a = 20000.0;
//     L *= a;
    double ans = L/3.0;
//     ans /= a;
//     cout << ans*ans*ans << endl;
    double aaa = ans*ans*ans;
//     printf("%.15lf", aaa);
//     
//
//     printf("%0.lf",ans);

    cout << std::fixed << std::setprecision(15) << aaa << endl;
// printf("%.16f", aaa);
    return 0;
}



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

int main(){
  string s;
  cin>>s;
  int f=-1,e=-1;
  for(int i=0;i<s.size();i++){
    if(s[i]=='A' && f==-1){
      f=i;
    }
    if(s[i]=='Z' && f!=-1){
      e=i;
    }
  }
  cout<<e-f+1<<endl;
}

Measured memory_bytes: 640
// B.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const LL MOD = 1000000007;

struct modll {
	long long x;
	modll() { }
	modll(long long _x) : x(_x) { }
	operator int() const { return (int)x; }
	modll operator+(const modll& r) { return (x + r.x) % MOD; }
	modll operator+=(const modll& r) { return x = (x + r.x) % MOD; }
	modll operator-(const modll& r) { return (x + MOD - r.x) % MOD; }
	modll operator-=(const modll& r) { return x = (x + MOD - r.x) % MOD; }
	modll operator*(const modll& r) { return (x * r.x) % MOD; }
	modll operator*(int r) { return (x * r) % MOD; }
	modll operator*=(const modll& r) { return x = (x * r.x) % MOD; }
	static modll modinv(int a) { return modpow(a, MOD - 2); }
	static modll modpow(int a, int b) {
		modll x = a, r = 1;
		for (; b; b >>= 1, x *= x) if (b & 1) r *= x;
		return r;
	}
};

int main(int argc, char* argv[]) {
#ifdef _MSC_VER
	while (true)
#endif
	{
		int n = -1;
		cin >> n;
		if (n < 0) return 0;
		vector<int> x(n);
		for (int i = 0; i < n; ++i) {
			cin >> x[i];
		}
		modll fact = 1, prev = 0, ans = 0;
		for (int i = 1; i < n; ++i) {
			fact *= i;
		}
		for (int i = 0; i < n - 1; ++i) {
			prev += fact * modll::modinv(i + 1);
			ans += prev * (x[i + 1] - x[i]);
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;
     
class Point
{
public:
    int x, y;
    bool operator<(const Point& p) const{
        return y < p.y;
    }
};
     
int main()
{
    int n, k;
    cin >> n >> k;
    vector<Point> p(n);
    for(int i=0; i<n; ++i)
        cin >> p[i].x >> p[i].y;
    sort(p.begin(), p.end());
     
    long long ans = LLONG_MAX;
    for(int i=0; i<n; ++i){
        for(int j=0; j<i; ++j){
            int x1 = p[i].x;
            int x2 = p[j].x;
            if(x2 < x1)
                swap(x1, x2);
     
            int yMinDiff = INT_MAX;
            int b = 0;
            int cnt = 0;
            for(int a=0; a<n; ++a){
                if(x1 <= p[a].x && p[a].x <= x2)
                    ++ cnt;
                for(;;){
                    if(x1 <= p[b].x && p[b].x <= x2){
                        if(cnt <= k)
                            break;
                        -- cnt;
                    }
                    ++ b;
                }
                if(cnt >= k)
                    yMinDiff = min(yMinDiff, p[a].y - p[b].y);
            }
     
            if(yMinDiff < INT_MAX)
                ans = min(ans, (x2 - x1) * (long long) yMinDiff);
        }
    }
    cout << ans << endl;
     
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string.h>
#include <string>
#include <cstring>
using namespace std;



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

	if(N/10==9||N%10==9){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	

	return 0;
}

Measured memory_bytes: 256
#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 n;
  cin >> n;
  vector<int>a(n);
  rep(i,n){
    cin >> a[i];
    a[i]--;
  }
  int l = 0;
  rep(i,n){
    int t = l;
    if(a[l] == 1){
      cout << i+1 << endl;
      return 0;
    }
    l = a[t];
  }
  cout << -1 << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    int N, Y;
    std::cin >> N >> Y;
    int k = 0;
    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= N - i; j++)
        {
            k = N - i - j;
            if (1000 * k == Y - 10000 * i - 5000 * j)
            {
                std::cout << i << ' ' << j << ' ' << k << std::endl;
                return 0;
            }
        }
    }

    std::cout << -1 << ' ' << -1 << ' ' << -1 << std::endl;
    return 0;
}


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

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 100;

const ll inf = 1e18 + 100;

int n;

ll a[maxn], b[maxn], s[maxn];

int main()
{
    #ifdef ONPC
    ifstream cin("a.in");
    ofstream cout("a.out");
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    ll sum = 0;
    b[0] = a[0];
    sum = a[0];
    for (int i = 1; i < n; i++){
        b[i] = a[i] - 2 * sum;
        sum += a[i];
    }
    s[n] = -inf;
    s[n - 1] = b[n - 1];
    for (int i = n - 2; i >= 0; i--)
        s[i] = max(s[i + 1], b[i]);
    int answer = 0;
    ll mx = -inf;
    for (int i = 0; i < n; i++){
        if (mx <= 2 * a[i] && s[i + 1] <= 0)
            answer++;
        mx = max(mx, b[i]);
    }
    cout << answer;
}


Measured memory_bytes: 3584
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
L = [-1 for _ in range(N)]
R = [-1 for _ in range(N)]

for i in range(N):
  L[i] = A[i] - i-1
  R[i] = A[i] + i+1

# L = -R となる物のうち、i>jになりゃいいんだけど、最後にいくつかで破れば良い気がす
# i > 0 なので、自分自身を２回選んでL＝Rみたいにはならない・・・？

LC = Counter(L)
RC = Counter(R)

ans = 0
for k,v in LC.items():
  if (-1) * k in RC:
    ans += v * RC[(-1)*k]
    #print(k,v,(-1)*k,RC[(-1)*k], ans)
print(ans)



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

using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define REP(i, n) for(int i=1;i<=n;i++)
typedef long long ll;

int main() {
	ll x;
	cin >> x;
	ll a = x / 11;
	ll b = x % 11;
	ll ans;
	if (b == 0) {
		ans = 2 * a;
		cout << ans << endl;
	} else if (0 < b && b <= 6) {
		ans = 2 * a + 1;
		cout << ans << endl;
	} else {
		ans = 2 * a + 2;
		cout << ans << endl;
	}
	
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long N,K;
pair<long long,long long>item[101];
long long DP[100001][101];
bool computed[100001][101];
long long dp(long long index,long long capacity)
{
	if(index==N)
	{
		return 0;
	}
	else if(computed[capacity][index])return DP[capacity][index];
	else
	{
		long long best=dp(index+1,capacity);
		if(capacity>=item[index].first)
		{
			best=max(best,item[index].second+dp(index+1,capacity-item[index].first));
		}
		computed[capacity][index]=true;
		return DP[capacity][index]=best;
	}
}

int main()
{
	cin>>N>>K;
	for(int j=0;j<100001;j++)
	for(int i=0;i<101;i++)computed[j][i]=false;
	for(int i=0;i<N;i++)
	{
		cin>>item[i].first>>item[i].second;
	}
	cout<<dp(0,K)<<endl;
}

Measured memory_bytes: 88704
n, m = map(int, input().split())

matrix = [[0 for i in range(m)] for j in range(n)]
vector = [0 for i in range(m)]

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

for i in range(m):
    vector[i] = int(input())

for i in range(n):
    sum = 0
    for j in range(m):
        sum += matrix[i][j] * vector[j]
    print(sum)



Measured memory_bytes: 6020
#include <iostream>
#define _USE_MATH_DEFINES
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
    int n, s[1000];
    double sum, m, a;

    while (true) {
        cin >> n;

        if (n == 0) {
            return 0;
        }

        sum = a = 0;

        for (int i = 0; i < n; i++) {
            cin >> s[i];
            sum += s[i];
        }

        m = sum / n;

        for (int i = 0; i < n; i++) {
            a += (s[i] - m) * (s[i] - m);
        }
        a = sqrt(a / n);

        cout << fixed << setprecision(8) << a << endl;
    }
}

Measured memory_bytes: 1236
n, m = map(int, input().split())
a = [" "] * n
for i in range(n):
    a[i] = input()
b = [" "] * m
for i in range(m):
    b[i] = input()

flag = False
for i in range(n-m+1):
    if flag: break
    for j in range(n-m+1):
        suba = a[i:i+m]
        for k in range(len(suba)):
            suba[k] = suba[k][j:j+m]
        if suba == b:
            flag = True
            break

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int h, w;
    cin >> h >> w;

    int G[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            int x;
            cin >> x;
            G[i][j] = x;
        }
    }

    int maxwidth = 0;
    int dp[h][w];
    // fill(&dp[0][0], &dp[h-1][w-1] + 1, 0);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            dp[i][j] = (G[i][j] + 1) % 2;
            maxwidth |= dp[i][j];
        }
    }

    for (int i = 1; i < h; ++i) {
        for (int j = 1; j < w; ++j) {
            if (G[i][j]) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                maxwidth = max(maxwidth, dp[i][j]);
            }
        }
    }
    cout << maxwidth * maxwidth << endl;

    return 0;
}

Measured memory_bytes: 18376
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
count = 0
for i in range(n):
    A = a[i]-1
    count += b[A]
    try:
        if a[i]+1==a[i+1]:
            count += c[A]
    except:
        continue
print(count)

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

#pragma GCC optimize "O3"
#define rep(i,a,n) for(int i=a; i<n; i++)
typedef long long ll;
typedef pair<int,int> P;
const ll MOD = (int)1e9+7;
const ll INF = MOD*MOD;
const ll powll = 1LL<<1;

int main(void){
   int n,y; cin >> n >> y;
   int x = -1,xx= -1, z = -1;
   rep(i,0,n+1){
       rep(j,0,n+1){
           int nn = n-i-j;
           if(nn >= 0 && nn <= n && 1000*i+5000*j+10000*nn == y){
               x = i;
               xx = j;
               z = nn;
           }
       }
   }
   printf("%d %d %d\n", z,xx,x);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound
 
int main(){
  int N;
  cin>>N;
  VI X(N);
  rep(i,N) if((i+1)%3 and (i+1)%5) X[i]=i+1;
  ll ans=0;
  rep(i,N) ans+=X[i];
  cout<<ans<<endl;
}



Measured memory_bytes: 7088
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define lamsort(v,p) sort(v.begin(),v.end(),[](p a, p b){return a.num < b.num;});
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s; cin >> s;
    int k; cin >> k;
    vector<int> v;
    int cnt = 1;
    REP(i,1,s.size()) {
        if(s[i]==s[i-1]) cnt++;
        else {
            v.push_back(cnt);
            cnt = 1;
        }
    }
    if(cnt) v.push_back(cnt);

    ll ans = 0;
    if((int)v.size()==1) {
        int a = v[0]/2;
        if(v[0]%2!=0){
            if(k%2==0) {
                ans += (ll)(k/2)*a;
                ans += (ll)(k/2)*(a+1);
            }
            else {
                ans += (ll)(k/2+1)*a;
                ans += (ll)(k/2)*(a+1);
            }
        }
        else ans = (ll)a*k;
    }
    else if(s[0]!=s[s.size()-1]) {
        rep(i,v.size()) {
            ans += v[i]/2;
        }
        ans = (ll)ans*k;
    }
    else {
        rep(i,v.size()) {
            ans += v[i]/2;
        }
        if(v[0]%2!=0 && v[v.size()-1]%2!=0) {
            ans++;
        }
        ans = (ll)ans*k;
        if(v[0]%2!=0 && v[v.size()-1]%2!=0) ans--;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <algorithm>

using namespace std;
using ll = long long;
using pint = pair<int, int>;

int main() {
	int S, W;
	cin >> S >> W;

	cout << ((S <= W) ? "unsafe" : "safe") << endl;
	return 0;
}


Measured memory_bytes: 3608
import java.util.*;


public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		List<Integer> list = new ArrayList<Integer>();
		
	    int a = sc.nextInt();
	    int b = sc.nextInt();
	    int c = sc.nextInt();
		
	    list.add(a);
	    list.add(b);
	    list.add(c);

	    Collections.sort(list);

	    int ans1 = list.get(0);
	    int ans2 = list.get(1);
	    int ans3 = list.get(2);

	    System.out.println(ans1 + " " + ans2 + " " + ans3);
	}

}

Measured memory_bytes: 17304
p = $<.map{|e| e.split(",").map(&:to_f) }
sum = 0
c = p.pop
p.each_cons(2){ |a,b|
    sum += 0.5 * (a[0] * b[1] + b[0] * c[1] + c[0] * a[1] - b[0] * a[1] - c[0] * b[1] - a[0] * c[1])
}
puts sprintf("%.6f" , sum.abs )


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	ll m = 0;
	ll s = 0;
	for (int i = 0 ; i < n ; i++) {
		ll t;
		cin >> t;
		m = max(m, t);
		s += m - t;
	}
	cout << s << "\n";

	return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
const int ma=1e6;
int a[ma],t[ma];
string s;
int ne(int p2,int p,int t)
{
    if(p)t^=1;
    if(t==0)return p2;
    return p2^1;
}
main()
{
    int n;
    cin>>n;
    cin>>s;
    rep(i,0,n)
    {
        if(s[i]=='o')t[i]=0;
        else t[i]=1;
    }
    rep(i1,0,2)
    {
        rep(i2,0,2)
        {
            a[0]=i1,a[1]=i2;
            rep(i,2,n)a[i]=ne(a[i-2],a[i-1],t[i-1]);
            if(ne(a[n-2],a[n-1],t[n-1])!=a[0])continue;
            if(ne(a[n-1],a[  0],t[  0])!=a[1])continue;
            rep(i,0,n)
            {
                if(a[i]==0)printf("S");
                else printf("W");
            }
            printf("\n");
            return 0;
        }
    }
    cout<<-1<<endl;
}

Measured memory_bytes: 4992
//AND BAND KA TOLA JO MERA CODE DEKHRA WO BHEN KA ....
//------------------------------------------Template------------------------------------------------
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define lp(i,a,b) for(ll i=a;i<b;i++)
#define rlp(i,a,b) for(ll i=b;i>=a;i--)
#define TEZI_BOLTEY ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define INF 1e9
#define pb push_back 
#define mp make_pair 
#define endl "\n"
ll nCr(ll n, ll k) {double res = 1;lp(i,1,k+1){res = res * (n - k + i) / i;}return (int)(res + 0.01);}
//---------------------------------------------------------------------------------------------------
//---------------------------------<<< DRAGON SIN MELIODAS >>>---------------------------------------
//---------------------------------------------------------------------------------------------------
int main()
{
	TEZI_BOLTEY
	ll d,t,s;
	cin >> d >> t >> s;
	if(t*s>=d)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;

	}
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007   // 1e9+7
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
set<int> prime_find(int n){
	vector<bool> v(n+1,1);
	set<int>p;
	int k=2;
	while(k*k<=n)
	{
		if(v[k])for(int i=k*k;i<=n;i+=k)v[i]=0;
		k++;
	}
	for(int i=2;i<=n;i++)if(v[i])p.insert(i);
	return p;
}
int main() {
	int n;
	cin>>n;
	vector<int> v(n); 
	for(int i=0;i<n;i++)scanf("%d",&v[i]);
	set<int> p=prime_find(1e7);
	map<int,int> mp;
	for(int i=0;i<n;i++)
	{
		int k=v[i];
		for(set<int>::iterator it=p.begin();(*it)*(*it)<=k&&it!=p.end();it++)
		{
			int x=*it;
			if(k%x==0)
			{
				while(k%x==0)k/=x; 
				mp[x]++;
			}
		}
		if(k!=1)mp[k]++;
	}
	int ans=0;
	for(set<int>::iterator it=p.begin();it!=p.end();it++){
		ans=max(mp[*it],ans);
	}
	if(ans<=1)cout<<"pairwise coprime"<<endl;
	else if(ans<n)cout<<"setwise coprime"<<endl;
	else cout<<"not coprime"<<endl;
	return 0;
}

Measured memory_bytes: 69596
#include <bits/stdc++.h>
using namespace std;
int main() {
    double a;
    cin >> a;

    double odd=0;
    if(a == 0){
        cout << "0" << endl;
        return 0;

    }
    for(int i = a; i > 0; i--){
        if(i%2==1){
            odd++;
        }
    }

    cout << odd/a; 
    return 0;

}
  
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using intt =  unsigned long long;
using namespace std;

int main()
{
    fast;
    intt n,W;
    cin>>n>>W;
    intt wt[n];
    intt val[n];
    intt sum = 0;
    for(intt i = 0;i<n;i++)
    {
        cin>>wt[i]>>val[i];
        sum+=val[i];
    }
    vector<intt> dp(sum+1,INT_MAX);
    dp[0] = 0;

    for(int i = 0;i<n;i++)
        for(int v = sum-val[i];v>=0;v--)
            dp[v+val[i]] = min(dp[v+val[i]],dp[v]+wt[i]);

    intt ans = 0;
    for(intt i = 0;i<=sum;i++)
        if(W>=dp[i])
            ans = max(ans,i);
    cout<<ans;


}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string S; cin >> S;
    bool used[26] = {};
    for (auto c : S) used[c-'a'] = true;
    if (S.size() != 26) {
        for (int i = 0; i < 26; i++) {
            if (!used[i]) {
                cout << S << (char)(i + 'a') << endl;
                return 0;
            }
        }
    } else {
        for (int i = 25; i > 0; i--) {
            if (S[i] > S[i-1]) {
                char c = 'z';
                for (int j = i; j < 26; j++) {
                    if (S[j] > S[i-1]) c = min(c, S[j]);
                }
                cout << S.substr(0, i-1) << c << endl;
                return 0;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256