akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>

namespace Simulation
{

class Dice
{
public:
    struct DiceStruct{
        int top;
        int front;
        int right;
        int left;
        int back;
        int botom;

        //?????¢????????§???
        int current;
    };

    void set(int a, int b, int c, int d, int e, int f);
    void printTop();

    void TurnNorth();
    void TurnEast();
    void TurnSouth();
    void TurnWest();

private:
    DiceStruct m_dice{0,0,0,0,0,0,0};
}; //namespace Dice


std::unique_ptr<Dice> dice(new Dice());

} //namespace Simulation 

int main()
{
    using namespace Simulation;

    int a, b, c, d, e, f;
    std::cin >> a >> b >> c >> d >> e >> f;

    dice->set(a, b, c, d, e, f);


    std::string order = "";
    std::cin >> order;

    for (int i = 0; i < order.length(); i++) {
        if (order[i] == 'N') {
            dice->TurnNorth();
        }

        if (order[i] == 'S') {
            dice->TurnSouth();
        }

        if (order[i] == 'W') {
            dice->TurnWest();
        }

        if (order[i] == 'E') {
            dice->TurnEast();
        }
    }

    dice->printTop();

    return 0;
}

namespace Simulation
{

void Dice::set(int a, int b, int c, int d, int e, int f)
{
    m_dice.top = a;
    m_dice.front = b;
    m_dice.right = c;
    m_dice.left = d;
    m_dice.back = e;
    m_dice.botom = f;

}

void Dice::printTop()
{
    std::cout << m_dice.top << std::endl;
}

void Dice::TurnNorth()
{
    m_dice.current = m_dice.top;
    m_dice.top = m_dice.front;
    m_dice.front = m_dice.botom;
    m_dice.botom = m_dice.back;
    m_dice.back = m_dice.current;
    m_dice.current = 0;
}

void Dice::TurnEast()
{
    m_dice.current = m_dice.top;
    m_dice.top = m_dice.left;
    m_dice.left = m_dice.botom;
    m_dice.botom = m_dice.right;
    m_dice.right = m_dice.current;
    m_dice.current = 0;
}

void Dice::TurnSouth()
{
    m_dice.current = m_dice.top;
    m_dice.top = m_dice.back;
    m_dice.back = m_dice.botom;
    m_dice.botom = m_dice.front;
    m_dice.front = m_dice.current;
    m_dice.current = 0;
}

void Dice::TurnWest()
{
    m_dice.current = m_dice.top;
    m_dice.top = m_dice.right;
    m_dice.right = m_dice.botom;
    m_dice.botom = m_dice.left;
    m_dice.left = m_dice.current;
    m_dice.current = 0;
}

}//namespace Simulation

Measured memory_bytes: 3168
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using lli=long long int;
using ld=long double;


int N;
ld memo[3000][1500];
ld p[3000];

ld prob(int index,int tail)
{
	if(tail>(int)(N/2))
		return 0.0;
	if(index==N)
		return 1.0;
	if(memo[index][tail]!=-1)
		return memo[index][tail];
	return( memo[index][tail]=  ( prob(index+1,tail)*p[index] + prob(index+1,tail+1)*(1-p[index]) )  );
}

