akhauriyash/Code-Regression huggingface dataset:
import sys
N = int(input().strip())
array = list(map(int, input().strip().split()))
ans = 1
for i in array:
  if i == 0:
    print(0)
    sys.exit()
for i in array:
  ans *= i
  if ans > 1e18:
    print(-1)
    sys.exit()
if ans > 1e18:
  print(-1)
else :
  print(ans)

Measured memory_bytes: 21660
struct Heap<Element: Comparable>: SequenceType, GeneratorType {
    var items = [Element]()
    var i = 0
    mutating func next() -> Element? {
        defer { i += 1 }
        return i < items.count ? items[i] : nil
    }
    mutating func push(item: Element) {
        var i = items.count
        while i > 0 {
            let p = (i - 1) / 2
            if items[p] <= item {
                break
            }
            if i == items.count {
                items.append(items[p])
            } else {
                items[i] = items[p]
            }
            i = p
        }
        if i == items.count {
            items.append(item)
        } else {
            items[i] = item
        }
    }
    mutating func pop() -> Element {
        let ret = items[0]
        let x = items[items.count - 1]
        var i: Int = 0
        while i * 2 + 1 < items.count - 1 {
            var a = i * 2 + 1
            let b = i * 2 + 2
            if b < items.count - 1 && items[b] < items[a] {
                a = b
            }
            if items[a] >= x {
                break
            }
            items[i] = items[a]
            i = a
        }
        items[i] = x
        _ = items.removeLast()
        return ret
    }
}
let M = Int(String(readLine()!.characters.split(" ")[1]))!
var a = Heap<Int>()
readLine()!.characters.split(" ").forEach{a.push(-Int(String($0))!)}
(0..<M).forEach{_ in a.push(a.pop()/2)}
print(a.reduce(0){$0-$1})

Measured memory_bytes: 7420
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
r = a.pop(0)
s = r
temp = 0
for i in range(n-1):
    if abs(r - 2*a[i]) < s:
        s = abs(r - 2*a[i])
        temp = a[i]
print(r, temp)

Measured memory_bytes: 20132
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 60;
const int INF = 0x7FFFFFFF/2;
typedef pair<int, int> state;
bool f[N][N][N][N];
int n, m, k, sx, sy, ex, ey;

int calc_dist()
{
	static int dist[N][N];
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			dist[i][j] = INF;
	dist[sx][sy] = 0;
	queue<state> q;
	q.push(make_pair(sx, sy));
	while (!q.empty()) {
		state now = q.front();
		int x = now.first, y = now.second;
		if (x - 1 >= 0 && dist[x - 1][y] == INF) {
			if (f[x][y][x][y + 1]) {
				dist[x - 1][y] = dist[x][y] + 1;
				q.push(make_pair(x - 1, y));
				if (x - 1 == ex && y == ey) break;
			}
		}
		if (x + 1 < n && dist[x + 1][y] == INF) {
			if (f[x + 1][y][x + 1][y + 1]) {
				dist[x + 1][y] = dist[x][y] + 1;
				q.push(make_pair(x + 1, y));
				if (x + 1 == ex && y == ey) break;
			}
		}
		if (y - 1 >= 0 && dist[x][y - 1] == INF) {
			if (f[x][y][x + 1][y]) {
				dist[x][y - 1] = dist[x][y] + 1;
				q.push(make_pair(x, y -1));
				if (x == ex && y - 1 == ey) break;
			}
		}
		if (y + 1 < m && dist[x][y + 1] == INF) {
			if (f[x][y + 1][x + 1][y + 1]) {
				dist[x][y + 1] = dist[x][y] + 1;
				q.push(make_pair(x, y + 1));
				if (x == ex && y + 1 == ey) break;
			}
		}
		q.pop();
	}
	return dist[ex][ey];
}

int main()
{
	ios::sync_with_stdio(false);
	memset(f, true, sizeof(f));
	cin >> n >> m >> k;
	for (int i = 1; i <= k; ++i) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2) swap(x1, x2);
		if (y1 > y2) swap(y1, y2);
		if (y1 == y2) {
			for (int x = x1; x < x2; ++x) {
				f[x][y1][x + 1][y1] = false;
				f[x + 1][y1][x][y1] = false;
			}
		} else if (x1 == x2) {
			for (int y = y1; y < y2; ++y) {
				f[x1][y][x1][y + 1] = false;
				f[x1][y + 1][x1][y] = false;
			}
		}

	}
	cin >> sx >> sy;
	cin >> ex >> ey;
	int ori_dist = calc_dist();
	int next_dist, ans = -1;
	

	for (int x = 0; x < n; ++x)
		for (int y = 0; y < m; ++y) {
			if (f[x][y][x][y + 1]) {
				f[x][y][x][y + 1] = false;
				next_dist = calc_dist();
				if (next_dist != INF) {
					ans = max(ans, next_dist);
				}
				f[x][y][x][y + 1] = true;
			}
			if (f[x][y][x + 1][y]) {
				f[x][y][x + 1][y] = false;
				next_dist = calc_dist();
				if (next_dist != INF) {
					ans = max(ans, next_dist);
				}
				f[x][y][x + 1][y] = true;
			}
		}
	if (ans == -1)
		cout << 0 << endl;
	else {
		cout << ans - ori_dist << endl;
	}
	return 0;
}

Measured memory_bytes: 13896
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    int n;
    cin>>n;
    int cnt = 0;
    if(n<3){
        cout<<0<<endl;
        return 0;
    }
    cnt = 0;
    while(n>=3){
        cnt++;
        n-=3;
    }
    cout<<cnt<<endl;
    return 0;
}

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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
#define INF 10000000

