akhauriyash/Code-Regression huggingface dataset:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    T = [400, 600, 800, 1000, 1200, 1400, 1600, 1800]
    i = bisect.bisect_right(T, N)
    print(9 - i)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9704
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

#define INF 999999999

int map[52][52];
bool ch[52][52];
int ans;

void dfs(int map[52][52], bool c[52][52], int x, int y){
	//cout << x << " " << y << " " << ans << endl;
	c[x][y] = 1;
	if(map[x-1][y]==1 && c[x-1][y]==0) dfs(map,c,x-1,y);
	if(map[x-1][y-1]==1 && c[x-1][y-1]==0) dfs(map,c,x-1,y-1);
	if(map[x-1][y+1]==1 && c[x-1][y+1]==0) dfs(map,c,x-1,y+1);
	if(map[x+1][y]==1 && c[x+1][y]==0) dfs(map,c,x+1,y);
	if(map[x+1][y-1]==1 && c[x+1][y-1]==0) dfs(map,c,x+1,y-1);
	if(map[x+1][y+1]==1 && c[x+1][y+1]==0) dfs(map,c,x+1,y+1);
	if(map[x][y-1]==1 && c[x][y-1]==0) dfs(map,c,x,y-1);
	if(map[x][y+1]==1 && c[x][y+1]==0) dfs(map,c,x,y+1);
}

int main(){
	int i, j, w, h;
	while(1){
		cin >> w >> h;
		if(!w) break;
		for(i=0;i<=h+1;i++){
			for(j=0;j<=w+1;j++){
				if(i==0||i==h+1||j==0||j==w+1)map[i][j]=0;
				else cin >> map[i][j];
				ch[i][j] = 0;
			}
		}
		ans = 0;
		for(i=1;i<=h;i++){
			for(j=1;j<=w;j++){
				if(map[i][j]&&!ch[i][j]){
					dfs(map,ch,i,j);
					ans++;
				}
			}
		}
		
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1500
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
//const long long MOD = 998244353LL;
const long long INF_LL = 1e18+3; const int INF_int = 1e9+3;
#define ll long long
#define rep(i,n) for(int i = 0;i<n;i++)
#define lrep(i,n) for(long long i = 0;i<n;i++)
#define All(a) a.begin(),a.end()
#define Debug_Output_ALL(a) for(auto itr = a.begin();itr!=a.end();itr++) cout << *itr << " ";cout << endl;
#define pii pair<int,int>
//aのMODbでの逆元
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int main(){
    int n;
    cin >> n;
    vector<int> edge[n+1];
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    bool visited[n+1];
    fill_n(visited,n+1,false);
    ll ans = 1;
    lrep(i,n){
        ans*=(i+1);
        ans%=MOD;
    }
    queue<int> que;
    que.push(1);
    vector<int> rank[n+1];
    rank[0].push_back(1);
    int rank_n[n+1];
    rank_n[1]=0;
    while(!que.empty()){
        int now = que.front();
        visited[now]=true;
        que.pop();
        rep(i,edge[now].size()){
            int to = edge[now][i];
            if(!visited[to]){
                rank_n[to]=rank_n[now]+1;
                rank[rank_n[to]].push_back(to);
                //cout << to << " " << rank_n[to] << endl;
                que.push(to);
            }
        }
    }
    fill_n(visited,n+1,false);
    vector<ll> meu;
    rep(i,n+1) meu.push_back(0);
    //cout << rank[0].size() << endl;
    for(int i = n-1;i>=0;i--){
        rep(j,rank[i].size()){
            int now = rank[i][j];
            meu[now]++;

            ans*=modinv(meu[now],MOD);
            ans%=MOD;

            visited[now]=true;
            rep(k,edge[now].size()){
                int to = edge[now][k];
                if(!visited[to]){
                    meu[to]+=meu[now];
                    //cout << to << " " << meu[to] << endl;
                } 
            }
           // cout << j << endl;
        }
        //cout << i << endl;
    }
    ll ansvec[n+1];
    ansvec[1]=ans;
    stack<pii> stk;
    stk.push(make_pair(1,-1));
    fill_n(visited,n+1,false);
    //Debug_Output_ALL(meu);
    while(!stk.empty()){
        pair<int,int> noww = stk.top();
        int now = noww.first;
        int from = noww.second;
        if(now!=1){
            ll tmpans = ansvec[from];
            tmpans *= meu[now];
            tmpans%=MOD;
            tmpans *= modinv(n-meu[now],MOD);  
            tmpans%=MOD; 
            ansvec[now]=tmpans;   

        }
        visited[now]=true;
        stk.pop();
        rep(i,edge[now].size()){
            int to = edge[now][i];
            if(!visited[to]){
                stk.push(make_pair(to,now));
            }
        }
    }
    rep(i,n){
        cout << ansvec[i+1] << endl;
    }
}

Measured memory_bytes: 25200
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

	static Scanner scanner;
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int x=gi();
	    int y=gi();
	    
	    int xa =0;
	    int ya =0;
	    if (x==2) {
	    	xa=1;
	    } else if (x==4 || x==6 || x==9 || x==11) {
	    	xa=2;
	    }
	    
	    if (y==2) {
	    	ya=1;
	    } else if (y==4 || y==6 || y==9 || y==11) {
	    	ya=2;
	    }


        //System.out.println(c);
        if (xa==ya) {
        	System.out.print("Yes");
        }else{
            System.out.print("No");
        }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}
}