int main()
{
	cout<<fixed<<setprecision(18);
   int i,j;
   for(i=0;i<3000;i++)
   	for(j=0;j<1500;j++)
   		memo[i][j]=-1;

	cin>>N;

	for(i=0;i<N;i++)
	{
		cin>>p[i];
	}
	ld ans;
	ans=prob(0,0);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define _rep(i,m,n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;

int main(){
   int a,b; cin >> a >> b;
   int count = 0;
   int sum = 1;
   while(sum < b){
      sum += a - 1;
      count++;
   }
   print(count);
}


Measured memory_bytes: 256
from math import sqrt

def f(n):
    if n == 2:
        return 1

    if n % 2 == 0:
        return 0

    for i in range(3, round(sqrt(n)+1), 2):
        if n % i == 0:
            return 0
    else:
        return 1

def g(n):
    d = {}
    for _ in range(n):
        i = int(input())
        if not (i in d):
            d[i] = f(i)
        yield d[i]

n = int(input())
print(sum(g(n)))

Measured memory_bytes: 8556
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mode        998244353
#define mod         1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define mset(x)     memset(x,0,sizeof x)
#define pi          3.14159265358979323

const int N = 303;

ll n, m, a[N][N], ans=500;
bool vis[N];
ll cnt[N];

void solve()
{
       cin>>n>>m;
       rep(i,1,n+1) rep(j,1,m+1) cin>>a[i][j];
       vis[0]=1;
       rep(k,1,m+1)
       {
              mset(cnt);
              ll mx=-1, pos=1;
              rep(i,1,n+1)
              {
                     rep(j,1,m+1)
                     {
                            if(!vis[a[i][j]])
                            {
                                   cnt[a[i][j]]++;
                                   break;
                            }
                     }
              }
              rep(i,1,m+1) if(mx<cnt[i]) { mx=cnt[i]; pos=i; }
              vis[pos]=1;
              ans=min(ans,mx);
       }
       cout<<ans;
}


int main()
{
    speed_up
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M (ll)1000000007
#define MM (ll)1e8
#define INF (ll)1e18
#define arep(i, x, n) for (long long i = x; i < n; i++)
#define rep(i, n) for (long long i = 0; i < n; ++i)
#define pi 3.141592653589793
#define eps 0.00000001
int main() {
    ll n, k;
    cin >> n >> k;
    ll a[n];
    rep(i, n) { cin >> a[i]; }

    bool b[n - k];
    arep(i, k, n) {
        if (a[i] > a[i - k]) {
            b[i - k] = true;
        } else
            b[i - k] = false;
    }

    rep(i, n - k) {
        if (b[i])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

Measured memory_bytes: 5288
import scala.io.StdIn.{readInt, readLine};
import scala.reflect.ClassTag;
object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        val set = new OriginalSet[String](1000000);
        val ret = (0 until n).foldLeft[List[String]](Nil) { (list, i) =>
            readLine.split(" ") match {
                case Array("insert", key) => {
                    set.insert(key);
                    list;
                }
                case Array("find", key) => {
                    if (set.find(key) == true) "yes" :: list else "no" :: list;
                }
            }
        }
        println(ret.reverse.mkString("\n"));
    }
}

class OriginalSet[A](size: Int)(implicit m: ClassTag[List[A]]) {
    val set = m.newArray(size);
    def insert(key: A): Unit = {
        val index = (key.hashCode & Int.MaxValue) % size;
        if (set(index) == null) {
            set(index) = List(key);
        } else {
            if (! set(index).exists(_ == key)) set(index) = key :: set(index);
        }
    }
    
    def find(key: A): Boolean = {
        val index = (key.hashCode & Int.MaxValue) % size;
        if (set(index) == null) {
            false;
        } else {
            if (set(index).exists(_ == key)) true else false;
        }
    }
}


Measured memory_bytes: 507584
#include <bits/stdc++.h>
const int N=605,mu=1e9+7;
void reduce(int &x){ x+=x>>31&mu; }
int n,a[N],b[N],dp[N][N][N],cnt;
int c(int x){
	return x&1?x+1:x-1;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=2*n;i++){
		scanf("%d",&a[i]);
		if (a[i]>0) b[a[i]]=i;
	}
	dp[2*n+1][0][0]=1;
	int tot=n;
	for (int i=2*n;i>=1;i--){
		if (b[i] && a[c(b[i])]>0){
			if (b[i]&1) tot--;
			memcpy(dp[i],dp[i+1],sizeof(dp[i]));
			continue;
		}
		if (cnt<n) cnt++;
		if (b[i]){//位置固定 
			tot--;
			for (int j=0;j<=cnt;j++)
				for (int k=0;k<=cnt-j;k++){
					int t=dp[i+1][j][k];
					if (!t) continue;
					if (k) reduce(dp[i][j][k-1]+=dp[i+1][j][k]-mu);
					reduce(dp[i][j+1][k]+=dp[i+1][j][k]-mu); 
				}
		}else{//不固定 
			for (int j=0;j<=cnt;j++)
				for (int k=0;k<=cnt-j;k++){
					int t=dp[i+1][j][k];
					if (!t) continue;
					if (j) reduce(dp[i][j-1][k]+=1ll*t*j%mu-mu);
					if (k) reduce(dp[i][j][k-1]+=t-mu);
					reduce(dp[i][j][k+1]+=t-mu);
				}
		}
	} 
	int ans=dp[1][0][0];
	for (int i=1;i<=tot;i++) ans=ans*1ll*i%mu;
	printf("%d\n",ans);
} 

Measured memory_bytes: 859008
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
const double PI = acos(-1.0);
const long mod = 1000000007;
const long INF = 1e9 + 1;

int main() { 
  int n,m,x;
  cin >> n >> m >> x;
  int c[n],a[n][m];
  for(int i = 0; i < n; i++) {
    cin >> c[i];
    for(int j = 0; j < m; j++)
      cin >> a[i][j];
  }

  int mi = INF;
  for(int bit = 0; bit < (1 << n); bit++) {
    int num = 0,sum[m];
    for(int i = 0; i < m; i++) sum[i] = 0;
    for(int i = 0; i < n; i++) {
      if(bit & (1 << i)) {
        num += c[i];
        for(int j = 0; j < m; j++) sum[j] += a[i][j];
      }
    }
    bool flag = 1;
    for(int j = 0; j < m; j++) {
      if(sum[j] < x) {
        flag = 0; break;
      }
    }
    if(flag) mi = min(mi,num);
  }
  
  if(mi == INF) cout << -1 << endl;
  else cout << mi << endl;
}

Measured memory_bytes: 3564
import sys
from collections import Counter
N = int(input())
D = Counter(map(int, input().split()))

M = int(input())

for t in map(int, input().split()):
    if t in D:
        if D[t] > 0:
            D[t] -= 1
        else:
            print("NO")
            exit()
    else:
        print("NO")
        exit()

print("YES")



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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

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

bool isIn(int x, int y){
     return 0 <= x && x < 3 && 0 <= y && y < 3;
}

int main(){
    vector<string> button;
    button.pb("ABC"); button.pb("DEF"); button.pb("GHI");

    string input;
    while(cin >> input){
        bool is = true;
        int x, y;
        for(int i=0; i < input.size(); i++){
            bool exist = false;
            if(i == 0){
                rep(j, 3)rep(k, 3) if(button[j][k] == input[i]){x = k; y = j;}
                exist = true;
            }
            else {
                rep(j, 4){
                    int nx = x+dx[j], ny = y+dy[j];
                    if(!isIn(nx, ny)) continue;
                    if(button[ny][nx] == input[i]){x=nx; y=ny; exist = true;}
                }
            }
            if(!exist){is = false; break;}
        }
        if(is) cout << input << endl;
    }
}

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

  int n;
  cin>>n;
  
  int count = 0;

  bool ans = false;
  while(n--)
  {
      int a,b;
      cin>>a>>b;

      if(a == b)
      {
          count++;
      }
      else
      {
          count = 0;
      }
      if(count == 3)
      {
          ans = ans || 1;
      }
  }

  if(ans)
   cout<<"Yes\n";
  else
    cout<<"No\n";
}


Measured memory_bytes: 3632
$stack = []
$x=0
$y=0
$cnt = 0

def calc(x,y)
	$stack.push([x,y])
	while $stack.size() != 0 do
		(posx,posy) = $stack.pop()
		if posx+1 < $x then
			check(posx+1,posy)
		end
		if posx-1 >= 0 then
			check(posx-1,posy)
		end
		if posy+1 < $y then
			check(posx,posy+1)
		end
		if posy-1 >= 0 then
			check(posx,posy-1)
		end
	end
end

def check(x,y)
	tmp = $bord[y][x]
	if tmp == 0 then
		$bord[y][x] = 2
		$stack.push([x,y])
		$cnt += 1
	end
end
	
loop{
	line = gets
	if line==nil then
		break
	end
	sp = line.split(nil)
	
	if sp.count() != 2 then
		break
	else
		$x = sp[0].to_i()
		$y = sp[1].to_i()
		if $x == 0 and $y == 0 then
			break
		end
		
		sx = 0
		sy = 0
		$cnt = 1 
		$bord = Array.new($y).map{Array.new($x,0)}
		for i in 1..$y
			line = gets
			for j in 0..$x-1
				tmp = 0
				if line[j] == "#" then
					tmp = 1
				elsif line[j] == "@" then
					tmp = 2
					sx = j
					sy = i-1
				end
				$bord[i-1][j] = tmp
			end
		end
		calc(sx,sy)
		print $cnt
		print("\n")
	end
}

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

int main(){
  using ll = long long int ;
  ll n ;
  cin >> n ;
  vector<pair<ll,ll>> a(n) ;
  for(int i=0;i<n;i++){
    ll x,l ;
    cin >> x >> l ;
    a.at(i).first = x+l ;
    a.at(i).second = x-l ;
  }
  sort(a.begin(),a.end()) ;
  ll ans = 1 ;
  ll g ;
  g = a.at(0).first ;
  for(int i=1;i<n;i++){
    if(a.at(i).second>=g){
      ans++ ;
      g = a.at(i).first ;
    }
  }
  cout << ans << endl ;
}

Measured memory_bytes: 1920
#!/usr/bin/env python3
import numpy as np
from scipy.sparse.csgraph import shortest_path

H, W = list(map(int, input().split()))
s_table = []
node_index = 0

for _ in range(H):
    s_list = list(input())
    s_table.append(s_list)

adj = [[0] * (W * H) for _ in range(W * H)]
node_index = -1
for h_i, s_list in enumerate(s_table):
    for w_i, s in enumerate(s_list):
        node_index += 1
        if s == "#":
            continue
        if w_i + 1 < W:
            # 右隣と隣接しているか
            if s_list[w_i + 1] == ".":
                adj[node_index][node_index + 1] = 1
                adj[node_index + 1][node_index] = 1
        if h_i + 1 < H:
            # 下と隣接しているか
            if s_table[h_i + 1][w_i] == ".":
                adj[node_index][(h_i + 1) * W + w_i] = 1
                adj[(h_i + 1) * W + w_i][node_index] = 1

adj = np.array(adj)
d_matrix = shortest_path(adj)

d_matrix[d_matrix == float("inf")] = -1
ans = int(d_matrix.max())
print(ans)


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

using namespace std;

int main(void){
   int k, x;
   cin >> k >> x;
   
   int temp = 500 * k;
   
   if(temp >= x) cout << "Yes" << endl;
   else cout << "No" << endl;

}


Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let sx: i32 = input();
    let sy: i32 = input();
    let tx: i32 = input();
    let ty: i32 = input();

    let out = std::io::stdout();
    let mut buf = std::io::BufWriter::new(out.lock());

    for _ in 0..ty - sy {
        write!(buf, "U").unwrap();
    }
    for _ in 0..tx - sx {
        write!(buf, "R").unwrap();
    }
    for _ in 0..ty - sy {
        write!(buf, "D").unwrap();
    }
    for _ in 0..tx - sx {
        write!(buf, "L").unwrap();
    }
    write!(buf, "L").unwrap();
    for _ in 0..ty - sy + 1 {
        write!(buf, "U").unwrap();
    }
    for _ in 0..tx - sx + 1 {
        write!(buf, "R").unwrap();
    }
    write!(buf, "D").unwrap();
    write!(buf, "R").unwrap();
    for _ in 0..ty - sy + 1 {
        write!(buf, "D").unwrap();
    }
    for _ in 0..tx - sx + 1 {
        write!(buf, "L").unwrap();
    }
    write!(buf, "U").unwrap();
}