int main()
{
  int n,m;cin>>n>>m;
  vector<int> a(m);
  vector<int> b(m);
  int i;
  rep(i,m)cin>>a[i]>>b[i];
  vector<vector<int>> e(n);
  rep(i,m)
  {
    a[i]--;
    b[i]--;
  }
  rep(i,m)
  {
    e[a[i]].emplace_back(b[i]);
    e[b[i]].emplace_back(a[i]);
  }
  vector<int> root(n,-1);
  vector<int> minstep(n,INF);
  queue<int> q;
  queue<int> q2;
  q.push(0);
  minstep[0]=0;
  while(!q.empty())
  {
    while(!q.empty())
    {
      int now=q.front();
      q.pop();
      rep(i,e[now].size())
      {
        if(minstep[e[now][i]]==INF)
        {
          root[e[now][i]]=now;
          minstep[e[now][i]]=minstep[now]+1;
          q2.push(e[now][i]);
        }
      }
    }
    while(!q2.empty())
    {
      q.push(q2.front());
      q2.pop();
    }
  }
  cout<<"Yes"<<endl;
  for(i=1;i<n;i++)
  {
    cout<<root[i]+1<<endl;
  }
}


Measured memory_bytes: 12120
#include<bits/stdc++.h>
using namespace std;
#define int long long


//達成できる最小の重みを返す
//達成できない場合は -1
int dfs(vector<vector<int> > &adj, int u, vector<int> &w){

    // 極小
    if(adj[u].size() == 0) return 0;
    
    vector<pair<int, int> > vec;
    int sum = 0;
    for(auto v : adj[u]){
        int val = dfs(adj, v, w);
        if(val == -1) return -1;

        vec.push_back({val, w[v]});
        sum += val + w[v];
    }

    int n = (int)vec.size();
    //ここから DP する
    vector<vector<bool> > dp(n + 1, vector<bool> (sum + 1, false));
    dp[0][0] = true;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= sum; j++){
            if(dp[i][j] == false) continue;
            dp[i + 1][j + vec[i].first] = dp[i + 1][j + vec[i].second] = true;
        }
    }

    int ret = -1;
    for(int j = min(w[u], sum); j >= 0; j--){
        
        if(dp[n][j]){
            ret = sum - j;
            break;
        }
    }

    return ret;
}

