akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int ans = 0;
    REP(i, 3) ans += s[i] - '0';
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int f(int n,int d){
  return n/d;
}

int main(){
  int l,r,d; cin >>l >>r >>d;
  print(f(r,d)-f(l-1,d));
}


Measured memory_bytes: 3592
(defun splitat (c line)
  (labels ((rec (line acc)
				(let ((pos (position-if (lambda(cc) (char= c cc)) line)))
				  (if pos
					  (rec (subseq line (1+ pos)) (cons (subseq line 0 pos) acc))
					(nreverse (cons line acc))))))
	(rec line nil)))
(defun splitspace(line)
  (splitat #\space line))
(let ((line (parse-integer (read-line nil nil))))
  (format t "~A~%" (nth (1- line) '(1 1 1 2 1 2 1 5 2 2 1 5 1 2 1 14 1 5 1 5 2 2 1 15 2 2 5 4 1 4 1 51))))


Measured memory_bytes: 12516
//
//  main.c
//  yigrve
//
//  Created by x19012xx on 2019/12/06.
//  Copyright © 2019 AIT. All rights reserved.
//

#include <stdio.h>

int check(int a,int aa,int b,int bb){
    if(a==b && aa==bb){
        return 1;
    }else{
        return 0;
    }
}
int over(int a){
    if(a>2){
        return 5-a;
    }else{
        return a;
    }
}
int ck(int a,int b){
    int c=0;
    if(a>2){
        c++;
    }
    if(b>2){
        c++;
    }
    if(over(a)>over(b)){
        c++;
    }
    if(over(a)==0 && over(b)==2){
        c++;
    }
    if(over(a)==2 && over(b)==0){
        c++;
    }
    return c;
}


int main(int argc, const char * argv[]) {
    int A_Dise[6],B_Dise[6];
    int i,j,k;
    int OO=0;
    
    for(i=0;i<6;i++){
        scanf("%d",&A_Dise[i]);
    }
    for(i=0;i<6;i++){
        scanf("%d",&B_Dise[i]);
    }
    
    for(i=0;i<6;i++){
        if(check(A_Dise[0], A_Dise[5-0], B_Dise[i], B_Dise[5-i])==1){
            OO++;
            break;
        }
    }
    for(j=0;j<6;j++){
        if(check(A_Dise[1], A_Dise[5-1], B_Dise[j], B_Dise[5-j])==1){
            OO++;
            break;
        }
    }
    
    if(over(i)+over(j)==1){
        k=2;
    }else if(over(i)+over(j)==2){
        k=1;
    }else{
        k=0;
    }
    
    if(ck(i,j)%2==0){
        if(check(A_Dise[2], A_Dise[5-2], B_Dise[k], B_Dise[5-k])==1){
            OO++;
        }
    }else{
        if(check(A_Dise[2], A_Dise[5-2], B_Dise[5-k], B_Dise[k])==1){
            OO++;
        }
    }

    if(OO==3){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}



Measured memory_bytes: 2104
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
    a[i] -= 1
path = [0]
now = 0
visited = {0}
p = 0
while True:
    if a[now] in visited:
        p = a[now]
        break
    now = a[now]
    visited.add(now)
    path += [now]
p_index = 0
for i in range(len(path)):
    if path[i] == p:
        p_index = i
        break

if k <= p_index:
    print(path[k] + 1)
else:
    print(path[p_index + (k-p_index)%len(path[p_index:])] + 1)


Measured memory_bytes: 32420
n = int(input())
w = [input() for _ in range(n)]

for i in range(n-1):
    if w[i][-1] != w[i+1][0]:
        print("No")
        quit()
for j in range(n):
    if w.count(w[j]) != 1:
        print("No")
        quit()
print("Yes")

Measured memory_bytes: 3060
#include<stdio.h>
#define N 10000
int main(){
  int a[N],n,i,j,s,count=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(i=0;i<n;i++){
    s=0;
    for(j=2;j*j<=a[i];j++){
      if(a[i]%j==0)s=1;
    }
      if(s==0)count++;
  }
  printf("%d\n",count);
  return 0;
}



Measured memory_bytes: 2100
package main
 
import "fmt"
 
func main(){
  	var a, b int
	fmt.Scan(&a, &b)
  	if a % 2 == 1 && b % 2 == 1 {
    	fmt.Println("Odd")
  	}else{
    	fmt.Println("Even")
  	}
}


Measured memory_bytes: 512
//#include "stdafx.h"
#include<bits/stdc++.h> 
#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
int n,q;
long long ans;
int main()
{
	cin>>n;
	for(int i=n;i>=0;i--){
		q=sqrt(i);
		ans=q*q;
		if(ans==i){
			cout<<i<<"\n";
			break;}
	}

	return 0;
}



Measured memory_bytes: 3612
#include <stdio.h>

#define MAX 1000000
#define NIL -1

struct Node{int p, l, r; };

struct Node T[MAX];
int n, D[MAX];

void print(int u);
int rec(int u, int p);

int main(){
  int i, j, k, l, d, s, c, r;

  scanf("%d", &n);
  for(i=0; i<n; i++){
    T[i].p=NIL;
    T[i].l=NIL;
    T[i].r=NIL;
}

  for(i=0; i<n; i++){
    scanf("%d%d", &s, &d);
    for(j=0; j<d; j++){
      scanf("%d", &c);
      if(j==0) T[s].l=c;
      else T[l].r =c;
      l=c;
      T[c].p=s;
    }
  }
  for(i=0; i<n; i++){
    if(T[i].p==NIL) r=i;
  }
  rec(r, 0);
  for(i=0; i<n; i++) print(i);
  return 0;
}

void print(int u){
  int j, c;
  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);
  if(T[u].p==NIL)         printf("root, ");
  else if(T[u].l==NIL)    printf("leaf, ");
  else                    printf("internal node, ");

  printf("[");
  for(j=0, c=T[u].l; c!=NIL; j++, c=T[c].r){
    if(j)       printf(", ");
    printf("%d", c);
}
  printf("]\n");
}
int rec(int u, int p){
  D[u]=p;
  if(T[u].r!=NIL) rec(T[u].r, p);
  if(T[u].l!=NIL) rec(T[u].l, p+1);
}



Measured memory_bytes: 6488
/*
3つの数の整列
*/

#include<stdio.h>
int main(void){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  if(a<b)
    if(b < c)
      printf("%d %d %d\n",a,b,c);
    else
      if(a<c)
	printf("%d %d %d\n",a,c,b);
      else
	printf("%d %d %d\n",c,a,b);
  else
    if(a < c)
      printf("%d %d %d\n",b,a,c);
    else
      if(b <c)
	printf("%d %d %d\n",b,c,a);
      else
	printf("%d %d %d\n",c,b,a);
  return 0;
}


Measured memory_bytes: 2076
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 	string s; cin>>s;
  	int ans = 0;
  	for(int i=0;i<4;i++){
    	if(s.at(i)=='+'){
     		ans++;   
        }else if(s.at(i)=='-'){
     		ans--;   
        }
    }
  	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int LIMIT=45;
int limit;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct point{
    int x,y;
};
struct puzzle{
    int f[4][4];
    point p[16];
    point zero;
};
puzzle aim,in;
void init()
{
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    {
        int num=4*i+j+1;
        if(num==16) continue;
        aim.f[i][j]=num;
        aim.p[num].x=i,aim.p[num].y=j;
    }
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    {
        int num=in.f[i][j];
        if(num==0) {in.zero.x=i;in.zero.y=j;continue;}
        in.p[num].x=i,in.p[num].y=j;
     } 
}
int exp(puzzle a)
{
    int t=0;
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    {
        int num=a.f[i][j];
        if(num==0) continue;
        t+=abs(i-aim.p[num].x)+abs(j-aim.p[num].y);
    }
    return t;
}
bool dfs(puzzle t,int step,int di)
{
    int e=exp(t);
    if(step+e>limit) return false;
    if(e==0) return true;
    for(int i=0;i<4;i++)
    {
        puzzle tmp=t;
        int x=tmp.zero.x,y=tmp.zero.y;
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>3||tx<0||ty>3||ty<0) continue;
        if(max(di,i)-min(di,i)==2) continue;
        swap(tmp.zero,tmp.p[tmp.f[tx][ty]]);
        swap(tmp.f[x][y],tmp.f[tx][ty]);
        if(dfs(tmp,step+1,i)) return true;
    }
    return false;
}
int iterative_deepening()
{
    init();
    for(limit=exp(in);limit<=LIMIT;limit++)
    if(dfs(in,0,-100)) return limit;
}
int main()
{
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++) cin>>in.f[i][j];
    cout<<iterative_deepening()<<endl;
    return 0;
}


Measured memory_bytes: 3108
use std::fmt::{Debug, Display};
use std::io::{self, Read};
use std::str::{self, FromStr};

fn main() {
    let stdin = io::stdin();
    let mut sc = Scanner::new(stdin.lock().bytes());
    println!("{}", solve(sc.next()));
}


fn solve(s: String) -> usize {
    let ref s = s.as_bytes();
    for n in (0..s.len() / 2).rev() {
        if s[0..n] == s[n..2 * n] {
            return 2 * n;
        }
    }
    panic!()
}


struct Scanner<R: Read> {
    buf: Vec<u8>,
    bytes: io::Bytes<R>,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(bytes: io::Bytes<R>) -> Self {
        Scanner {
            buf: Vec::with_capacity(256),
            bytes: bytes,
        }
    }

    fn next<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut c = self.bytes.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = self.bytes.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = self.bytes.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse().unwrap()
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
        where <T as FromStr>::Err: Debug
    {
        (0..n).map(|_| self.next()).collect()
    }

    fn pairs<A: FromStr, B: FromStr>(&mut self, n: usize) -> Vec<(A, B)>
        where <A as FromStr>::Err: Debug,
              <B as FromStr>::Err: Debug
    {
        (0..n).map(|_| (self.next(), self.next())).collect()
    }

    fn trios<A: FromStr, B: FromStr, C: FromStr>(&mut self, n: usize) -> Vec<(A, B, C)>
        where <A as FromStr>::Err: Debug,
              <B as FromStr>::Err: Debug,
              <C as FromStr>::Err: Debug
    {
        (0..n)
            .map(|_| (self.next(), self.next(), self.next()))
            .collect()
    }

    fn mat<T: FromStr>(&mut self, m: usize, n: usize) -> Vec<Vec<T>>
        where <T as FromStr>::Err: Debug
    {
        (0..n).map(|_| self.vec(m)).collect()
    }
}


#[allow(dead_code)]
fn print_foreach<T: Display>(answer: &[T]) {
    for x in answer {
        println!("{}", x);
    }
}


#[allow(dead_code)]
fn print_yn(answer: bool, yes: &str, no: &str) {
    println!("{}", if answer { yes } else { no });
}


#[allow(dead_code)]
fn print_or<T: Display>(answer: &Option<T>, or: &T) {
    match *answer {
        Some(ref x) => println!("{}", x),
        None => println!("{}", or),
    }
}


Measured memory_bytes: 4352
#include <iostream>

using namespace std;

int min(int x, int y)
{
  if (x<y) return x; else return y;
}
int max(int x,int y)
{
  if (x>y) return x; else return y;
}

int main()
{
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if (b<=c || d<=a) cout << 0; else
  {
    cout << min(b,d) - max(a,c);
  } 
  return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,A,B;
int P[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	int C[3]={};
	FOR(i,N) {
		cin>>P[i];
		if(P[i]<=A) C[0]++;
		else if(P[i]<=B) C[1]++;
		else C[2]++;
	}
	cout<<min({C[0],C[1],C[2]})<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rand() (rand() << 15 | rand())
using namespace std;
typedef long long  ll;
#define EPS 1e-9
#define PI acos(-1.0)

int main() {

   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   int n;
   cin >> n;
   vector<int> a(n);
   for(int &x : a)
      cin >> x;
   int mn = a[0] , ans = 1;
   for(int i = 1 ; i < n ; ++i){
      if(a[i] <= mn)
         ++ans;
      mn = min(mn , a[i]);
   }
   cout << ans << "\n";
}

Measured memory_bytes: 1024
const input = require("fs").readFileSync("/dev/stdin", "utf8")

;(input => {

    const lines = input.split('\n')
    const N = lines[0] - 0
    const A = lines[1].split(" ").map(Number)

    A.sort((a, b) => b - a)

    let com = 0
    for (let i = 1; i < N; i++) {
        com += A[Math.floor(i /  2)]
    }

    console.log(com)

})(input)

Measured memory_bytes: 52908
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        long n = sc.NextLong();
        long[] aa = sc.LongArray();
        long[] bb = sc.LongArray();

        List<long> under = new List<long>();
        List<long> over = new List<long>();
        long even = 0;

        for (int i = 0; i < n; i++)
        {
            if (aa[i] > bb[i])
            {
                over.Add(aa[i] - bb[i]);
            }
            else if (aa[i] < bb[i])
            {
                under.Add(bb[i] - aa[i]);
            }
            else
            {
                even++;
            }
        }

        long underSum = under.Sum();
        long underCount = under.Count();

        if (underSum > over.Sum())
        {
            Console.WriteLine(-1);
            return;
        }

        over = over.OrderByDescending(num => num).ToList();

        long answer = underCount;

        if (underSum != 0)
        {
            foreach (var o in over)
            {
                underSum -= o;
                answer++;
                if (underSum <= 0)
                {
                    break;
                }
            }
        }

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 45248
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
vector<P> xvec, yvec;
vector<P> road[100100];
priority_queue<P, vector<P>, greater<P>> que;
bool used[100100];
ll n, x, y, res, mincost[100100];
int main(void){
    // Your code here!
    cin >> n;
    for (ll i = 0; i < n; i++){
        cin >> x >> y;
        xvec.push_back(P(x, i));
        yvec.push_back(P(y, i));
    }
    sort(xvec.begin(), xvec.end());
    sort(yvec.begin(), yvec.end());
    for (ll i = 0; i < n - 1; i++){
        ll dx = xvec[i + 1].first - xvec[i].first, smax = xvec[i].second, larx = xvec[i + 1].second;
        road[smax].push_back(P(larx, dx));
        road[larx].push_back(P(smax, dx));
        ll dy = yvec[i + 1].first - yvec[i].first, smay = yvec[i].second, lary = yvec[i + 1].second;
        road[smay].push_back(P(lary, dy));
        road[lary].push_back(P(smay, dy));
    }
    for (ll i = 0; i < n; i++){
        used[i] = false;
    }
    que.push(P(0, 0));
    while(que.size()){
        P p = que.top(); que.pop();
        if (used[p.second]) continue;
        used[p.second] = true;
        for (ll i = 0; i < road[p.second].size(); i++){
            P q = road[p.second][i];
            if (used[q.first]) continue;
            que.push(P(q.second, q.first));
        }
        res += p.first;
    }
    cout << res << endl;
}


Measured memory_bytes: 17892
#include <iostream>
#include <algorithm>
using namespace std;
#define fn(i, n) for (int i = 0; i < n; i++)
#define fs(i, s) for (int i = 0; i < s.size(); i++)
#define ll long long int
#define nl endl
int main()
{
	int n,a=0,w=0,t=0,r=0;
	cin>>n;
    fn(i,n)
	{
		string s;
		getchar();
		cin>>s;
		if(s=="AC"){a++;}
		else if(s=="TLE"){t++;}
		else if(s=="WA"){w++;}
		else if(s=="RE"){r++;}
	}
	//cout<<a<<" "<<w<<" "<<t<<" "<<r<<nl;
	cout<<"AC x "<<a<<nl;
	cout<<"WA x "<<w<<nl;
	cout<<"TLE x "<<t<<nl;
	cout<<"RE x "<<r<<nl;
}


Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>

using namespace std;


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

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    map<long long, long long> mp;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long l_i = i + a[i];
        long long r_i = i - a[i];
        ans += mp[r_i];
        mp[l_i]++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 27392
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
using namespace std;
 
#define LL long long int
const LL INF = (LL)(1e18)+1;
const LL mod = 1000000007ll;

LL N,T;
vector<pair<LL,LL>> dish;//pair<所要時間、満足度>

LL ans = 0;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}

void solve(){
	sort(dish.begin(),dish.end(), compare_by_b);//昇順に並べ替え
	vector<vector<LL>> dp(3001,vector<LL>(3001,0));
	//i-1個目までの料理から、
	//A（所要時間）の和がt以下となるよう選択した時の、
	//Bの和（満足度）の最大値をdp[i][t]とする
	//ただしdp[0][t] = 0
	for(int i=0;i<N;i++){//食べる順番は考慮しなくても最大値を求められる
		//dp[i+1]をdp[i]から求める
		for(int t=0;t<T;t++){
			//i番目を食べない場合
			//この場合 所要時間は変化しない
			dp[i+1][t] = max(dp[i+1][t],dp[i][t]);
			//i番目を食べる場合
			//この場合所要時間にdish[i].firstを足す
			if(t+dish[i].first<T){
				dp[i+1][t+dish[i].first] = max(dp[i+1][t],dp[i][t]+dish[i].second);
			}
		}
		ans = max(ans,dp[i][T-1]+dish[i].second);
	}
}
 
int main(){
	cin >> N >> T;
	for(int i=0;i<N;i++){
		LL a,b;
		cin >> a >> b;
		dish.push_back(make_pair(a,b));
	}
 
	solve();

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

Measured memory_bytes: 70784
import java.util.Scanner
import math._

object Main extends App {

  val sc = new Scanner(System.in)

  val h, w = sc.nextInt()

  println(min(minimum(h, w), minimum(w, h)))

  def minimum(h: Int, w: Int) : Long = Stream.range(1, h)
    .map(h1 => (h1, (h - h1) / 2, w / 2))
    .map {
      case (h1, h2, w2) => calc(h, w, h1, h2, w2)
    }
    .fold(1L * h * w) {
      case (ans, t) => min(ans, t)
    }

  def calc(h: Int, w: Int, h1 : Long, h2: Long, w2: Long): Long = {
    val s1 = 1L * h1 * w
    val sl2 = 1L * h2 * w
    val sl3 = 1L * (h - h1 - h2) * w
    val sr2 = 1L * (h - h1) * w2
    val sr3 = 1L * (h - h1) * (w - w2)

    var sl = 1L * h * w
    if (sl2 != 0) sl = Seq(s1, sl2, sl3).max - Seq(s1, sl2, sl3).min

    var sr = 1L * h * w
    if (sr2 != 0) sr = Seq(s1, sr2, sr3).max - Seq(s1, sr2, sr3).min

    min(sl, sr)
  }
}


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

int check(int start, int x, int **bit)
{
    for (int i = 0; i < 20; i++)
        if (bit[x][i] - bit[start][i] >= 2)
            return 0;
    return 1;
}

int bisect(int start, int x, int y, int **bit)
{
    if (y - x == 1)
        return x;
    int mid = (y - x) / 2 + x;
    if (check(start, mid, bit))
        return bisect(start, mid, y, bit);
    else
        return bisect(start, x, mid, bit);
}


int main(void)
{
    int N;
    scanf("%d", &N);
    int *L = (int *) malloc(N * sizeof(int));
    for (int i = 0; i < N; i++)
        scanf("%d", &L[i]);
    int **bit = (int **) malloc((N + 1) * sizeof(int *));
    for (int i = 0; i < N + 1; i++)
        bit[i] = (int *) calloc(20, sizeof(int));

    for (int j = 0; j < N; j++)
        for (int i = 0; i < 20; i++)
            bit[j + 1][i] = (L[j] >> i) & 1;
    for (int j = 1; j < N; j++)
        for (int i = 0; i < 20; i++)
            bit[j + 1][i] += bit[j][i];

    long cnt = 0;

    for (int i = 0; i < N; i++)
        cnt += bisect(i, i, N + 1, bit) - i;
    printf("%ld\n", cnt);
}


Measured memory_bytes: 21248
#ABC087

l = [int(input()) for _ in range(4)]


count = 0
for i in range(l[0]+1):
    s = l[3]
    if s - i * 500 >= 0:
        
        for j in range(l[1]+1):
            s = l[3] - i * 500
            if s - j * 100 >= 0:
                
                s -= j * 100
                #print(s)
                if s // 50 <= l[2]:
                    #print(i,j,s//50)
                    count += 1
                
print(count)

Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n[3];
    for(int i = 0;i < 3;i++)
    {
        cin >> n[i];
    }
    sort(n,n + 3);
    for(int i = 0;i < 3;i++)
    {
        cout << n[i];
        if(i != 2)
        {
            cout << " ";
        }
    }
    cout << "\n";

    return 0;
}


Measured memory_bytes: 3084
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <deque>
#include <stack>
#include <algorithm>
#include <memory.h>

#define rep(idx, max)			for(int idx = 0, idx##Max = (max); idx < idx##Max; idx ++)
#define rrep(idx, min, max)	for(int idx = (min), idx##Max = max; idx < idx##Max; idx ++)
#define erep(idx, min, max)	for(int idx = (min), idx##Max = max; idx <= idx##Max; idx ++)

#define rev(idx, max)			for(int idx = (max) - 1; idx >= 0; idx --)
#define rrev(idx, min, max)	for(int idx = (max) - 1, idx##Min = (min); idx >= idx##Min; idx --)
#define erev(idx, min, max)	for(int idx = (max), idx##Min = (min); idx >= idx##Min; idx --)

#define foreach(it, obj)	for(auto it = obj.begin(), it##End = obj.end(); it >= it##End; it ++)

using namespace std;

int main()
{
	int	hourglasses;
	int	boilTime;
	int allowableError;
	vector<int>	times;
	
	cin >> hourglasses >> boilTime >> allowableError;
	times.resize(hourglasses);
	rep(i, hourglasses)	{	cin >> times[i];	}
	
	int	hgIdx = -1;
	rep(i, hourglasses)
	{
		for(int t = times[i]; t <= boilTime + allowableError; t += times[i])
		{
			if(boilTime - allowableError <= t && t <= boilTime + allowableError)
			{	hgIdx = i + 1; break;	}
		}
	}
	cout << hgIdx << endl;
}

Measured memory_bytes: 1200
N, K = map(int, input().split())
H = []
for i in range(N):
    h = int(input())
    H.append(h)
H = sorted(H)
mi = 10**9
for i in range(N-K+1):
    _ = H[i+(K-1)] - H[i]
    if mi > _:
        mi = _
print(mi)

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

ll n, m, q, a[51],b[51], c[51],d[51],v[10], f=-1;

void dfs(ll x, ll p =1)
{
	if(x==n)
    {
      ll k = 0;
      rep(i, q){
      	if(v[b[i]]-v[a[i]]==c[i])
          k+=d[i];
      }
      f=max(f,k);
      return;
    }
  for(int i=p; i < m+1; i++){
    v[x]=i;
    dfs(x+1,i);
  }
}
  
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll i, j,t;
  t=1;
  string s;
  while(t--){
   cin >> n >> m >> q;
    rep(i, q){
      cin>>a[i]>>b[i]>>c[i]>>d[i];
      a[i]--; b[i]--;
    }
    dfs(0);
    cout<<f;
    cout<<"\n";
  }
  return 0;
}

Measured memory_bytes: 3664
n, m = gets.split.map(&:to_i)
ab = []
m.times do
  ab.push gets.split.map(&:to_i)
end
h = Hash.new([])
ab.each do |e|
  a = e.first
  b = e.last
  h[a] += [b]
  h[b] += [a]
end

def dfs(h, node, depth)
  if h[node].empty?
    if depth == h.size
      return 1
    else
      return 0
    end
  end
  count = 0
  h[node].each do |x|
    nh = h.dup
    h.each do |k, v|
      nh[k] -= [node]
    end
    nh[node] -= [x]
    # nh[x] -= [node]
    count += dfs(nh, x, depth + 1)
  end
  count
end

puts dfs(h, 1, 1)


Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define pb push_back
#define fi first`
#define se second
void solve()
{
	ll n;
	cin>>n;
	std::vector<ll> v(n),ans(n);
	for(auto &i:v)
		cin>>i;
	ans[1]=abs(v[1]-v[0]);
	// ans[2]=min(ans[0]+abs(v[2]-v[1]),abs(v[2]-v[0]));
	for(int i=2;i<n;i++)
		ans[i]=min(ans[i-1]+abs(v[i]-v[i-1]),ans[i-2]+abs(v[i]-v[i-2]));
	cout<<ans[n-1];

}

int main()
{


// #ifndef ONLINE_JUDGE
//     // for getting input from input.txt
//     freopen("input.txt", "r", stdin);
//     // for writing output to output.txt
//     freopen("output.txt", "w", stdout);
// #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--)
    {
        solve();
        // cout << endl;
    }

}




Measured memory_bytes: 1792
(let ((mazui (read))
      (umai (read))
      (umai-poison (read)))
  (if (< (+ umai-poison 2) (+ mazui umai))
      (princ (+ umai-poison umai))
      (princ (min (+ 1 mazui (* umai 2)) 
                  (+ umai umai-poison)))))

Measured memory_bytes: 12004
#include <iostream>
using namespace std;
using ll = long long;

int N, X;
int A[100010];

int main() {
    cin >> N >> X;
    for (int i = 0; i < N; ++i) cin >> A[i];

    ll operation = 0;
    for (int i = 0; i < N - 1; ++i) {

        if (A[i] + A[i + 1] > X) {

            int d = A[i] + A[i + 1] - X;
            if (d <= A[i + 1]) {
                A[i + 1] = A[i + 1] - d;
                operation += d;
            } else {
                A[i + 1] = 0;
                A[i] = A[i] - (d - A[i + 1]);
                operation += d;
            }
        }
    }


    cout << operation << endl;
    return 0;
}

Measured memory_bytes: 888
import java.util.Scanner;

public class Main {

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

		if (a + b == 15) {
			System.out.println("+");
		} else if (a * b == 15) {
			System.out.println("*");
		} else {
			System.out.println("x");
		}

		return;
	}
}


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

using namespace std;

typedef long long ll;

const int N = 55;

double dp[N][N];
int n;
double a[N];
ll pref[N];

int main() {
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);
  double prev = a[0];
  for(int i = 1; i < n; i++) {
    prev = (prev + a[i]) / 2.0;
  }
  cout << prev << '\n';
}

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

using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

const ll mod = 1e9 + 7;
const ll IMF = 1LL<<29;
const double PI = 3.14159265358979323846;


// ******************************CODE**********************************//





int main()
{
        vector<int> abc(3);
        for(int i = 0; i < 3; i++) cin >> abc[i];
        sort(all(abc));

        int maxval = abc[2];
        int sum = abc[0] + abc[1] + abc[2];

        if(sum%2 != maxval%2){
                maxval++;
        }

        cout << ((maxval*3) - sum)/2 << endl;
        return 0;
}


Measured memory_bytes: 256
n = int(input())
s = [[] for _ in range(n)]

for i in range(n):
    s[i] = input()
comb = [[0]*2 for i in range(2)]
    
al = 0
be = 0
ans = 0
for i in range(n):
    m = len(s[i])
    for j in range(m-1):
        if s[i][j] == "A" and s[i][j+1] == "B":
            ans += 1
    if s[i][0] == "B" and s[i][-1] == "A":
        comb[1][1] += 1
    elif s[i][0] == "B" and s[i][-1] != "A":
        comb[0][1] += 1
    elif s[i][0] != "B" and s[i][-1] == "A":
        comb[1][0] += 1
    else:
        comb[0][0] += 1
        
if comb[0][1] == 0 and comb[1][0] == 0:
    ans += max(0,comb[1][1] - 1)
elif comb[0][1] != 0 and comb[1][0] == 0:
    ans += comb[1][1]
elif comb[0][1] == 0 and comb[1][0] != 0:
    ans += comb[1][1]
else:
    ans += (comb[1][1] + 1 + min(comb[1][0]-1,comb[0][1]-1))
    
print(ans)


Measured memory_bytes: 46424
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = read_ints()
    if len(A) == len(set(A)):
        return 'YES'
    return 'NO'


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 126680
//------------------------------------------
// C++ templete 
//------------------------------------------
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long;

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//動的計画法で役に立つ関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//最大公約数と最小公倍数
ll gcd(ll a, ll b) {
    if(b==0)return a;
    return gcd(b, a%b);
}

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

vector<vector<long long> > comb(int n) {
  vector<vector<long long> > v(n + 1,vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}

ll calc(int n)
{
    ll ans=1;
    REP(i,n)
    {
        ans*=(ll)(i+1);
        ans = ans%MOD;
    }
    return ans;
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin>>N>>M;
    ll ans=0;
    if (abs(N-M)==0)
    {
        ans++;
        int n= max(N,M);
        ll kai=calc(n);
        ans *= kai*kai*2;
        ans = ans%MOD;
    }
    else if (abs(N-M)==1)
    {
        ans++;
        int n=max(N,M);
        ans*=calc(n);
        ans*=calc(n-1);
        ans=ans%MOD;
    }
    cout<<ans<<endl;
    return 0;
}



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

int main()
{
    
    int N;
    cin >> N;
    
    double result = 0;
    for (int i = 0; i < N; i++) {
        double X = 0.0;
        string U;
        cin >> X >> U;
        
        if (U == "JPY") {
            result += X;
        }else{
            result += X * 380000;
        }
    }
   
    cout << result << endl;
}

Measured memory_bytes: 256
using System;
					
public class Program
{
	public static void Main()
	{
		int K = int.Parse(Console.ReadLine()); 
		string S = Console.ReadLine();
		string ans = "";
		
		if(S.Length > K){
			for(int i=0; i<K; i++){
				ans = ans + S[i];
			}
			ans = ans + "...";
			Console.WriteLine(ans);
		}else{
			Console.WriteLine(S);
		}
		
	}
}

Measured memory_bytes: 17660
//Author rahuliitkgp
/*A thing of beauty is a joy forever,
Its loveliness increases,
it will never pass into nothingness.*/
//Men at Work :)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;

#define ff              first
#define ss              second
#define SZ(x)           ((int)(x).size())
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void cpp() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
}

int main() {
    cpp();
    ll x;
    cin>>x;
    ll sum = 100;
    ll t = 0;
    while(sum<x){
        t++;
        sum= (ll)sum*(1.01);
    }
    cout<<t<<endl;
    return 0;
}



Measured memory_bytes: 3656
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
//#include<algorithm>
//#include<cmath>
using namespace std;
int main() {
	int A[100];
	int i = 0;
	while (cin >> A[i]) {
		if (A[i] == 0) cout << A[--i] << endl;
		else i++;
	}
	return 0;
}

Measured memory_bytes: 3072
#include <iostream>
#include <cmath>
#include <cstring>
#include <utility>
using namespace std;
 
int solve(int x,int p){
    return floor(p*(1+x*0.01));
}
 
int main() {
    int n;
    int a[6][10];
    memset(a,0,sizeof(a));
    while(cin >> n && n){
        for(int i=0;i<n;i++) for(int j=0;j<5;j++) cin >> a[j][i];
        int sum=0;
        int csum;
        do{
            csum=sum;
            for(int i=0;i<n;i++){
                int current=0;
                int count=0;
                int start;
                for(int j=0;j<6;j++){
                    if(current != a[j][i]){
                        if(count>=3){
                            sum+=count*current;
                            for(int k=1;k<=count;k++){
                                a[j-k][i]=0;
                            }
//                          cout << "count:" << count << endl;
//                          cout << "current:" << current << endl;
                        }
                        current = a[j][i];
                        count=1;
                    } else {
                        count++;
                    }
                }
            }
/*          for(int i=0;i<n;i++){
                for(int j=0;j<5;j++){
                    cout << a[j][i] << " ";
                }
                cout << endl;
            }*/
            for(int j=0;j<5;j++){
                for(int i=n-1;i>0;i--){
                    if(a[j][i]==0){
                        for(int k=i-1;k>=0;k--){
                            if(a[j][k]!=0){
//                              cout << j << " swap " << i << " " << k << endl;
                                swap(a[j][k],a[j][i]);
                                break;
                            }
                        }
                    }
                }
            }
        }while(csum!=sum);
        cout << sum << endl;
    }
    return 0;
}

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

void solve()
{
	ll a, b, n; 
	cin >> a >> b >> n;
	
	
	ll mx = (a * min(n, b-1))/b;
	cout << mx;
	
}

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



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

using namespace std;

int main (void)
{
    long long X,s,t;
    cin>>X;
    s=X/500;
    X=X%500;
    t=X/5;
    int joy=1000*s+5*t;
    cout<<joy<<endl;
    return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i <= (ll)(n); ++i)
#define MAX 500010
#define MOD 1000000007
typedef long long  ll;

using namespace std;

ll ans;

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

	string S,revS;
	cin >> S;

	ll n = S.size();

	rep(i,n/2){
		if(S.substr(0,i) == S.substr(i,i)){
			ans = max(ans,2*i);
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
 struct vect{
    double x,y;
 };
int main(){
  vect a,b,c,p,l1,l2,M1,M2;
  double t1,r;
  int n;
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
    M1.x = (a.x + b.x) /2;
    M1.y = (a.y + b.y) /2;
    M2.x = (b.x + c.x)/2;
    M2.y = (b.y + c.y)/2;
    l1.y = -(b.x - a.x);
    l1.x = b.y -a.y;
    l2.y = -(c.x-b.x);
    l2.x = c.y -b.y;
    t1 = 1/(-l1.x * l2.y + l2.x * l1.y) *( -l2.y * (M2.x -M1.x) + l2.x * (M2.y -M1.y));
    p.x = M1.x + l1.x * t1;
    p.y = M1.y + l1.y * t1;
    r = sqrt((p.x - a.x)*(p.x - a.x) +(p.y - a.y)*(p.y -a.y));
    printf("%.3f %.3f %.3f\n",p.x,p.y,r);
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

vector<string> ans;

string get(int x) {
	if (x == 0) return "0 ";
	string t;
	while (x > 0) {
		int Q = x%10;
		t += (char) (Q + '0');
		x /= 10;
	}

	reverse(all(t));
	t += ' ';
	return t;
}

void print(vector<string> ans) {
	cout << ans.size() << endl;
	for (auto x : ans) {
		cout << x << endl;
	}
}

void add(char ch, int a, int b, int c) {
	string s = "";
	s += ch;
	s += ' ';
	s += get(a);
	s += get(b);
	s += get(c);

	ans.pb(s);
}

int main(){
#ifdef LOCAL
	//freopen("E_input.txt", "r", stdin);
	freopen("E_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ans.pb("+ 0 1 199999");
	ans.pb("+ 199999 199999 3");
	ans.pb("< 0 3 3");
	ans.pb("+ 0 3 0");
	ans.pb("+ 1 3 1");

	for (int i = 1; i < 30; ++i) {
		
		add('+', i+2, i+2, i+3);

	}

	int free = 10000;

	for (int i = 29; i >= 0; i--) {
		add('+', i+3, 93, free);
		add('<', free, 0, 33+i);
		free--;

		add('+', free, 33+i, free);

		for (int j = 0; j < i; ++j) {
			add('+', free, free, free);
		}

		add('+', 93, free, 93);
		free--;
	}

	for (int i = 29; i >= 0; i--) {
		add('+', i+3, 94, free);
		add('<', free, 1, 63+i);
		free--;

		add('+', free, 63+i, free);

		for (int j = 0; j < i; ++j) {
			add('+', free, free, free);
		}

		add('+', 94, free, 94);
		free--;
	}

	for (int i = 0; i < 30; ++i) {
		for (int j = 0; j < 30; ++j) {
			add('+', 33+i, 63+j, free);
			add('<', 3, free, free - 1);
			for (int e = 0; e < i+j; ++e) {
				add('+', free-1, free-1, free-1);
			}
			add('+', 2, free-1, 2);
			free -= 2;
		}
	}

	print(ans);

}


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

int main()
{
	int n;
	stack<int> train;
	while (cin >> n) {
		if (n) {
			train.push(n);
		}
		else {
			cout << train.top() << endl;
			train.pop();
		}
	}
	return 0;
}

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

int kei(char a[], char b[]){

  int i,j;
  int m = strlen(a);
  int n = strlen(b);
  int c[m+1][n+1];

  for(i=0; i<=m; i++){
    c[i][0] = 0;
  }
  for(j=0; j<=n; j++){
    c[0][j]= 0;
  }
  for(i=1; i<=m; i++){
    for(j=1; j<=n; j++){
      if(a[i-1] == b[j-1])
	c[i][j] = c[i-1][j-1]+1;
      else if(c[i-1][j] >= c[i][j-1]){
	c[i][j] = c[i-1][j];
      }
      else
	c[i][j] = c[i][j-1];
    }
  }
  return c[m][n];
}

int main(){
  char x[1000],y[1000];
  int n,i,j;
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%s %s",x, y);
    printf("%d\n",kei(x,y));
  }
  return 0;
}




Measured memory_bytes: 5736
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main(void) {
    ll n,k;
    cin>>n>>k;
    ll ans = 1;
    ll d = n-k;
    while(d>0){
        d-=k-1;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

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

constexpr int inf = 1e9;

int main() {
    int n, k; cin >> n >> k;
    vector<int> h(n);
    for(int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    vector<int> dp(n, inf);
    dp[0] = 0;
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j <= k && i - j >= 0; ++j) {
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
        }
    }

    cout << dp.back() << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

#define FOR(i,n) for(int i = 0; i < n; i++)
#define FORa(i,a,b) for(int i = a; i < b; i++)
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define SORT(a,n) sort(begin(a), begin(a) + n)
#define VSORT(v) sort(v.begin(), v.end())
#define MAX 1000000
#define ll long long
#define LOW(s) transform(s.begin(),s.end(),s.begin(),::tolower)
#define UP(s) transform(s.begin(),s.end(),s.begin(),::toupper)

//-------------------------------------------------------//

int main() {
	int a,b,c,k, sum = 0, take;
	cin >> a >> b >> c >> k;
	
	take = min(k, a);
	sum += take;
	k -= take;
	
	take = min(k, b);
	k -= take;
	
	take = min(k, c);
	sum -= take;
	
	cout << sum << endl;
	
	return 0;
}

















Measured memory_bytes: 3580
h, w = map(int, input().split())
grid = [[0 for _ in range(w+2)] for _ in range(h+2)]
for j in range(1, h+1):
  cnt = 0
  for a in input():
    cnt+=1
    grid[j][cnt]= 1 if a!='.' else 0
grid[1][1]=3

for j in range(1,h+1):
  for i in range(1,w+1):
    if grid[j][i] == 1 and grid[j-1][i] == 0 and  grid[j+1][i] == 0 and grid[j][i-1] == 0 and  grid[j][i+1] == 0:
      print('No')
      exit()
print('Yes')


Measured memory_bytes: 3064
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let s=read::<String>().chars().collect::<Vec<char>>();
    let mut a=(s.len()-1)/2;
    loop{
        let mut f=true;
        for i in 0..a{
            f&=s[i]==s[a+i]
        }
        if f{break}
        a-=1
    }
    println!("{}",a*2)
}


Measured memory_bytes: 4352
N = int(input())
WS = map(int, input().split())
WS = list(WS)

ans = 10000000
for i in range(1, N):
    a = WS[0:i]
    b = WS[i:]
    c = sum(a) - sum(b)
    d = abs(c)
    if d == 0:
        ans = d
        break
    if d < ans:
        ans = d
print(ans)

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

vector<int> g[1001];
string str[1001];

int n;

void print(int v, int depth)
{
	if (~depth){
		for (int i = 0; i < depth; i++){
			printf(".");
		}
		cout << str[v] << endl;
	}
	for (int i = 0; i < g[v].size(); i++){
		int to = g[v][i];
		print(to, depth + 1);
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		int k;
		cin >> k >> str[i];
		g[k].push_back(i);
	}
	
	print(0, -1);
}

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

long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }
long long num(long long n, long long c, long long d) {
    long long G = GCD(c, d);
    long long L = c / G * d;
    return n - n / c - n / d + n / L;
}

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << num(b, c, d) - num(a-1, c, d) << endl;
}


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

int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<n-2;i++){
        if(s[i]=='A'){
            if(s[i+1]=='B'){
                if(s[i+2]=='C')
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int i, index = 0, n, ans[200000], f;
	scanf("%d", &n);
	if (n % 2 == 0) 
		f = 1;
	else
		f = -1;
	for (i = 0; i < n; i++) {
		if (i % 2 == 0)
			index = index + i * f;
		else
			index = index - i * f;
		scanf("%d", &ans[n / 2 + index]);
	}
	for (i = 0; i < n; i++) {
		printf("%d ", ans[i]);
	}

	return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  string n;
  cin>>n;
  if(n[n.size()-1]=='3'){
    cout<<"bon"<<endl;
  }else if(n[n.size()-1]=='0'||n[n.size()-1]=='1'||n[n.size()-1]=='6'||n[n.size()-1]=='8'){
    cout<<"pon"<<endl;
  }else{
    cout<<"hon"<<endl;
  }
}

Measured memory_bytes: 3628
#include <iostream>
#include <stdio.h>
#include <math.h> 
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <string>
#include <numeric>
#include <bitset>
#include <queue>

using namespace std;

int main() {
	//input
	int n,i;
	cin >> n >> i;

	cout << n - i + 1 << endl;

	return 0;
}

Measured memory_bytes: 256