Measured memory_bytes: 4352
#include<iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); ++i)

using namespace std;

int main(){
  string S;
  int N, M, K, l;

  cin >> N;

  N %= 10;
  if (N==2 || N==4 || N==5 || N==7 || N==9) {
    cout << "hon" << endl;
  }else if (N==3) {
    cout << "bon" << endl;
  }else{
    cout << "pon" << endl;
  }



  return 0;
}


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

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

    if(a <= b && a <= c){
        cout << a << " " << min(b, c) << " " << max(b, c) << endl;
    }else if(b <= c && b <= a){
        cout << b << " " << min(a, c) << " " << max(a, c) << endl;
    }else{
        cout << c << " " << min(b, a) << " " << max(b, a) << endl;
    }
}


Measured memory_bytes: 3096
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

bool check(int a, int b) {
	return a > b;
}

int main() {
	int n;
	cin >> n;
	cout << n / 3 << endl;
	return 0;
}

Measured memory_bytes: 256
A, B = (int(i) for i in input().split()) 

diff = B - A 
if A % 2 == 0:
    if diff % 4 == 0:
        tp = 0 ^ B
    if diff % 4 == 1:
        tp = 1
    if diff % 4 == 2:
        tp = 1 ^ B
    if diff % 4 == 3:
        tp = 0