signed main(){

    int n; cin >> n;
    vector<vector<int> > adj(n);
    vector<int> w(n);
    for(int i = 1; i < n; i++){
        // 頂点 i の親が p
        int p; cin >> p;
        p--;
        adj[p].push_back(i);
    }

    for(int i = 0; i < n; i++) cin >> w[i];

    string ans = "POSSIBLE";
    if(dfs(adj, 0, w) == -1) ans = "IM" + ans;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
x,y = map(int, input().split())

all_kame = y - 2*x
#print(type(all_kame))
if all_kame < 0:
    print("No")
    
elif all_kame == 0:
    print("Yes")
    
else:
    for i in range(x+1):
        if all_kame - 2*(x-i) ==0:
            print("Yes")
            exit()
    print("No")

Measured memory_bytes: 9076
/* C/C++ program to remove invalid parenthesis */
#include <bits/stdc++.h> 
using namespace std; 
#define ll long long int
vector<vector<ll>> adj;
int dfs(int i,vector<ll>& dp, vector<ll>& visited)
{
    visited[i]=1;
    
    for(auto j:adj[i])
    {
        if(!visited[j])
        {
            
            dfs(j,dp,visited);
        }
        dp[i]=max(dp[i],1+dp[j]);
    }
    return 0;
}

int main() 
{ 
   ll v,e;
   cin>>v>>e;
   adj.resize(v);
   for(ll i=0;i<e;i++)
   {
       ll n,m;
       cin>>n>>m;
       adj[n-1].push_back(m-1);
   }
   ll ans=0;
   vector<ll> dp(v,0);
   vector<ll> visited(v,0);
   
   for(ll i=0;i<v;i++){
       if(!visited[i])
      dfs(i,dp,visited);
   }
   for(ll i=0;i<v;i++)
   ans=max(ans,dp[i]);
   
   cout<<ans;
	return 0; 
} 


Measured memory_bytes: 9984
#include <bits/stdc++.h>
    using namespace std;
     
    int main(){
      int a,b,c;
      cin >> a >> b >> c;
      int ans = 0;
      while(true){
        if((b-a)>=0){
          b = b-a;
          ans++;
        }
        else break;
      }
      cout << min(c,ans) << endl;
      return 0;
    }

Measured memory_bytes: 256
/**
  * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_2_D
  * ????????¢????????????
  * ????????¢?????????????????????????????????????????????????????°????????????????????????????????????
  * ?¬????????????????????????¢?????????????????????????????¨??????????????????????????§?¨? (W,H) ????????????????????????
  * ????????????????????????????????§?¨? (x,y) ??¨?????? r ??§?????????????????????
  * ???????????´??° W???H???x???y???r ????????????????????§??????????????????????????????
  */
object Main {
  def main(args: Array[String]): Unit = {
    val seq = io.StdIn.readLine().split(" +").map(_.toInt).toSeq
    val (w, h, x, y, r) = seq match {
      case Seq(a, b, c, d, e) => (a, b, c, d, e)
    }
    // r ??? x ??? W - r
    // r ??? y ??? H - r
    val answer = if (r <= x && x <= w - r && r <= y && y <= h - r) {
      "Yes"
    } else {
      "No"
    }
    println(answer)
  }

}

Measured memory_bytes: 43916
#include <iostream>
#include <string>
using namespace std;
 
int main() {
 int n, pos;
 string str;
 
 cin>>n; cin.get( );
 while(n--){
 getline(cin, str); 
 while(pos = str.find("Hoshino"), pos!=string::npos)str.replace(pos, 7, "Hoshina");
 cout<<str<<endl;
 } 
 return 0;
}

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

int check(int a, int ans){
    string str;
    str = std::to_string(a);
    if(str[0] == str[4] && str[1] == str[3]) ans++;
    return ans;
}

int main(){
    int A, B;
    cin >> A >> B;
    int A_c = A;
    int ans = 0;
    for(int i=0; i<B-A+1; i++) {
        ans = check(A_c, ans);
        A_c++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3608
from pprint import pprint
from statistics import median

N = int(input())
As = list(map(int, input().split(" ")))

As = [A - i for i, A in enumerate(As)]

# pprint(As)

b = int(median(As))

ans = 0

for A in As:
    ans += abs(A-b)

print(ans)

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

vector<int> hamming_numbers;
int m, n;

void print_vi(vector<int> vi)
{
	rep(i, vi.size())
	{
		printf("%d ", vi[i]);
	}
}

signed main()
{
	rep(i,21) rep(j,13) rep(k,9)
	{
		int num = pow(2, i) * pow(3, j) * pow(5, k);
		if (num <= 1000000)
		{
			hamming_numbers.push_back(num);
		}
	}

	sort(hamming_numbers.begin(), hamming_numbers.end());

	//print_vi(hamming_numbers);

	while (cin >> m >> n)
	{
		cout << distance(lower_bound(hamming_numbers.begin(), hamming_numbers.end(), m), upper_bound(hamming_numbers.begin(), hamming_numbers.end(), n)) << endl;
	}
}

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

signed main() {
  int N; cin >> N;
  vector<int> C(N-1), S(N-1), F(N-1);
  rep(i, N-1) cin >> C[i] >> S[i] >> F[i];
  
  vector<int> ans(N, 0);
  
  rep(i, N-1) {
    int t = 0;
    rep(j, N-i-1) {
      while(!(t >= S[i+j] && t%F[i+j] == 0)) t++;
      t += C[i+j];
    }
    ans[i] = t;
  }
  
  rep(i, N) cout << ans[i] << endl;

}

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

int main(){
    int n;cin>>n;
    set<int> a;  //setに値を入れる
    for(int i=0,p;i<n;i++){
        cin>>p;
        a.insert(p);
    }

    int p,q;  //答えをp,qとしpを最大の値,qをp/2にもっとも近いpでない値とする
    set<int>::iterator itr;
    itr=a.end();
    itr--;
    p=*itr;    //pがとれる

    a.erase(p);    //p以外から探すのでpをsetから除く
    int dif=2000000000;  //xはp/2  difはp/2との差とする
                                  //dif,最初は十分大きくとる(小さく更新していくので)

    itr=a.begin();
    while(itr!=a.end()){            //それぞれの値に対してdifを考えて最小となるときをqに入れる
        if(dif>abs(*itr*2-p)){
            dif=abs(*itr*2-p);
            q=*itr;
        }
        itr++;
    }

    cout<<p<<" "<<q<<endl;

    return 0;
}


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

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

  vector<int> m;
  for (char c: n) {
    m.push_back(c - '0');
  }

  vector<int> op = { 1, -1 };
  vector<char> opc = { '+', '-' };

  int n_patterns = 1 << (m.size() - 1);

  for (int i = 0; i < n_patterns; i++) {
    string r = to_string(m[0]);
    int total = m[0];
    int cur = i;
    
    for (int j = 1; j < m.size(); j++) {
      total += m[j] * op[cur % 2];
      r += opc[cur % 2] + to_string(m[j]) ;
      cur /= 2;
    }

    if (total == 7) {
      cout << r << "=7" << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
def print_list(array):
    for i,e in enumerate(array):
        if i == N - 1:
            print(e)
        else:
            print(e, end=" ")

def bubbleSort():
    for i in range(N-1):
        for j in range(N-1, i, -1):
            if int(A[j][1:]) < int(A[j-1][1:]):
                w = A[j]; A[j] = A[j-1]; A[j-1] = w

def selectionSort():
    for i in range(N):
        min_index = i
        for j in range(i, N):
            if int(B[min_index][1:]) > int(B[j][1:]):
                min_index = j
        if i != min_index:
            w = B[i]; B[i] = B[min_index]; B[min_index] = w

N = int(input())
A = input().split()
B = list(A)
bubbleSort()
print_list(A)
print("Stable")
selectionSort()
print_list(B)
if A == B:
    print("Stable")
else:
    print("Not stable")



Measured memory_bytes: 5612
from collections import defaultdict, deque

N, Q = map(int, input().split())
adjacent = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adjacent[a].append(b)
    adjacent[b].append(a)
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

q = deque([(0, -1)])
while len(q) > 0:
    u, p = q.pop()
    for v in adjacent[u]:
        if v == p:
            continue
        ans[v] += ans[u]
        q.appendleft((v, u))
print(' '.join([str(ans[i]) for i in range(N)]))


Measured memory_bytes: 76260
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	private static final boolean TEST = false;

	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n = in.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		System.out.println(solve(a));
		in.close();
	}

	private static long solve(int[] a) {
		int mi = 0;
		for (int i = 1; i < a.length; i++)
			if (Math.abs(a[mi]) > Math.abs(a[i]))
				mi = i;

		long ans = 0;
		if (a[mi] == 0) {
			for (int i = 0; i < a.length; i++)
				ans += Math.abs(a[i]);
			return ans;
		}

		for (int i = 0; i < mi; i++)
			if (a[i] < 0) {
				ans -= a[i];
				a[i + 1] *= -1;
			} else
				ans += a[i];
		for (int i = a.length - 1; i > mi; i--)
			if (a[i] < 0) {
				ans -= a[i];
				a[i - 1] *= -1;
			} else
				ans += a[i];
		ans += a[mi];
		return ans;
	}
}

Measured memory_bytes: 50152
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b,c;
    cin>>a>>b;
    c=a+b;
    int x=0;
    int l=c.length();
    x+=(c[0]-'0');
    for(int i=1;i<l;i++){
        x*=10;
        x+=(c[i]-'0');
    }
    int ll=sqrt(x);
    if(ll*ll==x) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
    }


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int a;
  cin >> a;
  cout << a * (1 + a + a * a) << endl;
  return 0;
}

Measured memory_bytes: 3640
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]

