akhauriyash/Code-Regression huggingface dataset:
#![allow(unused)]

//入力マクロここから
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
//入力マクロここまで

//input
//use std::io::Read;

//collections
//use std::collections::BTreeMap;
//use std::collections::BTreeSet;
//use std::collections::HashMap;
//use std::collections::HashSet;
//use std::collections::VecDeque;
//use std::collections::BinaryHeap;

const INI: i64 = 1_000_000_000_000_000;
use std::cmp::*;

fn main() {
    input! {
        n: usize,
        k: usize,
        h:[i64;n],
    }

    let mut dp = vec![INI; n];
    dp[0] = 0;

    for i in 0..n {
        for j in 1..k + 1 {
            if i + j > n - 1 {
                break;
            }
            dp[i + j] = min(dp[i + j], dp[i] + (h[i] - h[i + j]).abs());
        }
    }

    println!("{}", dp[n - 1]);
}


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

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))   //最大値を求める
#define MIN(x) *min_element(ALL(x))   //最小値を求める
#define D()
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 10000007      //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素

signed main()
{
    string S,T,ans = "Yes";
    cin >> S >> T;
    REP(i,S.size()){
        if(S[i] != T[i]){
            ans = "No";
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, W, Z;
  cin >> N >> W >> Z;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
  }
  if(N == 1){
    cout << abs(vec[0] - Z) << endl;
  }
  else{ 
    cout << max(abs(vec[N-2] - vec[N-1]), abs(vec[N-1] - Z)) << endl;
  }
}

Measured memory_bytes: 3640
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include<iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<deque>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

bool ok[1111];

int main()
{
	ll n;cin >> n;
	
	vector<ll> a(n);
	vector<ll> b(n);
	
	ll tmp = 0;
	
	REP(i,n)cin >> a[i];
	REP(i,n)cin >> b[i];
	
	REP(i,n)
	{
		if(a[i] < b[i])
		{
			tmp += (b[i]-a[i])/2;
		}
		else if(a[i] > b[i])
		{
			tmp -= a[i] - b[i];
		}
	}
	
	//cout << tmp << endl;
	
	if(tmp >= 0)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
const int INF=10010010;

int zet(int a){
  if(a<0)
  a=-a;
  return a;
}

int main(){
  int n; cin>>n;
  vector<int> w(n);
  int s1=0;
  int s2=0;
  rep(i,n){
    cin>>w[i];
    s2+=w[i];
  }

  int ans=zet(s1-s2);

  rep(i,n){
    s1+=w[i];
    s2-=w[i];
    int z=zet(s1-s2);
    ans=min(ans,z);
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s; long long k;
  cin >> s >> k;
  int cnt = 0;
  while(s[cnt] == '1' && cnt < (int)s.size()) {
    cnt++;
  }
  if (cnt == 0) {
    cout << s[0] << endl;
  } else if (cnt >= k) {
    cout << 1 << endl;
  } else {
    cout << s[cnt] << endl;
  }
  return 0;
}

Measured memory_bytes: 3616
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
template <class T>
void setmax(T &a, T const &b) {
    if (a < b) a = b;
}

template <class T>
void setmin(T &a, T const &b) {
    if (a > b) a = b;
}

template <typename T, typename X>
auto vectors(T a, X x) { return vector<T>(x, a); }

template <typename T, typename X, typename Y, typename... Zs>
auto vectors(T a, X x, Y y, Zs... zs) {
    auto cont = vectors(a, y, zs...);
    return vector<decltype(cont)>(x, cont);
}

int main() {
    int N;
    long long C;
    cin >> N >> C;
    vector<long long> x(N), v(N);
    repeat(i, N) cin >> x[i] >> v[i];
    vector<long long> AnOA(N + 1, 0LL);
    vector<long long> BnOB(N + 1, 0LL);
    repeat(i, N) {
        AnOA[i + 1] = AnOA[i] + v[i] - x[i];
        if (i - 1 >= 0) AnOA[i + 1] += x[i - 1];
    }
    repeat(i, N) {
        setmax(AnOA[i + 1], AnOA[i]);
    }
    for (int i = N - 1; i >= 0; --i) {
        BnOB[i] = BnOB[i + 1] + v[i] - (C - x[i]);
        if (i + 1 <= N - 1) BnOB[i] += C - x[i + 1];
    }
    for (int i = N - 1; i >= 0; --i) {
        setmax(BnOB[i], BnOB[i + 1]);
    }
    long long B = 0;
    long long OB = 0;
    long long res = numeric_limits<long long>::min();
    for (int i = N; i >= 0; --i) {
        if (i < N) {
            B += v[i];
            OB = C - x[i];
        }
        setmax(res, B - OB - OB + AnOA[i]);
    }
    long long A = 0;
    long long OA = 0;
    for (int i = 0; i <= N; ++i) {
        if (0 < i) {
            A += v[i - 1];
            OA = x[i - 1];
        }
        setmax(res, A - OA - OA + BnOB[i]);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 6368
# 1: . , ! ? (スペース)
# 2: a b c
# 3: d e f
# 4: g h i
# 5: j k l
# 6: m n o
# 7: p q r s
# 8: t u v
# 9: w x y z
# 0: 確定ボタン

class KeitaiMessage
  @@button = {                         # 数字と文字の対応をハッシュで持っておく
    '1' => ['.',',','!','?',' '],
    '2' => [*'a'..'c'],
    '3' => [*'d'..'f'],
    '4' => [*'g'..'i'],
    '5' => [*'j'..'l'],
    '6' => [*'m'..'o'],
    '7' => [*'p'..'s'],
    '8' => [*'t'..'v'],
    '9' => [*'w'..'z'],
    '0' => ['']
  }
  def execute
    output=number2string(gets.to_i)    # 数字列を文字列に変換し、結合して返す
  end

  def number2string(n)
    output=''                           # n行分の文字列を格納
    n.times do
      input_numbers=gets.chomp.chars    # 数字列を受け取って配列に格納
      line=''                           # 1行分の文字列を格納
      push_count=0                      # ボタンを押した回数をカウント
      prev_number='0'                   # 一つ前に押された数字を持っておく
      input_numbers.each do |input_number|
        if input_number=='0'                                        # 0が押されたら文字を確定
          array_size = @@button[prev_number].size
          line+=@@button[prev_number][(push_count-1)%array_size]    # 数字列を文字に変換して末尾に追加
          push_count=0
        else
          push_count+=1                 # 0以外が押されたときは、押した回数を数える
        end
        prev_number=input_number        # 一つ前に押された数字を更新
      end
      output+=line+"\n"                 # 1行ずつoutputに追加
    end
    return output
  end
end

km=KeitaiMessage.new
puts km.execute


Measured memory_bytes: 6956
// https://atcoder.jp/contests/abc070/tasks/abc070_b

#include <bits/stdc++.h>
#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++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

int main()
{
  /* Magic word */
  // cin.tie(0);
  // ios::sync_with_stdio(false);
  /* ---------- */

  int a, b, c, d, s = 0;

  cin >> a >> b >> c >> d;

  FOR(i, min(a, c), max(b, d))
  {
    if (a <= i && i < b && c <= i && i < d)
      s++;
  }

  cout << s << '\n';

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main (void){
  int i,count;
  char a[100];
  gets(a);
  count=0;
  for(i=0;i<strlen(a);i++)
  {
      if(a[i]=='1')
      {
          count++;
      }
      
      
      
  }
  printf("%d",count);
  
   return 0;
    
}

Measured memory_bytes: 128
# イルカはプログラミングコンテスト好きで、今日はAtCoderのコンテストに参加します。
# 現在時刻は、24時間表記(0:00 〜23:59) で A時ちょうどであり、
# コンテストがちょうど B時間後に始まります。
# コンテストの開始時刻は、24時間表記で何時ちょうどでしょうか?

# 制約
# 0 ≦ A, B ≦ 23
# A, B は整数である。

# 標準入力から A時、B時を取得する
hour_a,hour_b = map(int,input().split())

# コンテストの開始時間を計算し出力する
contest_start_hour = 0  # コンテスト開始時間

contest_start_hour = hour_a + hour_b

if contest_start_hour >= 24:    # 日付変わってるよ～
    contest_start_hour -= 24

print(contest_start_hour)


Measured memory_bytes: 9068
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

set<char> s1;


int main(){
	int N =0;
	scanf("%d",&N);
	char a;
	int cnt =0;
	for(int i=0;i<N;i++){
		cin>>a;
		if(s1.count(a)==0){
			s1.insert(a);
			cnt++;
		}
	}
	if(cnt==3){
		printf("Three\n");
	}else{
		printf("Four\n");
	}
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.IOException
import java.io.InputStreamReader
import java.util.*
import kotlin.math.*

fun main() {
    var fs = Atcoder.FastReader()
    var s = fs.next().toCharArray()
    var d = fs.next().toCharArray()
    var best = 0
    for (i in 0..s.size-d.size) {
        var counter =0
        var ind = 0
        for (j in i until i + d.size){
            if(s[j] == d[ind]) counter++
            ind++
        }
        best = max(best,counter)
    }
    println(d.size-best)

}

class Atcoder {
    internal class FastReader {
        private var br: BufferedReader = BufferedReader(InputStreamReader(System.`in`))
        private var st: StringTokenizer? = null

        operator fun next(): String {
            while (st == null || !st!!.hasMoreElements()) {
                try {
                    st = StringTokenizer(br.readLine())
                } catch (e: IOException) {
                    e.printStackTrace()
                }

            }
            return st!!.nextToken()
        }

        fun nextInt(): Int {
            return Integer.parseInt(next())
        }

        fun nextLong(): Long {
            return java.lang.Long.parseLong(next())
        }

        fun nextDouble(): Double {
            return java.lang.Double.parseDouble(next())
        }

        fun nextLine(): String {
            var str = ""
            try {
                str = br.readLine()
            } catch (e: IOException) {
                e.printStackTrace()
            }
            return str
        }

        fun readIntArray(n: Int): IntArray {
            val a = IntArray(n)
            for (i in 0 until n) a[i] = nextInt()
            return a
        }

        fun readLongArray(n: Int): LongArray {
            val a = LongArray(n)
            for (i in 0 until n) a[i] = nextLong()
            return a
        }

        fun readDoubleArray(n: Int): DoubleArray {
            val a = DoubleArray(n)
            for (i in 0 until n) a[i] = nextDouble()
            return a
        }
    }
}


Measured memory_bytes: 34448
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

N = n1()
A = nn()

A.sort()
#print(A)

max_num = A[-1]
t = array1(max_num+1)
ans = 0

for i, n in enumerate(A):
    if t[n] == 0:
        if i < len(A) - 1 and A[i] == A[i+1]:
            pass
        else:
            ans += 1

    j = n
    while j <= max_num:
        t[j] = 1
        #print(t)
        j += n
    
print(ans)

Measured memory_bytes: 122072
import java.util.Scanner;
import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
		String[] array = sc.nextLine().split(" ");
		int sheep = Integer.parseInt(array[0]);
		int wolves = Integer.parseInt(array[1]);
		String result = sheep <= wolves ? "unsafe" : "safe";
	    System.out.println(result);
	}
}


Measured memory_bytes: 35872
import java.util.*
import java.math.*
import kotlin.math.*

fun readLn()=readLine()!!
fun readInt()=readLn().toInt()
fun readInts()=readLn().split(" ").map{it.toInt()}
fun readLong()=readLn().toLong()
fun readLongs()=readLn().split(" ").map{it.toLong()}

val out=mutableListOf<String>()
fun printLine(s:String){out.add(s)}
fun output(){println(out.joinToString("\n"))}

fun Array<Int>.lower_bound(x:Int,l:Int,r:Int):Int{
    val i=this.binarySearch(x,l,r)
    if(i>=0)return i
    return -i-1
}

val N=200050
var a=IntArray(0)
val E=Array(N){ArrayList<Int>()}
val ans=Array(N){0}
val lis=Array(N){0}
var sz=0
fun DFS(u:Int,p:Int){
    var pop=false
    val i=lis.lower_bound(a[u],0,sz)
    var las=0
    if(i==sz){
        pop=true
        lis[i]=(a[u])
        sz++
    }else{
        las=lis[i]
        lis[i]=a[u]
    }
    ans[u]=sz
    for(v in E[u])if(v!=p)DFS(v,u)
    if(pop){
        sz--
    }
    else lis[i]=las
}
var pop=Array(N){false}
var las=Array(N){0}
var pos=Array(N){0}
var par=Array(N){0}

fun main(){
    val n=readInt()
    a=readInts().toIntArray()
    for(i in 1 until n){
        var (u,v)=readInts()
        E[u].add(v)
        E[v].add(u)
    }
    //DFS(0,-1)
    var stk=Stack<Int>()
    stk.push(1)
    while(!stk.isEmpty()){
        var u=stk.pop()
        if(u>0){
            pos[u]=lis.lower_bound(a[u-1],0,sz)
            if(pos[u]==sz){
                pop[u]=true
                sz++
            }
            las[u]=lis[pos[u]]
            lis[pos[u]]=a[u-1]
            stk.push(-u)
            ans[u]=sz
            for(v in E[u])if(v!=par[u]){
                par[v]=u
                stk.push(v)
            }
        }else{
            u=-u
            if(pop[u])sz--
            else lis[pos[u]]=las[u]
        }
    }
    for(i in 1..n)printLine("${ans[i]}")
    output()
}

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

int main(){
  string s; cin >> s;
  int x, y, n = s.size(); cin >> x >> y;

  map<int, bool> xm[n+2], ym[n+2];
  xm[0][0] = true; ym[0][0] = true;

  int i=0;
  while(i < n and s[i] != 'T'){
    xm[i+1][i+1] = ym[i+1][0] = true;
    i++;
  }

  bool isx = true;
  int cnt = 0;
  s = s + 'T';
  for(; i<=n; i++){
    if(s[i] == 'T'){
      if(isx){
        for(const auto& itr: xm[i-cnt]){
          xm[i+1][itr.first-cnt] = xm[i+1][itr.first+cnt] = true;
        }
        for(const auto& itr: ym[i-cnt]){
          ym[i+1][itr.first] = true;
        }
      }
      else{
        for(const auto& itr: xm[i-cnt]){
          xm[i+1][itr.first] = true;
        }
        for(const auto& itr: ym[i-cnt]){
          ym[i+1][itr.first+cnt] = ym[i+1][itr.first-cnt] = true;
        }
      }

      isx = !isx;
      cnt = 0;
    }
    else{
      cnt++;
    }
  }

  if(xm[n+1][x] && ym[n+1][y])
    cout << "Yes" << endl;
  else 
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 464640
//
//  AOJ0096.c
//
//
//  Created by 中野 優 on 2014/02/23.
//
//

#include <stdio.h>
int main(void){
    long int ans[50],temp,n,i=0,j;
    while(scanf("%d",&n)!=EOF){
        temp=0;
        if(n<=1000){
            ans[i]=(n+3)*(n+2)*(n+1)/6;
        } else if (n<=2000) {
            for(j=0;j<n-1000;j++) temp+=2*(j+2)*(j+1);
            ans[i]=(n+3)*(n+2)*(n+1)/6 - temp;
        } else if(n<3000){
        	for(j=0;j<3000-n;j++) temp+=2*(j+2)*(j+1);
            ans[i] = (4003-n)*(4002-n)*(4001-n)/6 - temp;
        } else {
            ans[i]= (4003-n)*(4002-n)*(4001-n)/6;
        }
        i++;
    }
    for(j=0;j<i;j++) printf("%d\n",ans[j]);
    return 0;
}

Measured memory_bytes: 596
X,Y,Z,K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

D = {(0,0,0)}
used = set()
ans = []
for k in range(K):
  #print(k,D)
  mxdsum = 0
  for d in D:
    dsum = A[d[0]]+B[d[1]]+C[d[2]]
    if dsum >= mxdsum:
      mxdsum = dsum
      mxd = d
  ans.append(mxdsum)
  if mxd[0]+1 < X and (mxd[0]+1,mxd[1],mxd[2]) not in used:
    D.add((mxd[0]+1,mxd[1],mxd[2]))
  if mxd[1]+1 < Y and (mxd[0],mxd[1]+1,mxd[2]) not in used:
    D.add((mxd[0],mxd[1]+1,mxd[2]))
  if mxd[2]+1 < Y and (mxd[0],mxd[1],mxd[2]+1) not in used:
    D.add((mxd[0],mxd[1],mxd[2]+1))
  used.add(mxd)
  D.remove(mxd)
#print(D)
for a in ans:
  print(a)


Measured memory_bytes: 46684
program ABC150B;
var
n,c,i:integer;
s:string;
begin
readln(n);
readln(s);
c:=0;
for i:=3 to n do
if(S[i-2]='A')and(S[i-1]='B')and(S[i]='C')then inc(c);
writeln(c);
end.

Measured memory_bytes: 128
#include <iostream>
using namespace std;
typedef long long ll;
ll n, a[100], dp[100][3], res;
const ll mod = 1000000007;
int main(void){
    // Your code here!
    cin >> n;
    for (ll i = 0; i < 100; i++){
        a[i] = n % 2;
        n /= 2;
    }
    dp[90][2] = 1;
    for (ll i = 89; i >= 0; i--){
        if (a[i] == 0){
            (dp[i][2] = dp[i + 1][1] + dp[i + 1][2]) %= mod;
            (dp[i][1] = dp[i + 1][1]) %= mod;
            (dp[i][0] = dp[i + 1][1] + dp[i + 1][0] * 3) %= mod;
        } else {
            (dp[i][2] = dp[i + 1][2]) %= mod;
            (dp[i][1] = dp[i + 1][1] + dp[i + 1][2]) %= mod;
            (dp[i][0] = dp[i + 1][0] * 3 + dp[i + 1][1] * 2) %= mod;
        }
    }
    res = (dp[0][0] + dp[0][1] + dp[0][2]) % mod;
    cout << res << endl;
}


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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<60)           //1LL<<63でオーバーフロー
#define inf (1<<29)             //1<<29でオーバーフロー

template<class T>T GCD(T a, T b){if(a<b){T temp=a;a=b;b=temp;}T res=a%b;while(res!=0){a=b;b=res;res=a%b;}return b;}

int main(int argc,char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    int n;
    ll x;
    cin >> n >> x;

    vector<ll> xi(n);
    ll minxi=INF;
    for(int i=0;i<n;i++){
        cin >> xi[i];
        xi[i]=abs(xi[i]-x);
    }
    if(n==1){
        cout << xi[0] << endl;
        return 0;
    }

    ll allgcd=GCD(xi[0],xi[1]);
    for(int i=2;i<n;i++){
        allgcd=GCD(allgcd,xi[i]);
    }

    cout << allgcd << endl;

    return 0;
}


Measured memory_bytes: 3988
main = do
  li <- getLine
  let [s,c] = map read $ words li
  let ans = compute s c
  print ans

compute :: Int -> Int -> Int
compute s c
  | d >= 0 = s + d `div` 4
  | True   = c `div` 2
  where
    d = c - 2 * s

{-
 c + c -> S
 if 2s <= c, s + (c-2s)/4
 otherwise, c/2
-}


Measured memory_bytes: 508
mod = 10 ** 9 + 7
n, m = map(int, input().split())

def nprf(n):
    pf = {}
    for i in range(2, int(n ** 0.5)+1):
        while n % i == 0:
            pf[i] = pf.get(i, 0) + 1
            n //= i
    if n > 1:
        pf[n] = 1
    return pf

def comb(n, k):
    k = min(k, n-k)
    result = 1
    for i in range(n-k+1, n+1):
        result *= i
    for i in range(1, k+1):
        result //= i
    return result

ans = 1
for v in nprf(m).values():
    ans = ans * comb(v+n-1, v) % mod
    
print(ans)            

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int grid[1005][1005];
int dp[1005][1005];

int main()
{
//	cut here before submit 
//	freopen ("testcase.walk", "r", stdin );
	int h, w, n;
	while (scanf ("%d %d %d", &h, &w, &n ), h, w, n ){
		memset (grid, false, sizeof (grid ) );
		rep (i, h ){
			rep (j, w ){
				int in;
				scanf ("%d", &grid[i][j] );// 1 : 東 0 : 南
			} // end rep
		} // end rep
		memset (dp, 0, sizeof (dp ) );
		dp[0][0] = n - 1;
		for (int i = 1; i < h; i++ ){
			int k = dp[i-1][0];
			dp[i][0] = (k % 2 == 0 ? k/2 : (!grid[i-1][0] ? (k+1)/2 : (k-1)/2 ) );
		} // end for
		for (int j = 1; j < w; j++ ){
			int m = dp[0][j-1];
			dp[0][j] = (m % 2 == 0 ? m/2 : ( grid[0][j-1] ? (m+1)/2 : (m-1)/2 ) );
		} // end for

		for (int i = 1; i < h; i++ ){
			for (int j = 1; j < w; j++ ){
				int k = dp[i-1][j], m = dp[i][j-1];
				dp[i][j] += (k % 2 == 0 ? k/2 : (!grid[i-1][j] ? (k+1)/2 : (k-1)/2 ) );	
				dp[i][j] += (m % 2 == 0 ? m/2 : ( grid[i][j-1] ? (m+1)/2 : (m-1)/2 ) );
			} // end for
		} // end for

		int row = 0, col = 0;
		while (row < h && col < w ){
			if ((dp[row][col] + grid[row][col] ) % 2 == 0 ){
				row++;
			}else{
				col++;
			} // end if
		} // end while 
 
		printf ("%d %d\n", row+1, col+1 );	
	} // end loop
		
	return 0;
}

Measured memory_bytes: 9084
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/math/common_factor_rt.hpp>
#define USE_MATH_DEFINES
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
// namespace mp = boost::multiprecision;
// namespace mt = boost::math
// using Bint = mp::cpp_int;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
}

Measured memory_bytes: 256
n = int(input())
l = [0] * 10002
for a in range(1, 100):
    for b in range(1, 100):
        for c in range(1, 1000):
            tmp = a * a + b * b + c * c + a * b + b * c + c * a
            if tmp <= 10000: l[tmp] -= -1
for i in range(1, n + 1): print(l[i])

Measured memory_bytes: 73708
def Gcd(x,y):
    if( y>x ): # x>yにする
        r = x
        x = y
        y = r
    if( y==0 ):
        return x
    return Gcd(y,x%y)

import sys
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MAX = 10**5+5

def resolve():
    n = int(input())
    a = [0]
    a.extend(list(map(int,input().split())))
    leftmax = [0]*(n+2)
    rightmax = [0]*(n+2)
    leftmax[1]=a[1]
    rightmax[n]=a[-1]
    for i in range(2,n):
        r=n-i+1
        leftmax[i]=Gcd(leftmax[i-1],a[i])
        rightmax[r]=Gcd(rightmax[r+1],a[r])
    ans = 0
    for i in range(1,n+1):
        s = Gcd(leftmax[i-1],rightmax[i+1])
        ans = max(ans,s)
    print(ans)

if __name__ == "__main__":
    resolve()

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

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()
#define endl        "\n"
#define repp(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a,b) 	for(int i=a;i<=b;i++)
#define IOS         ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N=1e5 + 5;
const int M=1e9 + 7;

int32_t main()
{
	IOS;
	//memset(dp,-1,sizeof(dp));
	int a,b;
	cin >> a >> b;
	int ans = a - min(a,2*b);
	cout << ans << endl;
}


Measured memory_bytes: 256
let rec draw h w =
	let rec draw' w =
		match w with
		|0 -> print_string "\n"
		|_ -> print_string "#";draw' (w-1)
	in
	match h with
	|0 -> print_string "\n"
	|_ -> draw' w;draw (h-1) w;;

let rec loop () =
	Scanf.sscanf(read_line()) "%d %d" (fun x y -> if x = 0 && y = 0 then () else (draw x y;loop()));;

loop();;



Measured memory_bytes: 2240
#include <bits/stdc++.h>
using namespace std;
struct Point {double x,y;};

void koch(int n,Point a,Point b){
    if(n==0){return;}
    Point t,s,u;
    double th=M_PI*60.0/180.0;
    s.x =(2.0*a.x+1.0*b.x)/3;
    s.y =(2.0*a.y+1.0*b.y)/3;
    t.x =(2.0*b.x+1.0*a.x)/3;
    t.y =(2.0*b.y+1.0*a.y)/3;
    u.x =(t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
    u.y =(t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;
    
    koch(n-1,a,s);
    cout <<setprecision(10) << s.x<<' '<<setprecision(10)<<s.y<<endl;
    koch(n-1,s,u);
    cout <<setprecision(10)<<u.x<<' '<<setprecision(10)<<u.y<<endl;
    koch(n-1,u,t);
    cout <<setprecision(10)<<t.x<<' '<<setprecision(10)<<t.y<<endl;
    koch(n-1,t,b);
    
}

int main() {
   Point a,b; 
   int n; 
   cin>>n; 
   a.x=0;a.y=0;     
   b.x=100.0;b.y=0;
   cout<<a.x<<' '<<a.y<<endl;
   koch(n,a,b);
   cout<<b.x<<' '<<b.y<<endl;
  
}




Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B,K,i ;
  cin>>A>>B>>K ;
  int aans[K] ;
  int a = A ;
  for (i=0 ; i<K ; i++ ){
      aans[i] = a ;
      a++ ;
  }
  int bans[K] ;
  int b = B ;
  for (i=0 ; i<K ; i++ ){
      bans[i] = b-K+1 ;
      b++ ;
  }
  if(B-A >= K*2){
    for(i=0;i<K;++i){
    printf("%d\n", aans[i]);
  }
    for(i=0;i<K;++i){
    printf("%d\n", bans[i]);
  }
} else{
  for(i=A;i<B+1;++i){
    printf("%d\n",i);
  }
}
  return 0 ;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long X,m=100;
double r=1.01;
string S;
int main(){
    cin>>X;
    for(int i=1;;i++){
        m*=1.01;
        if(m>=X){cout<<i<<endl;return 0;}
    }
    return 0;
}

Measured memory_bytes: 3636
import numpy
import bisect

N,M,K = map(int, input().split())
ans = 0
A = list(map(int,input().split()))
B = list(map(int,input().split()))

A = numpy.cumsum(numpy.array(A))
A = list(A)
A.insert(0, 0)
B = numpy.cumsum(numpy.array(B))
B = list(B)
B.insert(0, 0)
ans = 0

for i in range(N+1):
    if K - A[i] < 0:
        break
    b = bisect.bisect(B, K - A[i])
    ans = max(ans, i+b-1)

print(ans)

Measured memory_bytes: 58712
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <utility>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define rep(i,n) for (int i=0;i<n;++i)
#define REP(i,n) for (int i=1;i<=n;++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define read(x) scanf("%d",&x)
int n,m;
char s[100005],t[100005];
int nxt[100005][26];
int main(){
	ios::sync_with_stdio(false);
	cin>>s+1>>t+1;n=strlen(s+1);m=strlen(t+1);
	for (int c=0;c<26;++c){
		int lst=0;
		for (int i=n;i>=0;--i){
			nxt[i][c]=lst;
			if (s[i]=='a'+c) lst=i;
		}
	}
	int p=0;ll cnt=0;
	for (int i=1;i<=m;++i){
		int c=t[i]-'a';
		if (nxt[0][c]==0){
			cout<<-1<<endl;return 0;
		}
		if (nxt[p][c]) p=nxt[p][c];
		else p=nxt[0][c],cnt+=n;
	}
	cout<<(ll)cnt+(ll)p<<endl;
	return 0; 
}

Measured memory_bytes: 10624
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
typedef long long int ll;
using namespace std;
#define P 1000000007
#define rep(i,n) for(i=0;i<n;++i)
#define repp(i,a,n) for(i=a;i<n;++i)
#define repr(i,a,n) for(i=a;i>=n;--i)

ll binpowmod(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll modInverse(ll n, ll p)
{
    return binpowmod(n, p-2, p);
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,j,h,w;
    char ch;
    cin >> h >> w;
    ll a[h][w];
    rep(i,h) 
    rep(j,w)
    {
        cin >> ch ;
        if(ch=='.') a[i][j]=1;
        else a[i][j]=0;
    }
    if(a[0][0]!=1||a[h-1][w-1]!=1)
    {
        cout << 0 ;
        return 0 ;
    }
    ll dp[h][w];
    memset(dp,0,sizeof(dp));
    
    for(i=0;i<h;++i)
    for(j=0;j<w;++j)
    {
        if(a[i][j])
        {
            if(i==0&&j==0) dp[i][j]=1;
            else if(i==0) dp[i][j]=dp[i][j-1];
            else if(j==0) dp[i][j]=dp[i-1][j];
            else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%P;
        }
    }
    cout << dp[h-1][w-1];
    return 0;
}

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

int main() {
  char b;
  cin >> b;
  if(b == 'A') cout << 'T' << endl;
  if(b == 'C') cout << 'G' << endl;
  if(b == 'G') cout << 'C' << endl;
  if(b == 'T') cout << 'A' << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<map>
#include<string>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<typeinfo>
#include<queue>
using namespace std;
int main() {
	int N, K;
	cin >> N >> K;
	vector<int>a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	if((N-1)%(K-1)==0)cout << (N-1) / (K - 1);
	else cout<< (N - 1) / (K - 1)+1;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

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

    if(S.length() <= K) {
        cout << S << endl;
    } else {
        cout << S.substr(0, K) << "..." << endl;
    }
}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i < n; i++) {
            double x1 = sc.nextDouble();
            double y1 = sc.nextDouble();
            double x2 = sc.nextDouble();
            double y2 = sc.nextDouble();
            double x3 = sc.nextDouble();
            double y3 = sc.nextDouble();
             
            double a = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
            double b = Math.sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));
            double c = Math.sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
             
            double s = (a+b+c)/2;
            double r = a*b*c / (4*Math.sqrt(s*(s-a)*(s-b)*(s-c)));
             
            double A1 = 2*(x2-x1);
            double B1 = 2*(y2-y1);
            double C1 = (x1*x1)-(x2*x2)+(y1*y1)-(y2*y2);
            double A2 = 2*(x3-x1);
            double B2 = 2*(y3-y1);
            double C2 = (x1*x1)-(x3*x3)+(y1*y1)-(y3*y3);
            double X = (B1*C2-B2*C1)/(A1*B2-A2*B1);
            double Y = (C1*A2-C2*A1)/(A1*B2-A2*B1);
 
            System.out.printf("%.3f %.3f %.3f\n",X,Y,r);
        }
    }
    public static double sr(double a) {
        a = a*10000;
        if(a%10 >=  5) {
            a += 10-a%10;
        }
        else {
            a -= a%10;
        }
        int b = (int)a;
         
        return (b/10000.0);
    }
}



Measured memory_bytes: 28752
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define RREP(i,a) for(int (i)=(a)-1;(i)>=0;(i)--)
#define FORR(i,a,b) for(int (i)=(a)-1;(i)>=(b);(i)--)
#define PI acos(-1.0)
#define DEBUG(C) cout<<C<<endl;
#define VI vector<int>
#define VII vector<VI>
#define VL vector<LL>
#define VLL vector<VL>
#define VD vector<double>
#define VDD vector<VD>
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<LL,LL>
#define VPII vector<PII>
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define EP emplace_back
#define FORE(a,b) for(auto &&a:b)

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF=1e9;
const int MOD=INF+7;

int main(void){
    string s; cin>>s;
    string res="";
    REP(i,s.size()){
        if(s[i]=='B'){
             if(!res.empty())res.pop_back();
        }else{
            res.push_back(s[i]);
        }
    }
    cout<<res<<endl;
}


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


int main(){
    int a, b, c, temp;
    cin>>a>>b>>c;
    temp=a;
    a=c;
    int temp2=b;
    b=temp;
    c=temp2;

    cout<<a<<" "<<b<< " "<<c<<endl;

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
 
using namespace std;
 
#define sp(x) cout<<setprecision(x);
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define yes "Yes"
#define no "No"
#define divs 1000000007
#define dive 1000000009
#define pi 3.141592653589793238
 
typedef pair<int, int> P;
 
 
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
    // Failed to predict input format
    int n, K; cin>>n>>K;
    vector<int> d(K);
    vector<vector<int>> v(K);
    vector<bool> ans(n,false);
    REP(i,K){
        cin>>d[i];
        REP(j,d[i]){
            int in; cin>>in;
            ans[in-1]=true;
        }
    }
    int cnt=0;
    REP(i,n){
        if(ans[i]==false) cnt++;
    }
    cout<<cnt<<endl;

    return 0;
}


Measured memory_bytes: 3640
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

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

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

string s;
int n;

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	bool f = 1;
	cin >> s;
	n = s.size();
	int ans = n;
	if (s.size() == 1) return cout << 1, 0;
//	cout << n << '\n';
	for (int i = 0; i < n - 1; i++){
		if (s[i] != s[i + 1]){
//			cout << i + 1 << ' ' << i + 2 << ' ' << n - (i + 1) << ' ' << i + 1 << '\n';;
			ans = min(ans, max(n - (i + 1), i + 1));
		}
	}
	cout << ans;









	return 0;
}


Measured memory_bytes: 512
N = int(input())
A = [int(i) for i in input().split()]

def gcd(x, y):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    return gcd(x%y, y)

L = [0]
R = [0]
for i in range(N):
    L.append(gcd(A[i], L[i]))
    R.append(gcd(A[-i-1], R[i]))

R.reverse()

M = []
for i in range(0, N):
    M.append(gcd(L[i], R[i+1]))

print(max(M))

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

int main()
{
    int n;
    cin >> n;
    vector<bool> dp(1e6 + 10, 1);
    vector<int> ar(n);
    set<int> a;
    vector<bool> ndup(1e6 + 10, 1);
    for (int i = 0; i < n; i++)
    {
        cin >> ar[i];
        if (a.count(ar[i]))
            ndup[ar[i]] = 0;
        else
            a.insert(ar[i]);
    }
    for (int x : a)
    {
        for (int j = 2; x * j <= 1e6 + 10; j++)
        {
            dp[x * j] = 0;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (dp[ar[i]] && ndup[ar[i]])
            ans++;
    }
    cout << ans << endl;
}


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

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
void pulse(pair<int,int>& a){
    a.first++;a.second++;
}
struct Ans{
int no;
vector<pair<int,int>> tree;
vector<pair<int,int>> next_tree(){
    vector<pair<int,int>> next=tree;
    int n=tree.size();
    rep(i,n)pulse(next[i]);
    for(int i=2;i<=no+1;i++){
        next.push_back(make_pair(1,i));
        next.push_back(make_pair(i,no+2));
    }
    return next;
}
void output(){
int n=tree.size();
cout<<n<<endl;
rep(i,n){
    cout<<tree[i].first<<" "<<tree[i].second<<endl;
}
}
};

signed main(){
    int n;cin>>n;
    vector<Ans> ans(105);
    ans[3].tree.push_back(make_pair(1,3));
    ans[3].tree.push_back(make_pair(2,3));
    ans[4].tree.push_back(make_pair(1,2));
    ans[4].tree.push_back(make_pair(1,3));
    ans[4].tree.push_back(make_pair(2,4));
    ans[4].tree.push_back(make_pair(3,4));
    rep(i,n+1)ans[i].no=i;
    for(int i=4;i<=100;i+=2){
        vector<pair<int,int>> next=ans[i].next_tree();
        ans[i+2].tree=next;
    }
    for(int i=5;i<=100;i+=2){
        vector<pair<int,int>> next=ans[i-1].tree;
        rep1(j,i-1)next.push_back(make_pair(j,i));
        ans[i].tree=next;
    }
    ans[n].output();
    return 0;
}

Measured memory_bytes: 3180
#include<bits/stdc++.h>
using namespace std;
int main()
{    long long int n,i,ans=0,p,q;
    cin>>n;
    p=n/500;
   // cout<<p<<" ";
    ans+=p*1000;
    n=n-p*500;
    q=n/5;
    ans+=q*5;
    cout<<ans;
}


Measured memory_bytes: 256
// Didn't see Editorial but I made a lot of mistakes
// 2d cumsum

#include <iostream>
#include <queue>
#include <iomanip>
#include <map>
#include <algorithm>

using namespace std;

using ll = long long;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int sumJ[1002][1002], sumO[1002][1002], sumI[1002][1002];

int main() {
    int M, N, K;
    cin >> M >> N >> K;

    string V[M];
    for (int i = 0; i < M; i++) {
        cin >> V[i];
        for (int k = 0; k < N; k++) {
            sumJ[i+1][k+1] = (V[i][k] == 'J');
            sumO[i+1][k+1] = (V[i][k] == 'O');
            sumI[i+1][k+1] = (V[i][k] == 'I');
        }
    }

//    for (int i = 0; i <= M; i++) {
//        for (int k = 0; k <= N; k++) {
//            cout << sumJ[i][k] << " ";
//        }
//        cout << endl;
//    }
//    cout << endl;

    for (int i = 0; i <= M; i++) {
        for (int k = 1; k <= N; k++) {
            sumJ[i][k] += sumJ[i][k-1];
            sumO[i][k] += sumO[i][k-1];
            sumI[i][k] += sumI[i][k-1];
        }
    }

//    for (int i = 0; i <= M; i++) {
//        for (int k = 0; k <= N; k++) {
//            cout << sumJ[i][k] << " ";
//        }
//        cout << endl;
//    }
//    cout << endl;

    for (int i = 1; i <= M; i++) {
        for (int k = 0; k <= N; k++) {
            sumJ[i][k] += sumJ[i-1][k];
            sumO[i][k] += sumO[i-1][k];
            sumI[i][k] += sumI[i-1][k];
        }
    }

//    for (int i = 0; i <= M; i++) {
//        for (int k = 0; k <= N; k++) {
//            cout << sumJ[i][k] << " ";
//        }
//        cout << endl;
//    }
//    cout << endl;

    for (int i = 0; i < K; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--; c--; d--;
        cout << (sumJ[c+1][d+1] - sumJ[c+1][b] - sumJ[a][d+1] + sumJ[a][b]) << " ";
        cout << (sumO[c+1][d+1] - sumO[c+1][b] - sumO[a][d+1] + sumO[a][b]) << " ";
        cout << (sumI[c+1][d+1] - sumI[c+1][b] - sumI[a][d+1] + sumI[a][b]) << endl;
    }

    return 0;
}

Measured memory_bytes: 15580
using System;
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            if( str[0].Substring(str[0].Length-1) == str[1].Substring(0,1) &&
                str[1].Substring(str[1].Length-1) == str[2].Substring(0,1))
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
            Console.ReadKey();
        }
    }


Measured memory_bytes: 13140
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from itertools import permutations
import math
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    X = []
    Y = []
    for _ in range(N):
        x, y = map(int, readline().split())
        X.append(x)
        Y.append(y)

    total = 0
    for i in permutations(range(N)):
        for j in range(1,N):
            total += math.sqrt((X[i[j]]-X[i[j-1]])**2 + (Y[i[j]]-Y[i[j-1]])**2)

    ans = total/math.factorial(N)
    print(ans)


if __name__ == '__main__':
    main()


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

int main(){
  int c, a, b;
  cin >> c >> a >> b;
  
  int s = (c + a + b) / 2.0;
  
  cout << pow(s * (s - a) * (s - b) * (s - c), 0.5) << endl;
}

Measured memory_bytes: 4104
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {
    
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;

    vector<long long> A(X), B(Y), C(Z);
    rep(i,X) cin >> A[i];
    rep(i,Y) cin >> B[i];
    rep(i,Z) cin >> C[i];

    sort(A.begin(), A.end(), greater<long long>());
    sort(B.begin(), B.end(), greater<long long>());
    sort(C.begin(), C.end(), greater<long long>());

    vector<long long> sums;

    for (int l = 0; l < X && l + 1 <= K; l++) {
        for (int m = 0; m < Y && (l + 1) * (m + 1) <= K; m++) {
            for (int n = 0; n < Z && (l + 1) * (m + 1) * (n + 1) <= K; n++) {
                sums.push_back(A[l] + B[m] + C[n]);
            }
        }
    }

    sort(sums.begin(), sums.end(), greater<long long>());
    
    rep(i,K) cout << sums[i] << endl;

    return 0;
}


Measured memory_bytes: 1404
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <list>
#include <iomanip>
#include <queue>
#include <cmath>
#include <numeric>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)

using namespace std;
using ll = long long;
typedef pair<ll, ll> p;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
const long long mod = 1e9 + 7;
ll gcd(ll a, ll b);
ll lcm(ll a, ll b);

int main() {

	int n;
	cin >> n;

	vector<ll> c(n), s(n), f(n);

	rep(i, n - 1) cin >> c[i] >> s[i] >> f[i];

	vector<ll> ans(n);
	ll tmp;

	rep(i, n - 1) {
		tmp = 0;
		repl(j, i, n - 1) {
			if(tmp <= s[j]){
				tmp = c[j] + s[j];
			}
			else {
				ll L = 1, k = 0;
				while (L < tmp) {
					L = s[j] + f[j] * k;
					k++;
				}
				tmp = L + c[j];
			}
		}
		ans[i] = tmp;
	}

	rep(i, n - 1) {
		cout << ans[i] << endl;
	}
	cout << 0;


	return 0;
}


ll gcd(ll a, ll b) {
	if (a % b == 0)return(b);
	else return(gcd(b, a % b));
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

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

int main() {
  int N,M,X,Y;
  cin>>N>>M>>X>>Y;
  vector<int> x(N);
  vector<int> y(M);
  bool parousia=0;
  for(int Z=X+1;Z<=Y;Z++){
    parousia=1;
    for(int i=0;i<N;i++){
      cin>>x.at(i);
        if(x.at(i)>=Z)
          parousia*=0;
    }   
    for(int j=0;j<M;j++){
      cin>>y.at(j);
        if(y.at(j)<Z)
          parousia*=0;
    }   
    if(parousia==1){
      cout<<"No War"<<endl;
      break;
    }
  }
  if(parousia==0)
    cout<<"War"<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String S = cin.next();

        String[] words = {"dream", "dreamer", "erase", "eraser"};

        Queue<Integer> q = new ArrayDeque<>();
        q.add(0);

        boolean matched = false;
        while (!q.isEmpty()) {
            int i = q.poll();
            if (i == S.length()) {
                matched = true;
                break;
            }

            for (String word : words) {
                int end = i + word.length();
                if (end > S.length()) {
                    continue;
                }
                if (S.substring(i, end).equals(word)) {
                    q.add(end);
                }
            }
        }

        if (matched) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 32112
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n;
  cin >> n;
  int ans = 0;
  for(int i = 1; i <= n; i += 2) {
    int total = 0;
    rep2(j, 1, i + 1) if(i % j == 0) total++;
    if(total == 8) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256