else:
    if diff % 4 == 0:
        tp = A
    if diff % 4 == 1:
        tp = A ^ B
    if diff % 4 == 2:
        tp = A - 1
    if diff % 4 == 3:
        tp = A - 1 ^ B

print(tp)

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    ll mn=1e8,mx=-1e8,sm=0;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        ll a;
        cin >> a;
        mn=min(mn,a);
        mx=max(mx,a);
        sm+=a;
    }
    cout << mn << " " << mx << " " << sm << endl;
    
    return 0;
}


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

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;

int main(){
    string s,t;
    int count = 0;
    int i;
    cin >> s >> t;

    for(i=0;i<3;i++){
        if( s[i] == t[i]){
            count++;
        }
    }

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


Measured memory_bytes: 256
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
n = ini()
ans = 0
for i in range(n+1):
    if i % 3 == 0:
        continue
    if i % 5 == 0:
        continue
    ans += i
print(ans)

Measured memory_bytes: 65292
from collections import deque
n, q = map(int, input().split())

edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

imos = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    imos[p] += x

q = deque([(0, -1)])
while q:
    v, p = q.pop()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        q.append((u, v))

print(' '.join([str(x) for x in imos]))


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

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

  string S;
  cin>>S;
  int a=S.size();
  int answer=0;
  rep(i, a/2)
    if(S[i] !=S[a-i-1])
      answer++;
  cout<<answer;
}

Measured memory_bytes: 256
object Main extends App {
  val n = scala.io.StdIn.readInt()
  val read = scala.io.StdIn.readLine()
  val d =  read.split(" ").map(_.toInt).toVector.sorted
  val half = d.size / 2
  val before = d(half - 1)
  val after = d(half)
  println(after - before)
}

Measured memory_bytes: 43048
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (ll)(n); i++)

int main() {
  ll n; cin >> n;
  ll t_1, t_2; cin >> t_1 >> t_2;
  rep(i, n-1) {
    ll a, b; cin >> a >> b;
    if (a == b) {
      t_1 = max(t_1, t_2);
      t_2 = t_1;
    } else if (a < b) {
      ll s_1 = t_1, s_2 = t_2;
      if (s_1%a) {
        s_1 = a*(s_1/a + 1);
      }
      if (s_1/a*b >= s_2) {
        t_1 = s_1; t_2 = s_1/a*b;
      } else {
        if (s_2%b) {
          s_2 = b*(s_2/b + 1);
        }
        t_1 = a*(s_2/b); t_2 = s_2;
      }
    } else {
      ll s_1 = t_1, s_2 = t_2;
      if (s_2%b) {
        s_2 = b*(s_2/b + 1);
      }
      if (s_2/b*a >= s_1) {
        t_1 = s_2/b*a; t_2 = s_2;
      } else {
        if (s_1%a) {
          s_1 = a*(s_1/a + 1);
        }
        t_1 = s_1; t_2 = b*(s_1/a);
      }
    }
  }
  cout << t_1 + t_2 << endl;
}

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

struct point {
	double x, y;
};

double toRadian(double r) { return (r / 180) * M_PI; }

void recKoch(int d, point p1, point p2) {
	if (d == 0) return;

	point s, u, t;

	s.x = (2 * p1.x + 1 * p2.x) / 3;
	s.y = (2 * p1.y + 1 * p2.y) / 3;
	t.x = (1 * p1.x + 2 * p2.x) / 3;
	t.y = (1 * p1.y + 2 * p2.y) / 3;
	u.x = (t.x - s.x) * cos(toRadian(60)) - (t.y - s.y) * sin(toRadian(60)) + s.x;
	u.y = (t.x - s.x) * sin(toRadian(60)) + (t.y - s.y) * cos(toRadian(60)) + s.y;

	recKoch(d-1, p1, s);
	printf("%7f %7f\n", s.x, s.y);
	recKoch(d-1, s, u);
	printf("%7f %7f\n", u.x, u.y);
	recKoch(d-1, u, t);
	printf("%7f %7f\n", t.x, t.y);
	recKoch(d-1, t, p2);
}