x = sum(A) - 2 * sum([A[2*i+1] for i in range(N//2)])
ans = [x]
for i in range(N-1) :
    ans.append(2 * A[i] - x)
    x = ans[i+1]

print(*ans)


Measured memory_bytes: 14108
#include<bits/stdc++.h>
#define N 200004
#define pp pair<int,int>
#define mp make_pair
#define pb push_back
#define ff first
#define dd second


using namespace std;
int n;
int maxi = 1;
int tab[N];

void removeDigits(set<pp> & digits, int sz) {
    while(!digits.empty() and digits.rbegin()->ff >= sz) digits.erase(*digits.rbegin());
}

int getNumber(set<pp> &digits, int index) {
    auto it = digits.lower_bound({index,-1});
    if (not(it  == digits.end() or it->ff != index)) {
        return it->dd;
    }
    return 0;
}

void setNumber(set<pp> &digits, int index, int val) {
    auto it = digits.lower_bound({index,-1});
    if (not(it  == digits.end() or it->ff != index)) {
        digits.erase(it);
    }
    if ( val != 0 ) digits.insert({index, val});
}

bool add(set<pp> & digits, int index, int base) {

    int rest = 1;

    while (index >= 0 and rest > 0) {
        int sum = getNumber(digits, index);
        sum += rest;
        rest = ((sum - (sum%base))/base);
        setNumber(digits, index, sum % base);
        index--;
    }

    if (index < 0 and rest > 0) {
        return false;
    }
    return true;
}

bool test(int s) {
    set<pp> digits;
    for(int i = 1; i < n; ++i) {

        removeDigits(digits, tab[i]);

        if (tab[i] <= tab[i-1] and !add(digits, tab[i]-1, s)) {
            return false;
        }
    }
    return true;
}

main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    if (n == 1) {
        cout << 1 << endl; exit(0);
    }

    for (int i = 0; i < n; ++i) cin >> tab[i], maxi = max(maxi, tab[i]);

    bool grow = true;

    for(int i = 1; i < n; ++i) if (tab[i] <= tab[i-1]) grow = false;

    if (grow) {
        cout << 1 << endl; exit(0);
    }

    //cout << test(2) << endl;

    int l = 2; int r = n;
    while(r-l > 4) {
        int s = (l+r)/2;
        if (test(s)) {
            r = s;
        } else {
            l = s;
        }
    }

    for (int i = l; i <= r; ++i) if ( test(i) ) {
            cout << i << endl;
            exit(0);
        }
}

Measured memory_bytes: 1024
# coding: utf-8
# Your code here!
def f(m,k):#最初のm個, kずつ
    if m == 0: return 0
    if m < k: return 0
#    if (m,k) in memo:
#        return memo[(m,k)]
    z = 0
    if acc[m]//k >= c[m]:
        return acc[m]//k
    else:
        return f(m-1,k-1)


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

from itertools import accumulate

n = int(input())
a = [int(i) for i in readline().split()]

res = [0]*(n+1)
for i in a: res[i] += 1

c = [0]
for i in res:
    if i > 0: c.append(i)
c.sort()#reverse=True)

l = len(c)-1
#print(c)
acc = list(accumulate(c))

#print(acc,c)
res = [n]+[acc[m]//c[m] for m in range(1,l+1)]


#print(l,res)


m = l
for k in range(1,n+1):
    k -= l-m
    if res[m] >= k:
        print(acc[m]//k)
    else:
#        print(k,m)
        while res[m] < k:
            m -= 1
            k -= 1
        print(acc[m]//(k))







Measured memory_bytes: 45168
#include <stdio.h>
#define W 0
#define G 1
#define B 2
#define inf 1000000000

void dij();
int n, M[100][100];

int main(){
  int u, k, v, c;
  int i, j;
  scanf("%d",&n);
  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      M[i][j] = inf;
    }
  }
  for(i=0; i<n; i++){
    scanf("%d%d",&u,&k);
    for(j=0; j<k; j++){
      scanf("%d%d",&v,&c);
      M[u][v] = c;
    }
  }
  dij();
  return 0;
}

void dij(){
  int minv;
  int d[100], c[100];
  int i, u, v;
  for(i=0; i<n; i++){
    d[i] = inf;
    c[i] = W;
  }
  d[0] = 0;
  c[0] = G;
  while(1){
    minv = inf;
    u = -1;
    for(i=0; i<n; i++){
      if(minv > d[i] && c[i] != B){
	u = i;
	minv = d[i];
      }
    }
    if(u == -1)break;
    c[u] = B;
    for(v=0; v<n; v++){
      if(c[v] != B && M[u][v] != inf){
	if(d[v] > d[u] + M[u][v]){
	  d[v] = d[u] + M[u][v];
	  c[v] = G;
	}
      }
    }
  }
  for(i=0; i<n; i++){
    printf("%d ",i);
    printf("%d\n",d[i]);
  }
}




Measured memory_bytes: 2048
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
int a[105];
int main() {
	int d,n;
	cin>>d>>n;
	int pow=1;
	if(d==0)
		pow=1;
	else
		for(int i=1;i<=d;i++)
			pow*=100;
	for(int i=1;i<=99;i++){
		a[i]=i*pow;
	}
	a[100]=101*pow;
	cout<<a[n];
	return 0;
} 

Measured memory_bytes: 256
#include<stdio.h>

void move(char d, int n){
  int i;
  for(i=0;i<n;i++)printf("%c",d);
}

int main(void){
  int sx,sy,tx,ty,x,y;
  scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
  x=tx-sx;
  y=ty-sy;
  move('U',y);
  move('R',x);
  move('D',y);
  move('L',x+1);
  move('U',y+1);
  move('R',x+1);
  move('D',1);
  move('R',1);
  move('D',y+1);
  move('L',x+1);
  move('U',1);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#define eol '\n'
using namespace std;

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

  string s;
  cin >> s;

  int n = s.length();

  if (s[0] == s[n-1]) {
    if (n % 2 == 0) {
      cout << "First" << eol;
    } else {
      cout << "Second" << eol;
    }
  } else {
    if (n % 2 == 0) {
      cout << "Second" << eol;
    } else {
      cout << "First" << eol;
    }
  }
  
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1 ; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1 ; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const bool debug = 0;
/***************************************/

int N;
int level[30];
int num[30]; // 0~9, 10:+, 11:*

ll solve(int p, int ope) { // 0:+, 1:*	
	vector<ll> v;
	FOR(i, p, N) {
		if (level[p] > level[i]) break;
		if (level[i] == level[p]) {
			if (num[i] >= 10) v.push_back(solve(i + 1, num[i] == 11));
			else v.push_back(num[i]);
		}
	}
	
	ll res = ope == 1;
	REP(i, v.size()) {
		if (ope) res *= v[i];
		else res += v[i];
	}
	return res;
}

int main() {
	while (cin >> N, N) {
		REP(i, N) {
			string str;
			cin >> str;
			level[i] = str.size() - 1;
			if (str.back() == '+') num[i] = 10;
			else if (str.back() == '*') num[i] = 11;
			else num[i] = str.back() - '0';
		}
		if (debug) printf("@ ");
		cout << solve(0, 0) << endl;
	}
	return 0;
}



Measured memory_bytes: 3220
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        boolean[][] cards = new boolean[4][14];
        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            String[] st = br.readLine().split(" ");
            int i = Integer.parseInt(st[1]);
            switch (st[0]) {
                case "S":
                    cards[0][i] = true;
                    break;
                case "H":
                    cards[1][i] = true;
                    break;
                case "C":
                    cards[2][i] = true;
                    break;
                case "D":
                    cards[3][i] = true;
                    break;
            }
        }
        String[] type = new String[]{"S", "H", "C", "D"};
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                if (!cards[i][j]) {
                    bw.append(type[i] + " " + j + "\n");
                }
            }
        }
        bw.flush();
    }
    
}