Measured memory_bytes: 35600
while True:
  a = int(input())
  if a ==0: break
  hoge=1
  for i in range(1,a+1):
    hoge*=i
  hoge=str(hoge)
  ans=0
  for i in range(len(hoge)-1,0,-1):
    if hoge[i] =='0':
      ans+=1
    else: break
  print ans

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

#define ALL(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;

ll mod = 1e9 + 7;

vector<vi> memo(100123, vi(2));
vector<vi> adj(100123);

void dfs(int u, int p) {
	if(memo[u][0]) {
		return;
	}

	ll black = 1, white = 1;
	for(int v : adj[u]) {
		if(v != p) {
			dfs(v, u);
			black *= memo[v][1]; black %= mod;
			white *= memo[v][1] + memo[v][0]; white %= mod;
		}

	}

	memo[u][0] = black;
	memo[u][1] = white;
}

void solve(void) {

	int n;
	cin >> n;

	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(1, 0);
	ll ans = (memo[1][1] + memo[1][0]) % mod;
	cout << ans << '\n';
}

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


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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9


int main(){
  int N, A;
  cin >> N >> A;
  vector<int> x(N+1);
  REP(i, N){
    cin >> x[i+1];
  }

  vector<vector<vector<ll>>> dp(51, vector<vector<ll>>(51, vector<ll>(52*51, 0)));
  // REP(i, N+1){
  //   dp[i][0] = 1;
  // }
  REP(i, N+1)  dp[i][0][0] = 1;
  dp[0][0][0] = 1;
  FOR(i, 1, N+1){
    FOR(j, 1, i+1){
      FOR(k, 0, A*(N+1)+1){
        if(i > j){
          dp[i][j][k] += dp[i-1][j][k];
        }
        dp[i][j][k+x[i]] += dp[i-1][j-1][k];
        //cout << "i:" << i << " j:" << j << " k:" << k << " " << dp[i][j][k] << endl;
      }
    }
  }
  // REP(i, N+1){
  //   REP(j, i+1){
  //     REP(k, A*(N+1)+1){
  //       cout << "i:" << i << " j:" << j << " k:" << k << " " << dp[i][j][k] << endl;
  //     }
  //   }
  // }
  // FOR(i, 1, N+1){
  //   FOR(j, 1, i+1){
  //     FOR(k, 0, A*(N+1)+1){
  //       if(i > j){
  //         dp[i][j][k]+= dp[i-1][j][k];
  //       }
  //       if(k-x[i] >= 0){
  //         dp[i][j][k] += dp[i-1][j-1][k-x[i]];
  //       }
  //     }
  //   }
  // }

  ll ans = 0;
  FOR(i, 1, N+1){
      ans += dp[N][i][A*i];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 55296
#include <bits/stdc++.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FOR_RE(i,a,b) for(int i = (a); i > (b); --i)
#define rep(i,n) FOR(i,0,n)

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;
int n;

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

    int h, w;
    cin >> h >> w;    
    string board[h];

    rep(i, h)   cin >> board[i];
    //cout << board[0] << endl;
    //cout << board[0][0] << endl;
    
    const int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    const int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    
    rep(i, h){
        rep(j, w){
            int count = 0;
            if(board[i][j] != '#'){
                rep(k, 8){
                    int col = i + dy[k];
                    int row = j + dx[k];
                    if(0 <= col && col <= h - 1 && 0 <= row && row <= w - 1){
                        if(board[col][row] == '#'){
                            count++;
                        }   
                    }
                }
                cout << count;
            }else{
                cout << '#';
            }
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int l, r, d;
  cin >> l;
  cin >> r;
  cin >> d;
  
  int count = 0;
  
  for(int i=l; i<=r; i++){
    if(i%d == 0)count++;
  }

  cout << count << endl;
  return 0; 
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int inf = 100100100;

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

  int tot = 0;
  for(int i = 1; i <=n; i++){
    tot += l+i-1;
  }

  int cnt = 1;
  int mn = inf;
  for(int i = 1; i <=n; i++){
    //int d = tot - (tot - (l+i-1));
    int d = 0;
    for(int j = 1; j <=n; j++){
      if(j == i) continue;
      d += l+j-1;
    }
    if(mn > abs(tot - d)){
      mn = abs(tot-d);
      cnt = i;
    }
  }
  cout << tot - (l+cnt-1) << endl;
    
}


Measured memory_bytes: 3644
// AOJ DSL_2_C Range Search (kD Tree)
// 2018.5.17 bal4u

#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in()
{
	int n = 0, c = gc();
	if (c == '-') { c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(int n)
{
	int i;
	char ob[20];

	if (!n) pc('0');
	else {
		i = 0; while (n) ob[i++] = n%10 + '0', n/=10;
		while (i--) pc(ob[i]);
	}
	pc('\n');
}

#define MAX_N  500005

typedef struct { int id; int p[2], child[2], min[2], max[2]; } NODE;
NODE kdTree[MAX_N];

int root;       // root of kd tree
int ans[102], len;
int s[2], t[2];

int mkKdTree(int l, int r, int k)
{
	int i, j, c;
	int m, x;
	NODE t;

	m = (l+r)>>1;
	t = kdTree[m], kdTree[m] = kdTree[r], kdTree[r] = t;
	i = l-1, x = kdTree[m].p[k];
	for (j = l; j < r; j++) {
		if (kdTree[j].p[k] < x) {
			if (++i != j) t = kdTree[++i], kdTree[i] = kdTree[j], kdTree[j] = t;
		}
	}
	t = kdTree[m], kdTree[m] = kdTree[r], kdTree[r] = t;

	kdTree[m].child[0] = (l == m)? 0: mkKdTree(l, m-1, k);
	kdTree[m].child[1] = (m == r)? 0: mkKdTree(m+1, r, k);

	for (i = 0; i < 2; i++) {
		kdTree[m].min[i] = kdTree[m].max[i] = kdTree[m].p[i];
		for (j = 0; j < 2; j++) if (c = kdTree[m].child[j]) {
			if (kdTree[m].min[i] > kdTree[c].min[i]) kdTree[m].min[i] = kdTree[c].min[i];
			if (kdTree[m].max[i] < kdTree[c].max[i]) kdTree[m].max[i] = kdTree[c].max[i];
		}
	}
	return m;
}

void printRange(int node)
{
	int c;

	if (kdTree[node].p[0] >= s[0] && kdTree[node].p[0] <= t[0] &&
		kdTree[node].p[1] >= s[1] && kdTree[node].p[1] <= t[1]) {
		ans[len++] = kdTree[node].id;
	}

	if ((c = kdTree[node].child[0]) &&
		kdTree[c].min[0] <= t[0] && s[0] <= kdTree[c].max[0] &&
		kdTree[c].min[1] <= t[1] && s[1] <= kdTree[c].max[1])
			printRange(c);

	if ((c = kdTree[node].child[1]) &&
		kdTree[c].min[0] <= t[0] && s[0] <= kdTree[c].max[0] &&
		kdTree[c].min[1] <= t[1] && s[1] <= kdTree[c].max[1])
			printRange(c);
}

int kdcmp(NODE *a, NODE *b) { if (a->p[0]-b->p[0]) return a->p[0]-b->p[0]; return a->p[1]-b->p[1]; }
int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int main()
{
	int n, q, i;

	n = in();
	for (i = 1; i <= n; i++) {
		kdTree[i].id = i-1, kdTree[i].p[0] = in(), kdTree[i].p[1] = in();
	}
	qsort(kdTree+1, n, sizeof(NODE), kdcmp);
	root = mkKdTree(1, n, 0);

	q = in();
	while (q--) {
		s[0] = in(), t[0] = in();
		s[1] = in(), t[1] = in();
		len = 0;
		printRange(root);
		qsort(ans, len, sizeof(int), cmp);
		for (i = 0; i < len; i++) out(ans[i]);
		pc('\n');
	}
}


Measured memory_bytes: 26200
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

/**
 * 課題C1
 *
 * @author ken2
 */
public class Main {

	/** 天気：晴れ */
	private static final String WATHER_SUNNY = "Sunny";
	/** 天気：曇り */
	private static final String WATHER_CLOUDY = "Cloudy";
	/** 天気：飴 */
	private static final String WATHER_RAINY = "Rainy";

	/**
	 * メイン処理

	 * @param args 起動引数
	 */
	public static void main(String[] args) {

		// 標準入力から今日の天気を取得
		String today = scanTodayWeather(System.in);

		// 標準出力へ明日の天気を出力
		String tomorrow = predictTomorrowWeather(today);
		System.out.println(tomorrow);
	}

	/**
	 * 今日の天気を取得
	 *
	 * @param in 入力ストリーム
	 * @return 今日の天気
	 */
	private static String scanTodayWeather(InputStream in) {
		String today = null;
		try {
			InputStreamReader isr = new InputStreamReader(in);
			BufferedReader br = new BufferedReader(isr);
			today = br.readLine();
			br.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return today;
	}

	/**
	 * 今日の天気から明日の天気を予測
	 * ・晴れ→曇り
	 * ・曇り→雨
	 * ・雨→晴れ
	 *
	 * @param today 今日の天気
	 * @return 明日の天気
	 */
	private static String predictTomorrowWeather(String today) {
		String tomorrow = null;
		if (today.equals(WATHER_SUNNY)) {
			tomorrow = WATHER_CLOUDY;
		} else if (today.equals(WATHER_CLOUDY)) {
			tomorrow = WATHER_RAINY;
		} else if (today.equals(WATHER_RAINY)) {
			tomorrow = WATHER_SUNNY;
		}
		return tomorrow;
	}
}


Measured memory_bytes: 20180
//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
#define ll long long
#define inf 20021225
#define N 1000010
using namespace std;
int read()
{
	int s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
char ch[N],s[N]; int n;
int pre[N],nxt[N],cnt[3];
set<int> pos[3]; int id[3];
void modify(int x)
{
	if(!x||x>n)	return;
	if(s[pre[x]]==s[nxt[x]])
	{
		if(pos[s[x]-'A'].find(x)!=pos[s[x]-'a'].end())	pos[s[x]-'A'].erase(x);
	}
	else	pos[s[x]-'A'].insert(x);
}
void del(int x)
{
	if(pos[s[x]-'A'].find(x)!=pos[s[x]-'A'].end()) pos[s[x]-'A'].erase(x);
	pre[nxt[x]]=pre[x],nxt[pre[x]]=nxt[x];
	modify(pre[x]); modify(nxt[x]);
}
bool cmp(int x,int y){return cnt[x]<cnt[y];}
int main()
{
	scanf("%s",ch+1); int nn=0; n=strlen(ch+1);
	for(int i=1;i<=n;i++)	if(ch[i]!=ch[i-1])
		s[++nn]=ch[i];
	n=nn; nxt[0]=1; pre[n+1]=n;
	for(int i=1;i<=n;i++)
	{
		cnt[s[i]-'A']++;
		pre[i]=i-1,nxt[i]=i+1;
		if(s[i-1]!=s[i+1])	pos[s[i]-'A'].insert(i);
	}
	int mn=0,mx=0,mid=0;
	id[0]=0,id[1]=1,id[2]=2;
	sort(id,id+3,cmp);
	mn=id[0],mx=id[2],mid=id[1];
	if(cnt[mid]!=cnt[mx])
	{
		while(cnt[mid]!=cnt[mx]&&!pos[mx].empty())
			del(*pos[mx].begin()),cnt[mx]--;
		
		if(cnt[mx]>cnt[mid])
		{
			int p2,p1;
			for(int i=nxt[0];i!=n+1;i=nxt[i])
			{
				p1=pre[i],p2=pre[p1];
				if(p2&&p1&&s[p2]-'A'==mn&&s[p1]-'A'==mx&&s[i]-'A'==mn)
					del(p1),del(p2),cnt[mx]--,cnt[mn]--;
				if(cnt[mx]==cnt[mid])	break;
			}
		}
	}
	if(cnt[mx]!=cnt[mid])	return 0;
	
	if(cnt[mn]!=cnt[mid])
	for(int i=nxt[0];i!=n+1;i=nxt[i])
	{
		int p1=pre[i],p2=pre[p1],n1=nxt[i];
		if(((!p2||s[p2]-'A'!=mn)||(n1==n+1||s[n1]-'A'!=mn))&&(p1&&s[p1]-'A'!=mn)&&s[i]-'A'!=mn)
			del(p1),del(i),cnt[mid]--,cnt[mx]--;
		if(cnt[mn]==cnt[mid])	break;
	}
	if(cnt[mid]==cnt[mn]&&cnt[mn]==cnt[mx])	for(int i=nxt[0];i!=n+1;i=nxt[i])
		printf("%c",s[i]);
	return 0;
}


Measured memory_bytes: 57856
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

void CountingSort(std::vector<int>& A, std::vector<int>& B, int k) {
    std::array<int, 10001> C = {};
    for (int i=0; i<k; ++i) {
        C[A[i]]++;
        B.push_back(-1);
    }
    
    for (int i=1; i<=10001; ++i) {
        C[i] += C[i-1];
    }
    
    for (int i=k-1; i>=0; --i) {
        B[C[A[i]]-1] = A[i];
        C[A[i]]--;
    }
}

int main() {
    int N, temp;
    std::cin >> N;
    
    std::vector<int> A, B;
    for (int i=0; i<N; i++) {
        std::cin >> temp;
        A.push_back(temp);
    }
    
    CountingSort(A, B, N);
    
    for (auto i=B.begin(); i!=B.end(); i++) {
        std::cout << *i;
        if (std::next(i, 1) != B.end()) {
            std::cout << " ";
        } else {
            std::cout << std::endl;
        }
    }
}


Measured memory_bytes: 22940
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll v):v(normS(v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll u[]={a,1,0},v[]={b,0,1};
		while(*v){
			ll t=*u/ *v;
			rep(i,3) swap(u[i]-=t*v[i],v[i]);
		}
		if(u[0]<0) rep(i,3) u[i]=-u[i];
		x=u[1],y=u[2];
		return u[0];
	}
	ModInt inv() const{
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<1000000007>;
int main(){
	int N;
	cin>>N;
	vector<mint> inv(N+1);
	rep1(i,N) inv[i] = mint(1)/i;
	vector<mint> acc(N+1);
	rep1(i,N) acc[i] = acc[i-1] + inv[i];
	mint ans = 0;
	rep(i,N){
		ll c;
		cin>>c;
		ans += (acc[i+1]+acc[N-i]-1)*c;
	}
	rep1(i,N) ans *= i;
	cout<<ans<<endl;
}

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

E = [[] for _ in range(n+1)]
for i in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai-=1;bi-=1
    E[ai].append((bi,-ci))
#「nまでの経路で」負閉路が要る
#https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
# V: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
dist = [INF] * n
dist[0] = 0
update = 1
for _ in range(n):
    update = 0
    for v, e in enumerate(E):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break

ans = dist[n-1]


for _ in range(n):
    update = 0
    for v, e in enumerate(E):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
if ans > dist[n-1]:
    print("inf")
else:
    print(-ans)###-



Measured memory_bytes: 51160
#include <iostream>

using namespace std;

int main() {
	int a, b, k, m;
	int c = 0, ans = 0;

	cin >> a >> b >> k;

	a < b ? m = a : m = b;

	for (int i = m; i > 0; i--) {
		if (a%i == 0 && b%i == 0) {
			++c;
			if (c == k) {
				ans = i; break;
			}
		}
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
typedef long long ll;
using namespace std;

int main() {
	ll maki,sophia=0;
	cin>>maki;
	ll niko[maki];
	for(int i=0;i<maki;i++){
		cin>>niko[i];
	}
	sort(niko,niko+maki);
	reverse(niko,niko+maki);
	for(int i=0;i<maki;i++){
		if(i%2==0){
			sophia+=niko[i];
		}
		else{
			sophia-=niko[i];
		}
	}
	cout << sophia<<endl;
	return 0;
}


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

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int modd = 1e9 + 9;
const int X = 1000003;
const int XX = 1000007;
typedef long long ll;
#define mp make_pair


char c;
string s;
ll n,i,t,tt,a,b,aa,bb,x,xx,bol=1,boll=1,ans;
map < pair < int , int > , int > M;

int main(){
    cin >> n >> s;
    for(t=X,i=mod-2; i ; i>>=1){
        if(i & 1) bol = bol*t % mod;
        t = t*t % mod;
    }
    for(t=XX,i=modd-2; i ; i>>=1){
        if(i & 1) boll = boll*t % modd;
        t = t*t % modd;
    }

    for(i=n-1; i>=0 ;i--){
        c = s[i];
        if(c == '+') xx++;
        if(c == '-') xx--;
        if(c == '>') xx *= XX;
        if(c == '<') xx *= boll;
        xx = (xx % modd + modd) % modd;
        if(c == '-') x--;
        if(c == '+') x++;
        if(c == '>') x *= X;
        if(c == '<') x *= bol;
        x = (x % mod + mod) % mod;
    }

    a = 1; b = 0;
    aa = 1;
    M[mp(0,0)] = 1;
    for(i=n-1; i>=0 ;i--){
        c = s[i];
        if(c == '+') b -= a, bb -= aa;
        if(c == '-') b += a, bb += aa;
        if(c == '>') a *= bol, aa *= boll;
        if(c == '<') a *= X, aa *= XX;
        a = (a % mod + mod) % mod;
        b = (b % mod + mod) % mod;
        aa = (aa % modd + modd) % modd;
        bb = (bb % modd + modd) % modd;


        t = (a*x + b) % mod;
        tt = (aa*xx + bb) % modd;

        ans += M[mp(t,tt)];
        M[mp(b,bb)]++;
    }

    cout << ans;
    return 0;
}

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

const int INF = 1e7;
array<int, 4> dx = {-1, 0, 1, 0};
array<int, 4> dy = {0, -1, 0, 1};


int arr[1001][1001];

void solve() {
    int H, W, Ch, Cw, Dh, Dw;
    cin >> H >> W >> Ch >> Cw >> Dh >> Dw;
    Ch--; Cw--; Dh--; Dw--;
    vector<string> v(H);
    for (auto& s : v) cin >> s;

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            arr[i][j] = INF;
        }
    }
    arr[Ch][Cw] = 0;

    deque<pair<int, int>> Q;
    Q.push_front({Ch, Cw});

    while (!Q.empty()) {
        const pair<int, int>& p = Q.front();
        Q.pop_front();
        int first = p.first;
        int second = p.second;

        int steps = arr[first][second];
        //if (steps < cost) continue;

        // All UP, DOWN, LEFT, RIGHT
        for (int i = 0; i < (int)dx.size(); ++i) {
            int x = first + dx[i];
            int y = second + dy[i];
            if (x >= 0 && x < H && y >= 0 && y < W && v[x][y] == '.') {
                if (arr[x][y] > steps)
                    Q.push_front({x, y});
                arr[x][y] = min(arr[x][y], steps);
            }
        }

        for (int i = -2; i <= 2; ++i) {
            int x = first + i;
            for (int j = -2; j <= 2 && x >= 0 && x < H; ++j) {
                int y = second + j;
                if (y < 0 || y >= W || v[x][y] == '#') continue;
                if (arr[x][y] > steps + 1)
                    Q.push_back({x, y});
                arr[x][y] = min(steps + 1, arr[x][y]);
            }
        }
    }
    if (arr[Dh][Dw] >= INF) cout << -1 << "\n";
    else cout << arr[Dh][Dw] << "\n";
}

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

    int t = 1;
    while(t--) {
        solve();
    }
}


Measured memory_bytes: 8744
#include <cstdio>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main() {
    int N, A;
    cin >> N >> A;
    if (N % 500 <= A) {
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
n,h=map(int,input().split())
ab=[[int(i) for i in input().split()] for _ in range(n)]
maxa=max(map(lambda x:x[0], ab))
ab.sort(key=lambda x:x[1],reverse=True)
ans=0
for a,b in ab:
  if b>maxa:
    h-=b
    ans+=1
  if h<=0:
    print(ans)
    exit(0)
print(ans+(h-1)//maxa+1)


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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO  cout << "NO"  << endl
#define No  cout << "No"  << endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;

ll gcd(ll a, ll b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

void solve()
{
    ll N; cin >> N;
    ll ans = 0;
    ll T0, A0; cin >> T0 >> A0;
    ans = T0+A0;
    REP1(i, N-1)
    {
        ll T, A; cin >> T >> A; 
        ll S = max((T0+T-1)/T, (A0+A-1)/A);
        T *= S; A *= S;
        T0 = T; A0 = A;
        ans = T0+A0;
    }
    cout << ans << endl;
}
    
int main() 
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 256
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n <- getInt
    ds <- getIntList
    print $ solve ds

solve [] = 0
solve (d:ds)
    | d /= 0 || map head ds' /= [1..length ds'] = 0
    | otherwise = productMod $ zipWith powerMod ds'' (tail ds'')
    where ds' = group $ sort ds
          ds'' = map length ds'

moduloN :: Int
moduloN = 998244353
modN = flip mod moduloN

mulMod x y = modN $ x * y
productMod xs = foldl' mulMod 1 xs

powerMod x 0 = 1
powerMod x y
    | even y = mulMod t t
    | otherwise = mulMod x $ mulMod t t
    where
        t = powerMod x $ div y 2

Measured memory_bytes: 22012
import java.util.Scanner;

public class Main {

	public static void main(final String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next(), t = sc.next();
		int r = 0;
		for (int i=0;i<s.length();i++) {
			if (s.charAt(i) != t.charAt(i)) ++r;
		}
		System.out.println(r);
	}
}


Measured memory_bytes: 40972
import math
import sys

def merge(nums, left, mid, right):
    sentiel = sys.maxsize

    lefts = [nums[left+i] for i in range(mid - left)]
    lefts.append(sentiel)

    rights = [nums[mid+i] for i in range(right - mid)]
    rights.append(sentiel)

    l = 0
    r = 0
    cnt = 0

    for k in range(left, right):
        if lefts[l] <= rights[r]:
            nums[k] = lefts[l]
            l += 1
        else:
            nums[k] = rights[r]
            r += 1
        cnt += 1

    return nums, cnt

def mergeSort(nums, left, right):
    if right - left <= 1:
        return nums, 0

    mid = left + math.ceil((right - left)/2)

    nums, cntl = mergeSort(nums, left, mid)
    nums, cntr = mergeSort(nums, mid, right)

    nums, cnt  = merge(nums, left, mid, right)

    return nums, cnt+cntl+cntr

def main():
    n = int(input())
    nums = [int(x) for x in input().split(' ')]

    snums, cnt = mergeSort(nums, 0, n)

    print(' '.join([str(x) for x in snums]), cnt, sep="\n")

if __name__ == '__main__':
    main()



Measured memory_bytes: 74580
n, k = map(int, input().split())                            
array = list(map(int, input().split()))
 
def jadgesuruo():
    for i in range(k):
        if str(n).find(str(array[i])) >= 0:
            return False
            break
    return True
 
for i in range(10**5):
    if jadgesuruo():
        print(n)
        break
    else:
        n = n + 1


Measured memory_bytes: 2940
import java.io.*;
import java.util.StringTokenizer;
 
class Main {
    public static void main(String args[]) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    try {
        int n = Integer.parseInt(br.readLine());
        for (int i=0;i<n;i++) {
        Double x[] = new Double[4];
        Double y[] = new Double[4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j=0;j<4;j++) {
            x[j] = Double.parseDouble(st.nextToken());
            y[j] = Double.parseDouble(st.nextToken());
        }
        Double vx[] = new Double[2];
        Double vy[] = new Double[2];
        vx[0] = x[1]-x[0];
        vx[1] = x[3]-x[2];
        vy[0] = y[1]-y[0];
        vy[1] = y[3]-y[2];
        if (parallelism(vx[0],vy[0],vx[1],vy[1])) System.out.println("YES");
        else System.out.println("NO");
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
    }
 
    public static boolean parallelism(Double x1,Double y1,Double x2,Double y2) {
        if (Math.abs(Math.round(Math.pow(100000,2)*(x1*y2-x2*y1)))==0.0) return true;
    else return false;
    }
}

Measured memory_bytes: 24428
# B問題
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
flag = False
count = 0
tmp = 1
for i in range(N):
    tmp = a[tmp-1]
    count += 1
    if tmp == 2:
        flag = True
        break
if flag:
    print(count)
else:
    print(-1)

Measured memory_bytes: 7084
#include<iostream>
#include<vector>
#include<set>
using ll =  long long;

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

using namespace std;

int main(){

    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int cnt=0;
    rep(i,a+1)rep(j,b+1)rep(k,c+1){
        if(500*i+100*j+50*k==x)
            cnt++;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args){
    int k;
    String str = "ACL";
    String result = "";
    Scanner sc = new Scanner(System.in);
 	
    k = sc.nextInt();
    
    for(int i = 1; i <= k; i++){
    	result = result + str;
    }
    
    System.out.println(result);
  }
}

Measured memory_bytes: 26976
#include <stdio.h>

void sort(int array[])
{
	int i, j;
	
	for (i = 0; i < 5 - 1; i++){
		for (j = 0; j < 5 - i - 1; j++){
			if (array[j] > array[j + 1]){
				int tmp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = tmp;
			}
		}
	}
}

int main(void)
{
	int i;
	int card[5];
	
	while (scanf("%d", &card[0]) != EOF){
		int count[5] = {0};
		int s_flag = 1;
		int null_flag = 1;
		
		for (i = 1; i < 5; i++){
			scanf(",%d", &card[i]);
		}
		sort(card);
		
		for (i = 0; i < 5; i++){
			int j;
			
			for (j = 0; j < i; j++){
				if (card[i] == card[j]){
					count[j]++;
					if (count[j] > 1){
						null_flag = 0;
						s_flag = 0;
					}
					break;
				}
			}
			if (j == i){
				count[i]++;
			}
			if (i != 0 && card[i - 1] + 1 != card[i]){
				if (card[i - 1] != 1){
					s_flag = 0;
				}
			}
		}
		for (i = 0; i < 5; i++){
			int j;
			if (s_flag == 1){
				puts("straight");
				break;
			}
			else if (count[i] == 4){
				puts("four card");
				break;
			}
			else if (count[i] == 3){
				for (j = 0; j < 5; j++){
					if (count[j] == 2){
						puts("full house");
						i = 6;
						break;
					}
				}
				if (i != 6){
					puts("three card");
					break;
				}
			}
			else if (count[i] == 2){
				for (j = 0; j < 5; j++){
					if (count[j] == 3){
						puts("full house");
						i = 6;
						break;
					}
					else if (j != i && count[j] == 2){
						puts("two pair");
						i = 6;
						break;
					}
				}
				if (i != 6){
					puts("one pair");
					break;
				}
			}
			if (count[i] > 1){
				null_flag = 0;
			}
		}
		if (null_flag == 1 && s_flag == 0){
			puts("null");
		}
	}
	
	return 0;
}

Measured memory_bytes: 580
import math
MAX = 1000000
A = [1]*MAX

for i in range(2,int(math.sqrt(MAX))+1):
    if A[i]==1:
        for j in range(2*i,MAX,i):
            A[j]=0
A[0]=0
A[1]=0
for i in range(1,MAX):
    A[i] += A[i-1]

while True:
    try:
        n = int(input())
    except:
        break
    print(A[n])


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

#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ll long long
#define ld long double
#define pb push_back
#define MOD 1000000007
#define LLMN LONG_LONG_MIN
#define LLMX LONG_LONG_MAX
#define LDMX LDBL_MAX
#define LDMN LDBL_MIN
#define MAX 1000003
#define pll pair<ll, ll>
#define vl vector<ll>
#define vll vector< vector<ll> >

ll mulmod(ll, ll);
ll fastpower(ll, ll);
void getprime(vector<bool>&);
void getfact(vector<ll>&, vector<ll>&);
ll ncr(ll, ll, vector<ll>&, vector<ll>&);

void solve()
{
    ll n, m, k;
    cin>>n;
    m = n + n*n + n*n*n;
    cout<<m;   
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll t = 1;
    //cin>>t;
    while(t--)
    {
        solve();        
    }
    return 0;
}

ll mulmod(ll a, ll b)
{
    ll res = 0; 
    a = a % MOD;
    while(b > 0)
    {
        if (b % 2 == 1)
            res = (res + a) % MOD;
 
        a = (a * 2) % MOD; 
        b /= 2;
    } 
    return res % MOD; 
}

ll  fastpower(ll a, ll n)
{
    ll res = 1;
    while(n > 0)
    {
        if(n % 2 != 0)
        {
            res = (res * a) % MOD;
        }
        n /= 2;
        a = (a * a) % MOD;
    }
    return res;
}

void getprime(vector<bool>&prime)
{
    prime[0] = false;
    prime[1] = false;
    
    for(ll i = 2;i <= MAX; i++)
    {
        if(prime[i])
        {
            for(ll j = i*i; j <= MAX; j += i)
                prime[j] = false;
        }
    }
}

void getfact(vector<ll> &fact, vector<ll> &ifact)
{
    fact[0] = 1;
    ifact[0] = 1;
    
    for(ll i = 1; i <= MAX; i++)
    {
        fact[i] = (fact[i-1] * i)%MOD;
        ifact[i] = (ifact[i-1] * fastpower(i, MOD -2) )%MOD;
    }
}

ll ncr(ll n, ll r, vector<ll>&fact, vector<ll>&ifact)
{
    ll res;
    res = (((fact[n] * ifact[r]) % MOD) * ifact[n-r]) % MOD;
    return res;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll ans=0;
    ll n;
    cin>>n;
    ans=n*500;
    ll x;
    cin>>x;
    if(ans>=x){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
}

Measured memory_bytes: 256
#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>
#define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
#define REPN(i,n) for(int(i)=1;(i)<(int)(n);(i)++)
#define _abs(x) ((x)>0?(x):-(x))
#define ll  long long 
using namespace std;   
int main()
{
    int n;
    cin>>n;
    double a[n];
    REP(i,n)
    {
        cin>>a[i];
    }
    double ans=0;
    sort(a,a+n);
    double s=a[0]+a[1];
    s/=2;
    for(int i=2;i<n;i++)
    {
        s=(s + a[i])/2;
    }
    cout<<s<<endl;
    return 0;
} 

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author indy256
 */

#include <bits/stdc++.h>

using namespace std;

void solve(istream &in, ostream &out) {
    int n, m;
    in >> n >> m;
    string s;
    in >> s;

    vector<int> res;
    bool ok = true;
    for (int i = n; i >= 0;) {
        if (s[i] == '1') {
            ok = false;
            break;
        }
        if (i == 0)
            break;
        int j = i;
        int cnt = m;
        int pi = i;
        bool found = false;
        while (cnt > 0 && j > 0) {
            --j;
            --cnt;
            if (s[j] == '0') {
                i = j;
                found = true;
            }
        }
        if (!found) {
            ok = false;
            break;
        }
        res.emplace_back(pi - i);
    }

    if (!ok) {
        out << -1 << '\n';
    } else {
        reverse(res.begin(), res.end());
        for (auto x:res)out << x << ' ';
        out << '\n';
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solve(in, out);
}


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

int main() {
  int n;
  cin >> n;
  bool jug = false;
  for (int i = 1; i < 10; i++) {
    for (int j = 1; j < 10; j++) {
      if (i * j == n) {
        jug = true;
      }
    }
  }
  if (jug) {
    cout << "Yes" << endl;
  } 
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3592
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/
#include<bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))
#define INF 0x3f3f3f3f
#define Min 1e-6
#define lowbit(x) ((x)&(-x))
#define ls rt<<1
#define rs rt<<1|1
#define ll int

using namespace std;

const int N = 2e5 + 7;
const int M = 1e9 + 7;
const ll Mod = 1e9 + 7;

int i,j,n,m,t,T,p,l,r,q,len,len1,v,u,k,w,st,res,cnt,ans,tmp,nex,a[N];
string s;

int main()
{
    ios::sync_with_stdio(false);
    mem(a);
    cin >> s;
    len = s.size();
    for(i = 0;i < len/2;i++){
        if(s[i] != s[len-i-1]){
            cout << "No";
            return 0;
        }
    }
    for(i = 0;i < len/4;i++){
        if(s[i] != s[len/2-i-1]){
            cout << "No";
            return 0;
        }
    }
    for(i = (len+3)/2-1;i < len;i++){
        if(s[i] != s[len+(len+3)/2-2-i]){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}



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

const int MOD = 1000000007;

int main() {
  string s;
  cin >> s;
  
  //cout << s.at(s.size()-1) << endl;
  if(s.at(s.size()-1) == 's') {
    cout << s << "es" << endl;
  } else {
    cout << s << "s" << endl;
  }

}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
struct edge { ll s, t, x; };
typedef pair<ll, ll> P;
typedef pair<ll,P> event;
const ll MAX = 510000;
const ll MOD = 1000000007;
#define INF (ll)1000000000000

vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}

int main() {
  ll N;
  cin>>N;
  ll ans=0ll;
  for(int i=1;i<=N;i++){
    ll t=N/i;
    ll g=1ll;
    g*=t*(t+1ll);
    g/=2ll;
    g*=i;
    ans+=g;
  }
  cout<<ans;
}


Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>

using namespace std;
using ll = long long;

int main()
{
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        vector<int> num(100, 0);
        int fin = 1000000;
        int maxind = 0;
        for (int i = 0; i < n; i++) {
            const int rest = n - i - 1;
            char C;
            cin >> C;
            num[C - 'A']++;
            int maxind1 = -1;
            int max1 = -1;
            int maxind2 = -1;
            int max2 = -1;
            for (int i = 0; i < 100; i++) {
                if (max1 == -1) {
                    maxind1 = 0;
                    max1 = num[0];
                } else if (max2 == -1) {
                    maxind1 = (num[0] > num[1]) ? 0 : 1;
                    max1 = max(num[0], num[1]);
                    maxind2 = 1 - maxind1;
                    max2 = min(num[0], num[1]);
                } else {
                    if (num[i] >= max1) {
                        max2 = max1;
                        maxind2 = maxind1;
                        max1 = num[i];
                        maxind1 = i;
                    } else if (num[i] > max2) {
                        max2 = num[i];
                        maxind2 = i;
                    }
                }
            }
            if (max1 > max2 + rest) {
                fin = min(fin, i + 1);
                maxind = maxind1;
            }
        }
        if (fin == 1000000) {
            cout << "TIE" << endl;
        } else {
            cout << (char)(maxind + 'A') << " " << fin << endl;
        }
    }

    return 0;
}

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

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

	string ans = "No";
	int N = S.size();
	int flag = 0;
	for( int i = 0; i < N / 2; i++ ) {
		if( S[i] != S[N - i - 1] ) flag = 1;
	}
	if( flag == 0 ) {
		int n = (N - 1) /2;
		for( int i = 0; i < n / 2; i++ ) {
			if( S[i] != S[n - i - 1] ) flag = 1;
		}
		if( flag == 0 ) {
			int n = (N + 3) /2;
			for( int i = n; i < N / 2; i++ ) {
				if( S[i] != S[N - i - 1] ) flag = 1;
			}
			if( flag == 0 ) {
				ans = "Yes";
			}
		}
	}

	cout << ans << endl;
}


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

int main(){
    //freopen("input.txt", "r", stdin);
    string s, t; cin >> s >> t;
    deque < char > d;
    for(int i = 0; i < s.size(); i++){
        d.push_back( t[i] );
    }
    int count = s.size();
    int count2 = 0;
    for(int i = 0; i < s.size(); i++){
        d.push_front(d[count-1]);
        d.pop_back();
        for(int j = 0; j < s.size(); j++) {
            if (d[j] != s[j]) {
                count2++;
            }
        }
        if(count2==0){
            cout << "Yes" << endl;
            return 0;
        }else{
            count2 = 0;
        }
        //count--;
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int a,b;
	cin>>a>>b;
	int ans;
	ans=1;
	int count=0;
	while(ans<b)
	{
		ans--;
		ans=ans+a;
		count++;
	}
	cout<<count;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[17]:


N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))


# In[18]:


import collections


# In[19]:


count = collections.Counter(A)
ans = 0
for d in count.values():
    if d%2 != 0:
        ans += 1
print(ans)


# In[ ]:






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

#define rep(i,z) for(int i = 0; i<(int)(z); i++)
#define rep1(i,z) for(int i = 1; i<=(int)(z); i++)
 
using namespace std;

typedef long long ll;
const ll MOD=1e9+7;
using pear = pair<int,int>;

int main(){
  string s,t;
  cin>>s>>t;
  int sl = s.length(), tl=t.length(), ans = tl;
  for(int i = 0; i< sl-tl+1;i++){
    int now=0;
    for(int j = 0;j<tl;j++){
      if(t[j]!=s[i+j]) now++;
    }
    if(now<ans) ans=now;
  }
  cout<<ans<<endl;
}


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

using namespace std;

int main()
{	
	int n;
	cin >> n;
	vector<pair <int, int> > cost; 
	vector<vector<int>> A(n + 1, vector<int> (3, 0));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j += 1)
		
			cin >> A[i + 1][j];
	}

	vector<vector<int>> dp(n + 1, vector<int> (3, 0));

	/*
	dp[i][j] = cel mai mare cost pe care il pot obtine daca am decis activitatile
	pentru toate zilele <= i si in ziua i am facut activitatea j
	*/


	for (int i = 1; i <= n; i++) {
		
		for(int j = 0; j < 3; j++) {

			dp[i][j] = A[i][j] + max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]);
		}
	}

	int maxi = max (dp[n][0], dp[n][1]);
	maxi = max (maxi, dp[n][2]);
	cout << maxi;	
	return 0;
}


Measured memory_bytes: 11136
import itertools

n = int(input())
x = [0 for i in range(n)]
y = [0 for i in range(n)]
ans = 0

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

for l in itertools.permutations(range(n)):
  for i in range(len(l)-1):
    ans +=  ((x[l[i]]-x[l[i+1]])**2 + (y[l[i]]-y[l[i+1]])**2)**0.5

print(ans/len(list(itertools.permutations(range(n)))))

Measured memory_bytes: 8180