signed main() {
	int n;
	cin >> n;
	point p1, p2;
	p1.x = 0;
	p1.y = 0;
	p2.x = 100;
	p2.y = 0;

	printf("%7f %7f\n", p1.x, p1.y);
	recKoch(n, p1, p2);
	printf("%7f %7f\n", p2.x, p2.y);
}



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

int main()
{
    int N;
    cin >> N;
    vector<int> s(N);
    int sum = 0;
    rep(i, N)
    {
        cin >> s[i];
        sum += s[i];
    }
    sort(s.begin(), s.end());

    if (sum % 10 != 0)
    {
        cout << sum << endl;
        return 0;
    }
    else
    {
        rep(i, N)
        {
            if (s[i] % 10 != 0)
            {
                cout << sum - s[i] << endl;
                return 0;
            }
        }
    }
    cout << 0 << endl;
}


Measured memory_bytes: 256
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <set>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
//const ll mod = 1000000007;
ll max(ll a, ll b) {
	if (a < b)
		return b;
	else
		return a;

}
ll min(ll a, ll b) {
	if (a < b)
		return a;
	else
		return b;

}

int main() {
	ll N;

	cin >> N;
	if (N % 2 == 0) {

		
		printf("%.10f", 1.0 / 2.0);
	}

	else {

		printf("%.10f", (double)(N / 2 + 1) / (double)N);

	}




	return 0;
}

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

using namespace std;