Measured memory_bytes: 24292
# coding: utf-8
N, A, B = map(int, input().split())
S = input()
num = 0
fo = 0
for i in range(N):
    if num >= A + B or S[i] == 'c':
        print('No')
    elif S[i] == 'a':
        print('Yes')
        num += 1
    elif S[i] == 'b':
        fo += 1
        if fo <= B:
            print('Yes')
            num += 1
        else:
            print('No')

Measured memory_bytes: 4016
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    cin>>N>>M;
    
    int total=0;
    for(int i=0;i<M;++i){
        int A;
        cin>>A;
        total+=A;
    }
    
    int ans=N-total;
    if(ans<0) ans=-1;
    cout<<ans<<endl;
}


Measured memory_bytes: 3636
// AOJ 1089: Strawberry Cake
// 2017.12.18 bal4u@uu

#include <stdio.h>
#include <string.h>
#include <math.h>

#define N 50
#define D 0.01
#define EPS 1e-8

typedef struct { double x, y; } PP;
typedef struct { PP s, e; } LINE;

PP a[21]; int n;

int dcmp(double x)
{
	if (fabs(x) < EPS) return 0;
	return x < 0 ? -1 : 1;
}

double cross(double ax, double ay, double bx, double by) { return ax*by - ay*bx; }

void lineIntersection(PP *p, LINE *a, PP *vs, PP *ve)
{
    double a1, a2;

	a1 = cross(ve->x  - vs->x, ve->y  - vs->y,
			   a->s.x - vs->x, a->s.y - vs->y);
	a2 = cross(ve->x  - vs->x, ve->y  - vs->y,
			   a->e.x - vs->x, a->e.y - vs->y);
	p->x = (a->s.x*a2 - a->e.x*a1) / (a2-a1);
	p->y = (a->s.y*a2 - a->e.y*a1) / (a2-a1);
}

int convex_cut(LINE *u, int n, PP *p, PP *po)
{
	int i, d1, d2, top = 0;

    for (i = 0; i < n; i++) {
        d1 = dcmp(cross(u->e.x - u->s.x, u->e.y - u->s.y,
						p[i].x - u->s.x, p[i].y - u->s.y));
        d2 = dcmp(cross(u->e.x - u->s.x, u->e.y - u->s.y,
				      p[i+1].x - u->s.x, p[i+1].y - u->s.y));
        if (d1 >= 0) po[top++] = p[i];
        if (d1*d2 < 0) lineIntersection(po + top++, u, p+i, p+i+1);
    }
	po[top] = po[0];
#if 0
printf("convex_cut %d\n", top);
for (i = 0; i < top; i++) printf("[%d] (%lf,%lf)\n", i+1, po[i].x, po[i].y);
#endif
	return top;
}

#if 0
double area(int n, PP *p)
{
	int i;
    double s = 0;

    for (i = 1; i < n-1; i++) {
        s += cross(p[i].x-p[0].x, p[i].y-p[0].y, p[i+1].x-p[0].x, p[i+1].y-p[0].y);
    }
    return fabs(s) / 2;
}
#endif

double area(int n, PP *pp)
{
   int i;
   double s;

   for (s = 0, i = 0; i < n; i++) {
      s += (pp[i].x - pp[i+1].x) * (pp[i].y + pp[i+1].y);
   }
   return fabs(s)/2;
}

double calc(double x, double s)
{
	int k;
	PP b[30];

	LINE u;
	u.s.x = u.s.y = 0;
	u.e.x = 128*cos(x), u.e.y = 128*sin(x);
	k = convex_cut(&u, n, a, b);
	return area(k, b) / s;
}