int main() {
  long long x = 0;
  long long year = 0;
  cin >> x;
  long long now = 100;
  while (now < x) {
    now += now * 0.01;
    year++;
  }
  cout << year << endl;
  return 0;
}

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

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

  int ans = 0;
  for(int i=0; i < n; i++) {
    if (s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C') ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3596
macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

fn main() {
    let n = get!(String);
    for nn in n.chars() {
        if nn == '1' {
            print!("9")
        } else {
            print!("1")
        }
    }
}

Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> v(m, 0);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int a;
            cin >> a;
            v[a-1] += 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (v[i] == n) {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main{

	public static void main(String[] args){
		solve();
	}

	public static void solve(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0){
				break;
			}
			String[] s = new String[n];
			for(int i=0;i<n;i++){
				s[i] = sc.next();
			}
			boolean[] judge = new boolean[n];
			Arrays.fill(judge,true);
			int[] num = {5,7,5,7,7,99};
			int now = 0;
			int counter = 0;
			int numi = 0;
			int x = 0;
			while(true){
				now = x;
				for(int i=x;i<n;i++){
					counter += s[i].length();
					//System.out.println(i+" "+counter+" "+numi);
					if(counter == num[numi]){
					now = i+1;
					numi++;
					counter = 0;
					}
					else if(counter>num[numi]){
						break;
					}
					if(numi>4){
						for(int j=i+1;j<n;j++){
							judge[j] = false;
						}
						break;
					}
				}
				if(numi>4){
					break;
				}
				counter = 0;
				numi = 0;
				Arrays.fill(judge,true);
				x++;
				for(int i=0;i<x;i++){
					judge[i] = false;
				}
			}
			for(int i=0;i<n;i++){
				if(judge[i]){
					System.out.println(i+1);
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 32536
S = input()
T = input()
N = len(S)
M = len(T)

judge = False
for i in range(N-M+1):
    c = N-M-i
    for j,t in enumerate(T):
        if c > N-1:
            break
        if t == S[c] or S[c] == "?":
            c += 1
            if j == M-1:
                judge = True
        else:
            break
    if judge:
        S= S[:N-M-i]+T+S[N-i:]
        break
#出力
if judge:
    for i in range(N):
        print(S[i] if S[i] != "?" else "a",end="")
else:
    print("UNRESTORABLE")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define int long long int
#define f(i,a,b) for (int i= a; i <b; ++i)
using namespace std;
double dp[3005][3005];
double solve(int i,int x,double a[])
{
    if(x==0)
        return 1;
    if(i==0)
        return 0;
    if(dp[i][x]> -.9)
        return dp[i][x];
    dp[i][x]=a[i]*solve(i-1,x-1,a)+(1-a[i])*solve(i-1,x,a);
    return dp[i][x];
}

signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    memset(dp,-1,sizeof dp);
    double a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cout<<fixed<<setprecision(10)<<solve(n,(n+1)/2,a);
}



Measured memory_bytes: 71040
use std::io;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}


fn main() {
    let line: Vec<i32> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let a = line[0];
    let b = line[1];
    let c = line[2];

    println!("{}", cmp::max(0, c - (a-b)));
}


Measured memory_bytes: 4352
#include <iostream> 
#include <cstring>
#include <algorithm>
#define INF 500050
double a[INF];
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	double sum = a[1]+a[2];
	long long k = 2;
	for(int i=3; i<=n; i++) {
		sum += 1.0*k*a[i];
		k *= 2;
	}
	sum/=k*1.0;
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <ios>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

int group(int x)
{
    switch (x) {
    case 1:
    case 3:
    case 5:
    case 7:
    case 8:
    case 10:
    case 12:
        return 0;
    case 4:
    case 6:
    case 9:
    case 11:
        return 1;
    case 2:
        return 2;
    default:
        return -1;
    }
}

int main()
{
    int x, y;
    cin >> x >> y;
    if (group(x) == group(y)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
}

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

using namespace std;

const int CMax = 100002;

int n, l, r, ats;

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d %d", &l, &r);
        ats += r - l + 1;
    }
    cout << ats << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

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

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

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

	string n;
	while (cin >> n) {
		if (n == "0") break;
		ll sum = 0;
		for (char c : n) {
			sum += c - '0';
		}
		cout << sum << endl;
	}
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 998244353;
#define REP(i,n) for(int i=0;i<(int)n;++i)

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

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll N;
string S;

ll powLL(ll a, ll n){
    ll res = 1;
    while(n>0){
        if(n&1){
            res *= a;
            res %= mod;
        }
        a = a*a;
        a %= mod;
        n >>= 1;
    }
    return res;
}

ll dp[202020][2];

ll rec(ll k, bool tight, ll made){
    if(dp[k][tight] >= 0) return dp[k][tight];
    if(k==made) return 1;

    ll res = 0;

    ll ub = (tight ? S[k]-'0' : 1);
    for(int d=0;d<=ub;d++){
        res += rec(k+1, ((tight && d==ub) ? true : false), made);
        res %= mod;
    }

    dp[k][tight] = res;
    return res;
}

ll calc_pos(ll d){
    ll l = N/d;
    REP(i, 202020)REP(j, 2) dp[i][j] = -1;
    ll dig = rec(0, 1, l);
    dig--;
    string T = "";
    string A = S.substr(0, l);
    string B = "";
    REP(i, l) B += (S[i]=='1' ? '0' : '1');

    REP(i, d){
        if(i%2==0) T += A;
        else T += B;
    }
    if(T<=S) dig++;
    return dig;
}

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

    cin >> N >> S;
    vector<ll> cum(N+1, 0);
    REP(i, N) cum[i+1] = cum[i] + (S[i]=='1');

    //bit DP
    REP(i, 202020)REP(j, 2) dp[i][j] = -1;
    ll total = rec(0, 1, N);
    //cout << rec(0, true) << endl;

    vector<ll> yaku;
    for(int i=2;i<=N;i++){
        if(N%i==0 && i%2==1) yaku.push_back(i);
    }

    ll M = yaku.size();
    vector<ll> num(M, 0);

    ll res = 0;

    for(int i=M-1;i>=0;i--){
        ll d = yaku[i];
        ll l = N/d;
        ll pos = calc_pos(d);
        num[i] += pos;
        num[i] %= mod;
        for(int j=i-1;j>=0;j--){
            if(yaku[i]%yaku[j]==0){
                num[j] -= num[i];
                num[j] += mod;
                num[j] %= mod;
            }
        }
        res += (2*l*num[i])%mod;
        res %= mod;
    }
    //cout << num << endl;

    ll sum = 0;
    REP(i, M){
        sum += num[i];
        sum %= mod;
    }

    ll tmp = (total - sum + mod)%mod;
    tmp *= (2*N);
    tmp %= mod;
    res += tmp;
    res %= mod;
    
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 21356
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;


int main() {
    ll c[26];
    char txt[200002];
    scanf(" %s", txt);
    ll t = strlen(txt);
    fill(c,c+26,0);
    for(int i = 0;i<t;i++) c[txt[i]-'a']++;
    ll r = (t * (t-1)) >> 1;
    ll s = 0;
    for(int i = 0;i<26;i++) {
      s += (c[i] * (c[i]-1) )>> 1;
    }
    printf("%lli\n", 1 + (r-s));
    return 0;
}


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

int main() {
    int N, K, S;
    cin >> N >> K >> S;
    vector<int>ans;
    for (int i = 0; i < K; ++i) {
        ans.push_back(S);
    }
    if (S == 1000000000) {
        for (int i = 0; i < N - K; ++i) {
            ans.push_back(S - 1);
        }
    } else {
        for (int i = 0; i < N - K; ++i) {
            ans.push_back(S + 1);
        }
    }
    for (int x: ans) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}

Measured memory_bytes: 1784
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    double N; cin >> N;
    cout << fixed << setprecision(10);
    if ((int)N % 2 == 0) {
        cout << 1.0 / 2 << endl;
    } else {
        cout << (floor(N/2) + 1) / N << endl;
    }
}


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

int main()
{
	string a, b, c;
	cin >> a >> b >> c;
	int an=a.size()-1, bn=b.size()-1;
	if (a[an] == b[0] && b[bn] == c[0])cout << "YES";
	else { cout << "NO"; }
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;


int main(void) {
  int n;
  cin >> n;
  vector<int> v;
  
  rep(i, 0, n) {
    int a;
    cin >> a;
    int l = -1, r = sz(v);
    while (r-l>1) {
      int m = (l+r)/2;
      if (v[m]>=a) l = m;
      else r = m;
    }
    if (r==sz(v)) v.pb(a);
    else v[r] = a;
  
  }
  
  int ans = sz(v);

  cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3900
W, H, N = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(N)]
x_black = [0] * W 
y_black = [0] * H 
def get_area(x, y, a): 
        if a == 1:
                for i in range(x):
                        x_black[i] = 1 
        if a == 2:
                for i in range(x, W): 
                        x_black[i] = 1 
        if a == 3:
                for i in range(y):
                        y_black[i] = 1 
        if a == 4:
                for i in range(y, H): 
                        y_black[i] = 1 
for i in xy: 
        get_area(i[0], i[1], i[2])
print(x_black.count(0) * y_black.count(0))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define L long long
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define pii pair<pi,int>
#define aa first
#define bb second
#define xx aa.aa
#define yy aa.bb
#define zz bb
#define mp make_pair
#define mpp(a,b,c) mp(mp(a,b),c)
using namespace std;
const int q=1000000007;
int n,m,t,x[60],y[60],p,qq,g[60],c[1010][1010],r,ans=1;
bool z[60];
vi a[60];
pi f[110];
inline int power(int a,int b)
{
	if(!b)
	  return 1;
	int c=power(a,b>>1);
	c=(L)c*c%q;
	if(b&1)
	  c=(L)c*a%q;
	return c;
}
inline int calc(int n)
{
	int i,k=0;
	for(i=0;i<n;i++)
	  k=(k+power(t,__gcd(n,i)))%q;
	k=(L)k*power(n,q-2)%q;
	return k;
}
inline void tj(int i,int j)
{
	int k;
	x[i]=y[i]=++p;
	z[i]=1;
	if(j)
	  {
	   f[++qq]=mp(j,i);
	   g[++r]=i;
	  }
	for(auto k:a[i])
	  if(k!=j)
	    if(!x[k])
	      {
		   tj(k,i);
		   y[i]=min(y[i],y[k]);
		   if(y[k]>=x[i])
		     {
			  int u=0,v=0;
			  while(g[r]!=k)
			    {
				 z[g[r]]=0;
				 u++;
				 r--;
				}
			  z[g[r]]=0;
			  u++;
			  r--;
			  while(f[qq]!=mp(i,k))
			    {
				 qq--;
				 v++;
				}
			  qq--;
			  v++;
			  u++;
			  if(v<u)
			    ans=(L)ans*t%q;
			  else if(v==u)
			    ans=(L)ans*calc(u)%q;
			  else
			    ans=(L)ans*c[v+t-1][t-1]%q;
			 }
		  }
		else if(z[k] && x[k]<x[i])
		  {
		   y[i]=min(y[i],x[k]);
		   f[++qq]=mp(i,k);
		  }
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k;
	scanf("%d%d%d",&n,&m,&t);
	for(i=1;i<=m;i++)
	  {
	   scanf("%d%d",&j,&k);
	   a[j].pb(k);
	   a[k].pb(j);
	  }
	for(i=0;i<=1e3;i++)
	  for(j=1,c[i][0]=1;j<=i;j++)
	    c[i][j]=(c[i-1][j]+c[i-1][j-1])%q;
	for(i=1;i<=n;i++)
	  if(!x[i])
	    tj(i,0);
	printf("%d\n",ans);
	return 0;
}


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




int main() {
 int N,R,ans;
 cin >> N >> R;

 if(N >= 10) ans = R;
 if(N <  10) ans = R+100*(10-N);

 cout << ans;
}



Measured memory_bytes: 256
(let* ((a (read))
       (b (read))
       (c (read))
       (x (read))
       (y (read)))
  (princ (min
          (+ (* 2 c (min x y)) (* a (- x (min x y))) (* b (- y (min x y))))
          (+ (* 2 c (max x y)))
          (+ (* a x) (* b y)))))

Measured memory_bytes: 13028
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vector<int, int> > vvi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    char a;
    cin >> a;
    if(a=='a' || a=='e' || a=='i' || a=='u' || a=='o'){
        cout << "vowel";
    }
    else cout << "consonant";
}

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

using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

#define ndl cout << '\n'
#define sz(v) int(v.size())
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define present(a, x) (a.find(x) != a.end())
#ifdef LOCAL
#define db(...) ({cout << "> Line " << __LINE__  \
		<< ": "; _db(#__VA_ARGS__, __VA_ARGS__);})
#define RNG() rng()
#else
#define db(...) true
#define RNG() true
#endif

template<class T>
void _db(const char *dbStr, T e) {
	cout << dbStr << " = " << e << endl;
}
template<class T, class... L>
void _db(const char *dbStr, T e, L... r) {
  while(*dbStr != ',') cout << *dbStr++;
  cout << " = " << e << ','; _db(dbStr + 1, r...);
}
template<class S, class T>
ostream& operator<<(ostream& o, const map<S, T>& v) {
	o << "["; int i = 0;
	for (const pair<S, T>& pr : v) o << (!i++ ? "" : ", ") << "{"
	<< pr.fs << " : " << pr.sc << "}"; return o << "]";
}
template<template <class, class...> class S, class T, class... L>
ostream& operator<<(ostream& o, const S<T, L...>& v) {
	o << "["; int i = 0;
	for (const auto& e : v) o << (!i++ ? "" : ", ") << e;
	return o << "]";
}
template<class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& pr) {
	return o << "(" << pr.fs << ", " << pr.sc << ")";
}
ostream& operator<<(ostream& o, const string& s) {
	for (const char& c : s) o << c;
	return o;
}

template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = VV<V<T>>;
using ll = long long;
using pii = pair<int, int>;
using vi = V<int>;
using vii = V<pii>;
using vvi = VV<int>;
using mii = map<int, int>;
using umii = unordered_map<int, int>;
using si = set<int>;
using usi = unordered_set<int>;

int N, K;
vi a;
map<ll, int> M;


int main() {
	#ifdef LOCAL
	auto stTime = clock();
//	freopen("in.txt", "r", stdin);
	mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
	#endif
	ios::sync_with_stdio(false);
	cout.precision(10);
	cin.tie(0);

	cin >> N >> K;

	a.assign(N + 1, 0);
	V<ll> sum(N + 1, 0);

	for (int i = 1; i <= N; ++i) {
		cin >> a[i];
		sum[i] = a[i] + sum[i - 1];
	}

	for (int i = 1; i <= min(N, K - 1); ++i) {
		db(sum[i], i);
		++M[(sum[i] - i) % K];
	}

	db(M);

	int j = min(N, K - 1) + 1;

	ll ans = 0, sub = 0;

	for (int i = 1; i <= N; ++i) {
		ans += M[sub % K];
		--M[(sum[i] - i) % K];
		if (j <= N)
			++M[(sum[j] - j) % K];
		++j;
		sub += a[i] - 1;
		db(sub, M);
	}

	cout << ans << '\n';


	#ifdef LOCAL
	cout << "\n\n\nExecution time: " <<
		(clock() - stTime) * 1e3 / CLOCKS_PER_SEC << " ms" << endl;
	#endif
    return 0;
}


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

using namespace std;
using ll =long long;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
using P = pair<int,int>;
//Write From this Line

int main()
{
	ll a;
	cin >> a;
	string b;
	cin >> b;
	int B = (b[0]-'0') * 100 + (b[2]-'0') * 10 + (b[3]-'0');
	cout << (a * B) / 100 << endl;
}


Measured memory_bytes: 3636
# coding: utf-8

f = 1
n, m = map(int, input().split())

li = [-1] * n

for _ in range(m):
    s, c = map(int, input().split())
    if li[s-1] != -1 and li[s-1] != c:
        f = 0
        break
    else:
        li[s-1] = c

if n > 1 and li[0] == 0:
    f = 0
else:
    if -1 in li and li.index(-1) == 0:
        if n > 1:
            li[0] = 1
        else:
            li[0] = 0
    while -1 in li:
        li[li.index(-1)] = 0

if f:
    for i in range(n):
        print(li[i], end='')
    print('')
else:
    print('-1')

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
using namespace std; 
#define ll long long int 
#define pb push_back
#define vv vector<ll>
#define fr(i,x) for(int i=0;i<x;i++)
#define MAX 10000005
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};

bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    
    if(a.first == b.first) return a.second<b.second;
    return (a.first < b.first); 
}

ll a[MAX];
void sieve(){
    for (int i = 1; i < MAX; i++)
    {
        for (int j = i; j <= MAX; j+=i)
        {
            a[j]++;
        }
        
    }
    
}
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
    

    ll n,d,x,y,r,cnt = 0,k;
    cin >> n >> d;
    while (n)
    {
        cin >> x >> y;
        //cout << sqrt(pow(x,2)+pow(y,2)) << endl;
        //cout << h << endl;
        if(sqrt(pow(x,2)+pow(y,2)) <= d) cnt++;
        n--;
    }
    cout << cnt << endl;
    
   
    
    
    
    
    
    
}

Measured memory_bytes: 3668
#include<stdio.h>
long long int gcd(long long int a,long long int b){
	if(!b)return a;
	else gcd(b,a%b);
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d\n",gcd(a,b));
	return 0;
}
	

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

int main(){
	int a,b,c,x;
	cin >> a >> b >> c >> x;

	int res = 0;

	for(int i = 0; i <= a; i++){
		for(int j = 0; j <= b; j++){
			for(int k = 0; k <= c; k++){
				if(i*500 + j*100 + k*50 == x){
					res++;
				}
			}
		}
	}

	cout << res << "\n";
	return 0;
}


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

int main(){
    vector<string> v{"Sunny","Cloudy","Rainy"};
    string s;
    cin>>s;
    for(int i=0;i<3;i++){
        if(s==v[i]){
            cout<<v[(i+1)%3];
        }
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	static Node r;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x;
		String com;
		
		for(int i=0; i<n; i++){
			com = sc.next();
			if(com.equals("insert")){
				x = sc.nextInt();
				insert(new Node(x, null, null, null));
			} else if (com.equals("find")){
				x = sc.nextInt();
				if(find(r, x) != null) System.out.println("yes");
				else System.out.println("no");
			} else if (com.equals("print")){
				inorder(r);
				System.out.println();
				preorder(r);
				System.out.println();
			}
		}
	}
	
	static Node find(Node u, int k){
		while (u != null && k != u.key){
			if(k < u.key) u = u.l;
			else u = u.r;
		}
		return u;
	}
	
	static void insert(Node z){
		Node y = null;
		Node x = r;
		
		while (x != null){
			y = x;
			if (z.key < x.key){
				x =  x.l;
			} else {
				x = x.r;
			}
		}
		z.p = y;
		
		if (y == null){
			r = z;
		} else {
			if(z.key < y.key){
				y.l = z;
			} else {
				y.r = z;
			}
		}
	}

	static void inorder(Node u){
		if (u == null) return;
		inorder(u.l);
		System.out.print(" " + u.key);
		inorder(u.r);
	}
	static void preorder(Node u) {
		if (u == null) return;
		System.out.print(" " + u.key);
		preorder(u.l);
		preorder(u.r);
	}
}


class Node {
    int key;
    Node p = null;
	Node l = null;
	Node r = null;
    public Node(int key, Node p,Node l, Node r) {
    	this.key = key;
        this.l = l;
        this.r = r;
        this.p = p;
    }
}


Measured memory_bytes: 201500