int main()
{
	int i, x, y;
	double s, s1, s2, l, r, m;

	while(scanf("%d", &n) && n > 0) {
		for (i = 0; i < n; i++) {
			scanf("%d%d", &x, &y);
			a[i].x = x, a[i].y = y;
		}
		a[n] = a[0];
		s = area(n, a);

		l = 0, r = D, s1 = calc(0, s);
		for ( ; ; l+=D, r+=D, s1 = s2) {
			s2 = calc(r, s);
			if (s1 <= 0.5 && s2 >= 0.5) {
				i = N; while (i--) {
					m = (l+r)/2;
					if (calc(m, s) <= 0.5) l = m; else r = m;
				}
				break;
			}
		}
		printf("%.15lf %.15lf\n", 128*cos(m), 128*sin(m));
	}
	return 0;
}

Measured memory_bytes: 2140
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define LL long long
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 2e5 + 7;

LL qpow(LL a,LL b) {
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1LL;
    }
    return res;
}

int a[maxn];

int main() {
    LL x;
    while(~scanf("%lld",&x)) {
        LL y = (int)log2(x) + 1;
        printf("%lld\n",qpow(2LL,y) - 1LL);
    }
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(void)
{
	string s;
	cin >> s;
	int ans=10000;
	for(int i=1;i<=s.size()-2;i++)
	{
		int now = abs(753-stoi(s.substr(i-1,3)));
		if(ans>now)
			ans=now;
	}
	cout << ans << endl;
}
		

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
//#define DEBUG
#ifdef DEBUG
#define DEBUG_PRINT(fm, ...) do{std::printf("%s:%d(%s)", __FILE__, __LINE__, __func__);std::cout << "DEBUG PRINT ";std::printf(fm, __VA_ARGS__);}while(0)
#define DEBUG_VAL(a, b) do{std::printf("%s:%d(%s)", __FILE__, __LINE__, __func__);std::cout <<"DEBUG VAL " << a << ":" << b << endl;}while(0)
#else
#define DEBUG_PRINT(...)do{}while(0);
#define DEBUG_VAL(a, b)do{}while(0);
#endif

using namespace std;
using ll = long long;
using v1 = vector<int>;
using vl = vector<long long>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;

int main(){
    double d, t, s;
    cin >> d >> t >> s;
    if(t < d/s) cout << "No" << endl;
    else cout << "Yes" << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  if (A + B > C + D) {
    cout << "Left" << endl;
  } else if (A + B == C + D) {
    cout << "Balanced" << endl;
  } else if(A + B < C + D) {
    cout << "Right" << endl;
  }
}

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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

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

  ll x, a, b;
  cin >> x >> a >> b;

  cout << (abs(a - x) < abs(b - x) ? "A" : "B");
}

Measured memory_bytes: 256
n,m = map(int, input().split( ))
p= [i for i in range(n)]+[n+j for j in range(m)]
rk = [0]*(n+m)
def rt(a):
    if a==p[a]:
        return a
    p[a] = rt(p[a])
    return p[a]
def uni(a,b):
    ra = rt(a);rb=rt(b)
    if ra==rb:
        return
    if rk[ra]>rk[rb]:
        p[rb] = ra
    else:
        if rk[ra]==rk[rb]:
            p[ra] = rb
            rk[rb]+=1
        else:
            p[ra]=rb 
    return

kl = {}
for i in range(n):
    ki,*li, = map(int, input().split( ))
    kl[i] = li
for ki in kl:
    for j in range(len(kl[ki])):
        kl[ki][j]-=1

for ki in kl:
    for lij in kl[ki]:
        uni(ki,lij+n)
for i in range(n):
    rt(i)
if len(set(p[:n]))==1:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 75500
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	double p=0;
	range(i,1,n+1)if(i%2)p+=1.0;
	puta(p/n);
	return 0;
}

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())

signed main(){

	lli a,b;
	cin>>a>>b;
	lli x = a*b;

		if(a<b){
    lli tmp = a;
    a = b;
    b = tmp;
  }

  lli r = a%b;
  while(r!=0){
  	a = b;
  	b = r;
  	r = a%b;
  }

  cout<<x/b<<endl;

	

	return 0;
}

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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int n, k, s;
	cin >> n >> k >> s;
	if(s > 500000000){
		for(int i = 0; i < k; ++i){ cout << s << " "; }
		for(int i = k; i < n; ++i){ cout << 1 << " "; }
		cout << endl;
	}else{
		for(int i = 0; i < k; ++i){ cout << s << " "; }
		for(int i = k; i < n; ++i){ cout << 1000000000 << " "; }
		cout << endl;
	}
	return 0;
}



Measured memory_bytes: 1280
#include "bits/stdc++.h"
using namespace std;
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define repi_(i,a,b) for(int i=(a), i##_len=(b); i<=i##_len; ++i)
#define rep_(i,n) repi_(i,0,n)
#define all(x) (x).begin(),(x).end()
#define vsort(v) sort((v).begin(), (v).end())
#define gsort(v) tsort(v); reverse((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define el "\n"
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define cosp(x) cout<<(x)<<' '
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#define inf INT_MAX
#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif
typedef long long lint;

lint dx[8] = { 0,1,1,1,0,-1,-1,-1 },
dy[8] = { 1,1,0,-1,-1,-1,0,1 };

template<class T>inline bool maxi(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool mini(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }


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

	lint n; cin >> n;
	string s[50];
	lint f[26] = { }, ftmp[26] = {0};
	rep(i, 26)f[i] = INT_MAX;

	rep(i, n) {
		cin >> s[i];
		rep(j, 26) {
			ftmp[j] = 0;
		}
		rep_(j, s[i].length()) {
			ftmp[s[i][j] - 'a']++;
		}
		rep(j, 26) {
			mini(f[j], ftmp[j]);
		}
	}
	
	rep(i, 26) {
		rep(j, f[i]) {
			cout << (char)('a' + i);
		}
	}
	cout << el;
	
	gc();
}

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

int main() {
    string S;
    cin >> S;
    string ans = "Good";
    for (int i = 0; i < 3; i++){
        if (S[i] == S[i+1]){
            ans = "Bad";
            break;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> p(N);
  for (int i = 0; i < N; i++) {
    cin >> p.at(i);
  }
  sort(p.begin(), p.end()); 
  reverse(p.begin(), p.end());
  int answer;
  answer = 0;
  for (int j = 1; j < N; j++) {
    answer+= p.at(j);
  }
  cout << answer + (p.at(0) / 2) << endl;
}
 


Measured memory_bytes: 256
package main

import (
	"bytes"
	"fmt"
)

const Mod = int(1e9 + 7)

var memo []map[string]int
var N int

func ok(last4 string) bool {
	for i := 0; i < 4; i++ {
		t := []byte(last4)
		if i >= 1 {
			t[i-1], t[i] = t[i], t[i-1]
		}
		if bytes.Contains(t, []byte("AGC")) {
			return false
		}
	}
	return true
}

func dfs(n int, last3 string) int {
	if n == N {
		return 1
	}
	if v, exists := memo[n][last3]; exists {
		return v
	}
	ans := 0
	for _, c := range []string{"A", "C", "G", "T"} {
		if ok(last3 + c) {
			ans += dfs(n+1, last3[1:]+c)
			ans %= Mod
		}
	}
	memo[n][last3] = ans
	return ans
}

func main() {
	fmt.Scan(&N)
	memo = make([]map[string]int, N+1)
	for i := 0; i < N+1; i++ {
		memo[i] = make(map[string]int)
	}
	fmt.Println(dfs(0, "TTT"))
}


Measured memory_bytes: 2780
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;

const long long infCost=1000000000000000ll;
long long n;
long long a, b, c, d;
double log10d;
unordered_map <long long, long long> memo;
long long ab(long long x){return x<0ll?-x:x;}
long long solve(long long n){
	if(n<0ll)
		return infCost;
	if(n<=1ll)
		return n*d;
	if(memo.count(n))
		return memo[n];
	long long ret=infCost;
	if(log10d+log10(n)<12.0){
		ret=min(ret, d*n);
	}
	for(int i = n%2;i > -2;i -= 2){
		ret=min(ret, solve((n-i)/2)+d*ab(i)+a);
	}
	for(int i = n%3;i > -3;i -= 3){
		ret=min(ret, solve((n-i)/3)+d*ab(i)+b);
	}
	for(int i = n%5;i > -5;i -= 5){
		ret=min(ret, solve((n-i)/5)+d*ab(i)+c);
	}
	// printf("%lld %lld\n", n, ret);
	return memo[n]=ret;
}
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		memo.clear();
		scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
		log10d=log10(d);
		printf("%lld\n", solve(n));
	}
}

Measured memory_bytes: 4016
import sys

MOD = 10 ** 9 + 7

def make_table(n=10**6, p=10**9+7):
    fac = [None] * (n + 1)
    fac[0] = 1
    ifac = fac.copy()
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % p
    ifac[n] = pow(fac[n], p - 2, p)
    for i in range(n-1, 0, -1):
        ifac[i] = ifac[i+1] * (i + 1) % p
    return fac, ifac
fac, ifac = make_table()
def comb_mod(n, r, mod=10**9+7):
    if r < 0 or r > n:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

h, w, a, b = map(int, sys.stdin.readline().split())

def main():
    total = comb_mod(h+w-2, h-1)

    ng = 0
    j = b - 1
    for i in range(h - a, h):
        ng += comb_mod(i + j, i) * comb_mod(h-1-i + w-1-b, h-1-i) % MOD
        ng %= MOD
    
    ans = (total - ng) % MOD
    return ans 

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 82292
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

N = list(get_input())
for l in range(len(N)):
    table = [[0 for i in range(3)] for j in range(3)]
    S = N[l]
    ans = "d"

    for i in range(9):
        if S[i] == "o":
            table[i // 3][i % 3] = 1
        elif S[i] == "x":
            table[i // 3][i % 3] = -1

    for i in range(3):
        s = 0
        for j in range(3):
            s += table[i][j]
        if s == 3:
            ans = "o"
        elif s == -3:
            ans = "x"

    for i in range(3):
        s = 0
        for j in range(3):
            s += table[j][i]
        if s == 3:
            ans = "o"
        elif s == -3:
            ans = "x"

    s = table[0][0] + table[1][1] + table[2][2]
    if s == 3:
        ans = "o"
    elif s == -3:
        ans = "x"

    s = table[0][2] + table[1][1] + table[2][0]
    if s == 3:
        ans = "o"
    elif s == -3:
        ans = "x"

    print(ans)



Measured memory_bytes: 5576
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
 
#if DEBUG
    #include "debug.h"
#else
    #define debug(args...)
#endif    

using namespace std;

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


#define M 1000000 
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define fill(a,x) memset(a,x,sizeof(a))
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = INT_MAX;
const int mod = 1e9+7;

const int N = 2e5 + 10;
inline int add(int x,int y){
  x += y;
  if(x >= mod) x -= mod;
  return x;
}
inline int mul(int x,int y){
  x = (1LL * x * y) % mod;
  return x;
}
clock_t time_p=clock();



int32_t main(){
  fast;

  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);

  int k,n;
  cin >> k >> n;
  vector<int>A(n);
  FOR(i,0,n-1)cin >> A[i];
  vector<int>D(n);
  FOR(i,0,n-2) {
    D[i] = A[i + 1] - A[i];
  }
  D[n - 1] = k - A[n - 1] + A[0];
  sort(all(D));
  debug(D);
  ll ans = 0;
  FOR(i,0,n-2)ans += D[i];
  cout << ans << "\n";


  time_p=clock()-time_p;
  cerr<<"\nTime Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";

  return 0;
}

Measured memory_bytes: 1792
import sys
a = []
b = []
c = [[False for i in range(3)] for i in range(3)]
for i in range(3):
    a.append(list(map(int, input().split())))

n = int(input())
for i in range(n):
    b.append(int(input()))

for i in range(n):
    for j in range(3):
        for k in range(3):
            if a[j][k] == b[i]:
                c[j][k] = True
# 縦
for i in range(3):
    if c[i] == [True, True, True]:
        print("Yes")
        sys.exit(0)

for i in range(3):
    if [c[0][i], c[1][i], c[2][i]] == [True, True, True]:
        print("Yes")
        sys.exit(0)

if [c[0][0], c[1][1], c[2][2]] == [True, True, True] or [c[0][2], c[1][1], c[2][0]] == [True, True, True]:
    print("Yes")
    sys.exit(0)
print("No")

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

	int val=n%1000;
	if(val==0)
	{
		cout<<0<<endl;;
	}
	else
	{
		cout<<1000-val<<endl;
	}
	return 0;

}

Measured memory_bytes: 3608
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;


int main(){
  int n;
  cin>>n;
  int a[n];
  REP(i, n)cin>>a[i];
  if(n==1){
    cout<<a[0]<<endl;
    return 0;
  }

  int b[n];
  if(n%2){
    REP(i, n/2+1) b[i] = a[n-1-i*2];
    for(int i=n/2+1; i<n; ++i) b[i] = a[2*(i-n/2)-1];
  }
  else{
    REP(i, n/2) b[i] = a[n-1-i*2];
    for(int i=n/2; i<n; ++i) b[i] = a[2*(i-n/2)];
  }

  REP(i, n-1)cout<<b[i]<<" ";
  cout<<b[n-1]<<endl;


  return 0;
}


Measured memory_bytes: 3712
import java.util.Scanner;

public class Main {
 
	public static void main(String[] args) {
 
		    Scanner scanner = new Scanner(System.in);
		    
		    int N = scanner.nextInt();
		    int X = scanner.nextInt();
		    int T = scanner.nextInt();
		    int amari = N % X;
		    if(amari != 0) {
		    	int sho = N / X + 1;
		    	System.out.println(sho * T);
		    }else {
		    	int sho = N / X;
		    	System.out.println(sho * T);
		    }
}
}

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

using ll=long long;

int main() {
  string S; cin >>S;
  int w; cin >>w;
  for (int i=0;i<(int)S.size();i+=w) {
    cout <<S[i];
  }
  cout <<endl;
  return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
int main(void){
    int n,s,x,a[10],e[11],c,i,j,m;
    int l[]={9,26,50,80,115,154,196,240,285,330};
    while(~scanf("%d%d",&n,&s)){
        x=c=m=0;
        for(i=0;i<11;i++)e[i]=0;
        for(i=0;i<n;i++){
            a[i]=n-i-1;
            e[a[i]]=1;
            x+=a[i]*(i+1);
        }
        if(s>330) m=n;
        do{
            if(x==s)c++;
            if(x>=s)m++;
            else while(s-x>l[m])m++;
            for(i=0;i<n;i++){
                x-=a[i]*(i+1);
                e[a[i]]=0;
                if(i<m)continue;
                if(i==0)
                    a[i]=(s-x<10&&!e[s-x]?s-x:10);
                else
                    do{a[i]++;}while(e[a[i]]);
                if(a[i]>9){m++;continue;}
                e[a[i]]=1;
                x+=a[i]*(i+1);
                for(i--;i>=0;i--){
                    for(j=0;j<10;j++){
                        if(e[j])continue;
                        a[i]=j;
                        e[a[i]]=1;
                        x+=a[i]*(i+1);
                        break;
                    }
                }
                if(x>s) {
                    m++;
                    if(m>=n) break;
                    continue;
                }
                m=0;
                break ;
            }
        } while(m<n);
        printf("%d\n",c);
    }
    return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>

#define INF 100000000
using namespace std;


int main(){
    int H, W;
    cin >> H >> W;
    
    char s[H+2][W+2];
    int distance[H+2][W+2];
    
    int white=0;
    
    for(int h=0; h<=H+1; h++){
        for(int w=0; w<=W+1; w++){
            if(h==0 || h==H+1 || w==0 || w==W+1){
                s[h][w]='#';
            }else{
                cin>>s[h][w];
            }
            
            distance[h][w]=INF;
            
            if(s[h][w]=='.'){white++;}
        }
    }
    
    distance[1][1]=0;
    
    typedef pair<int, int> hw;
    queue<hw> que;
    
    hw start;
    start.first=1;
    start.second=1;
    que.push(start);
    
    while(!que.empty()){
        int temp_h=que.front().first;
        int temp_w=que.front().second;
        que.pop();
        
        if(s[temp_h-1][temp_w]=='.' && distance[temp_h-1][temp_w]==INF){
            distance[temp_h-1][temp_w]=distance[temp_h][temp_w]+1;
            hw n;
            n.first=temp_h-1;
            n.second=temp_w;
            que.push(n);
        }
        
        if(s[temp_h+1][temp_w]=='.' && distance[temp_h+1][temp_w]==INF){
            distance[temp_h+1][temp_w]=distance[temp_h][temp_w]+1;
            hw n;
            n.first=temp_h+1;
            n.second=temp_w;
            que.push(n);
        }
        
        if(s[temp_h][temp_w-1]=='.' && distance[temp_h][temp_w-1]==INF){
            distance[temp_h][temp_w-1]=distance[temp_h][temp_w]+1;
            hw n;
            n.first=temp_h;
            n.second=temp_w-1;
            que.push(n);
        }
        
        if(s[temp_h][temp_w+1]=='.' && distance[temp_h][temp_w+1]==INF){
            distance[temp_h][temp_w+1]=distance[temp_h][temp_w]+1;
            hw n;
            n.first=temp_h;
            n.second=temp_w+1;
            que.push(n);
        }
    }
    
    
    
    if(distance[H][W]==INF){
        cout<<-1<<endl;
        return 0;
    }
    
    
    cout<<white-distance[H][W]-1<<endl;
    
    
    return 0;
}


Measured memory_bytes: 384