akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
    cin >> A[i];
  map<int, int> mp;
  for (int i = 0; i < N; i++)
    mp[A[i]]++;
  vector<long> l2, l4;
  for (auto a : mp)
  {
    if (2 <= a.second)
      l2.push_back(a.first);
    if (4 <= a.second)
      l4.push_back(a.first);
  }
  long ans1 = 0;
  long ans2 = 0;
  if (2 <= l2.size())
    ans1 = l2[l2.size() - 1] * l2[l2.size() - 2];
  if (1 <= l4.size())
    ans2 = l4[l4.size() - 1] * l4[l4.size() - 1];
  cout << max(ans1, ans2) << endl;
  return 0;
}

Measured memory_bytes: 5376
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()

ans = 0
if N >= 2:
    ans += N * (N - 1) // 2

if M >= 2:
    ans += M * (M - 1) // 2

print(ans)

Measured memory_bytes: 6860
use std::io::BufRead;
use std::cmp::Ordering;
fn main() {
    let handle = std::io::stdin();
    let mut taro = 0;
    let mut hanako = 0;
    for line in handle.lock().lines().skip(1) {
        let line = line.unwrap();
        let line = line.trim();
        let two_cards: Vec<String> = line.split_whitespace()
            .map(|a| a.to_string()).collect();
        match two_cards[0].partial_cmp(&two_cards[1]) {
            Some(Ordering::Equal) => {
                taro += 1;
                hanako += 1;
            },
            Some(Ordering::Greater) => {
                taro += 3;
            },
            Some(Ordering::Less) => {
                hanako += 3;
            },
            None => {}
        }
    }
    println!("{} {}", taro, hanako);
}


Measured memory_bytes: 5052
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	A, B, M := ReadInt(), ReadInt(), ReadInt()
	a := ReadInts(A)
	b := ReadInts(B)
	ans := Min(a...) + Min(b...)
	for i := 0; i < M; i++ {
		x, y, c := ReadInt()-1, ReadInt()-1, ReadInt()
		v := a[x] + b[y] - c
		ans = Min(ans, v)
	}
	fmt.Println(ans)
}

func Min(xs ...int) int {
	min := xs[0]
	for _, x := range xs[1:] {
		if min > x {
			min = x
		}
	}
	return min
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 6320
#include <cstdio>

int main() {
  int a,b,c;
  std::scanf("%d%d%d",&a,&b,&c);
  
  if (a<=b && a<=c) {
      if (b<=c) {
          std::printf("%d %d %d\n",a,b,c);

      } else {
          std::printf("%d %d %d\n",a,c,b);

      }
  } else if (b<=c && b<=a) {
      if (c<=a) {
          std::printf("%d %d %d\n",b,c,a);
      } else {
          std::printf("%d %d %d\n",b,a,c);

      }

  } else {
      if (a<=b) {
          std::printf("%d %d %d\n",c,a,b);

      } else {
          std::printf("%d %d %d\n",c,b,a);

      }

  }
  
}


Measured memory_bytes: 2724
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<iostream>
#include<algorithm>
#define mp make_pair
using namespace std;
typedef pair<long long,long long> pll;
typedef long long LL;
int read()
{
	int s=0;int c=getchar(),f=1;
	while(c<48||c>57)
	{
		if(c==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57) s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s*f;
}
void write(int x)
{
	if(x>=10) write(x/10);
	putchar(x%10+48);
}
const int maxn=5555;
const int base1=233;
const int base2=344;
const int mod1=1000000007;
const int mod2=998244353;
int N;
char ss[maxn];
int bs1[maxn],bs2[maxn];
pll f[maxn];
bool check(int x)
{
	int Mx=N-x-x+1;
	for(int i=1;i<=Mx;++i)
	{
		pll stdd=mp((f[i+x-1].first-f[i-1].first*bs1[x]%mod1+mod1)%mod1,(f[i+x-1].second-f[i-1].second*bs2[x]%mod2+mod2)%mod2);
		for(int j=i+x;j<=Mx+x;++j)
		{
			if(stdd==mp((f[j+x-1].first-f[j-1].first*bs1[x]%mod1+mod1)%mod1,(f[j+x-1].second-f[j-1].second*bs2[x]%mod2+mod2)%mod2)) return true;
		}
	}
	return false;
}
int main()
{
	N=read();scanf("%s",ss+1);
	bs1[0]=bs2[0]=1;
	for(int i=1;i<=N;++i)
	{
		bs1[i]=(LL)bs1[i-1]*base1%mod1;
		bs2[i]=(LL)bs2[i-1]*base2%mod2;
		f[i]=mp((f[i-1].first*base1+ss[i])%mod1,(f[i-1].second*base2+ss[i])%mod2);
	}
	int ans=0,l=1,r=N;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	write(ans);
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define mod 1000000007
#define N 500043
#define mp(a,b) make_pair(a,b)
#define loop(a,b) for(int i=a;i<b;i++)
#define test int t; cin >> t; while(t--)
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll>vec(n);
    loop(0,n) cin >> vec[i];
    ll prevmin=vec[0];
    ll tota=1000;
    for(int i=1;i<n;i++)
    {
        if(vec[i]>prevmin)
        {
            tota=tota+((tota/prevmin)*(vec[i]-prevmin));
            prevmin=vec[i];
        }
        else
            prevmin=vec[i];
    }
    cout << tota;
}


Measured memory_bytes: 3640
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

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

	int n;
	cin >> n;

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

	int res = 0;
	for (int i = 1; i+1 < n; ++i) {
		if (min(vals[i-1], vals[i+1]) < vals[i] && vals[i] < max(vals[i-1], vals[i+1])) ++res;
	}
	cout << res << '\n';
}


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

int main()
{
    int N;
    int K;
    cin >> N >> K;
    int ans=1;
    while (N)
    {
    	if ((ans * 2) < (ans + K)){
          ans *=2;
        }else {
          ans += K;
        }
        N--;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define db cout<<"db: "
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define all(v) v.B,v.E
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;

    cin>>n;
    pii arr[n];
    rep(i,0,n)cin>>arr[i].F>>arr[i].S;
    
    rep(i,2,n)
    {
        bool ok=1;
        for(j=0;j<=2;j++) if(arr[i-j].F!=arr[i-j].S) ok=0;
        if(ok)
        {
            cout<<"Yes";
            return 0;
        }
    }
cout<<"No";
    return 0;
}

Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var abc = ReadLongs();
            var a = abc[0];
            var b = abc[1];
            var c = abc[2];

            var d = c - a - b;

            if (d > 0 && d * d > 4 * a * b)
            {
                WriteLine("Yes");
            }
            else
            {
                WriteLine("No");
            }
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,-1,0,1},dy={1,0,-1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	int ga,gb,sa,sb,ba,bb;
	cin >> ga >> sa >> ba >> gb >> sb >> bb;
	vector<ll> dp(n+1);
	rep(i,n + 1){
		if(i - ga >= 0) dp[i] = max(dp[i], dp[i - ga] + gb);
		if(i - sa >= 0) dp[i] = max(dp[i], dp[i - sa] + sb);
		if(i - ba >= 0) dp[i] = max(dp[i], dp[i - ba] + bb);
		dp[i] = max(dp[i], (ll)i);
	}
	vector<ll> dp1(dp[n] + 1);
	rep(i,dp[n] + 1){
		if(i - gb >= 0) dp1[i] = max(dp1[i], dp1[i - gb] + ga);
		if(i - sb >= 0) dp1[i] = max(dp1[i], dp1[i - sb] + sa);
		if(i - bb >= 0) dp1[i] = max(dp1[i], dp1[i - bb] + ba);
		dp1[i] = max(dp1[i], (ll)i);
	}
	cout << dp1[dp[n]] << endl;
}


Measured memory_bytes: 195584
using System;
using System.Linq;
class Program
{
  static void Main (string[] args)
  {
    int a = int.Parse(Console.ReadLine());
    int b = int.Parse(Console.ReadLine());
    int c = int.Parse(Console.ReadLine());
    int d = int.Parse(Console.ReadLine());
    int e = int.Parse(Console.ReadLine());
    
    int[] array = new int[] { a, b, c, d, e };
    
    int minValue = array[0] % 10;
    int minIndex = 0;
    for (int i = 1; i < 5; i++) {
      int n = array[i] % 10;
      if (n != 0 && n < minValue) {
        minValue = n;
        minIndex = i;
      }
    }
    
    int time = 0;
    for (int i = 0; i < 5; i++) {
      if (i != minIndex) {
        time += ((array[i]/10) * 10);
        if (array[i]%10 != 0) {
          time += 10;
        }
      }
    }
    time += array[minIndex];
    Console.WriteLine(time);
  }
}


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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
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; }
//template end



int main(){
   int n; scanf("%d",&n);
   int cnt[10][10]={};
   rep(i,1,n+1){
      string s; tostr(i,s);
      cnt[s.front()-'0'][s.back()-'0']++;
   }
   int ans=0;
   rep(i,1,n+1){
      string s; tostr(i,s);
      ans+=cnt[s.back()-'0'][s.front()-'0'];
   }
   printf("%d\n",ans);
   return 0;
}

Measured memory_bytes: 256
S = str(input())

if S =="SUN":
	print(7)
elif S == "MON":
	print(6)
elif S =="TUE":
	print(5)
elif S =="WED":
	print(4)
elif S =="THU":
	print(3)
elif S =="FRI":
	print(2)
else:
	print(1)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;
typedef double db;
int read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    int x=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

const int N=3*1e5+5;
const ll inf=1e16;

int n,m,x,y,a[N],stack[N],top;
ll f[N],g[N],h[N],ans[N],t[N],c[N],tmp[N],sum[N];

db P(int y,int x) {
    return (t[y]+(ll)y*(y-1)/2+sum[y]-t[x]-(ll)x*(x-1)/2-sum[x])*1.0/(y-x);
}

void Dp() {
    fo(i,1,n) sum[i]=sum[i-1]+a[i];stack[top=1]=0;
    fo(i,1,n) {
        while (top>1&&P(stack[top],stack[top-1])<=i) top--;
        int now=stack[top];
        t[i]=max(t[i-1],t[now]+(ll)(i-now)*(i-now+1)/2+sum[now]-sum[i]);
        while (top>1&&P(stack[top],stack[top-1])<P(i,stack[top])) top--;
        stack[++top]=i;
    }
}

void solve(int l,int r) {
    if (l==r) {
        h[l]=max(h[l],g[r+1]+f[l-1]+1-a[l]);
        return;
    }
    int mid=l+r>>1;
    stack[top=1]=l-1;
    fo(i,l,mid-1) {
        while (top>1&&P(stack[top],stack[top-1])<P(i,stack[top])) top--;
        stack[++top]=i;
    }
    fo(i,mid,r) {
        while (top>1&&P(stack[top],stack[top-1])<=i) top--;
        int now=stack[top];
        tmp[i]=t[now]+(ll)(i-now)*(i-now+1)/2+sum[now]-sum[i]+g[i+1];
    }
    fd(i,r-1,mid) tmp[i]=max(tmp[i],tmp[i+1]);
    fo(i,mid,r) h[i]=max(h[i],tmp[i]);
    solve(l,mid);solve(mid+1,r);
}
int main() {
//    freopen("genocide.in","r",stdin);
//    freopen("genocide.out","w",stdout);
    n=read();
    fo(i,1,n) a[i]=read();
    Dp();fo(i,1,n) f[i]=t[i];
    fo(i,1,n/2) swap(a[i],a[n-i+1]);
    Dp();fo(i,1,n) g[i]=t[n-i+1];
    fo(i,1,n) ans[i]=-inf;

    fo(i,1,n/2) swap(a[i],a[n-i+1]);
    fo(i,1,n) t[i]=f[i];
    fo(i,1,n) sum[i]=sum[i-1]+a[i];
    fo(i,1,n) h[i]=-inf;
    solve(1,n);
    fo(i,1,n) ans[i]=max(ans[i],h[i]);

    fo(i,1,n) swap(f[i],g[i]);
    fo(i,1,n/2) {
        swap(a[i],a[n-i+1]);
        swap(f[i],f[n-i+1]);
        swap(g[i],g[n-i+1]);
    }
    fo(i,1,n) t[i]=f[i];
    fo(i,1,n) sum[i]=sum[i-1]+a[i];
    fo(i,1,n) h[i]=-inf;
    solve(1,n);
    fo(i,1,n) ans[i]=max(ans[i],h[n-i+1]);

    fo(i,1,n/2) {
        swap(f[i],f[n-i+1]);
        swap(g[i],g[n-i+1]);
        swap(a[i],a[n-i+1]);
    }
    fo(i,1,n) swap(f[i],g[i]);

    for(m=read();m;m--) x=read(),y=read(),printf("%lld\n",max(f[x-1]+g[x+1],ans[x]+a[x]-y));
    return 0;
}

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

bool dividable(int n, int a[]){
  for (int i = 0; i < n; i++) {
    switch (a[i] % 2) {
      case 0:break;
      default:return false;
    }
  }
  return true;
};

void update(int n, int a[]){
  for (int i = 0; i < n; i++) {
    a[i] = a[i] / 2;
  }
};

void input(int n, int a[]){
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
};

int main(){
  int n,a[200],counter = 0;
  cin >> n ;
  input(n,a);
  while (dividable(n,a)) {
    update(n,a);
    counter++;
  }
  cout << counter << endl;
}


Measured memory_bytes: 256
def main():
    h1,m1,h2,m2,k = map(int,input().split())
    start = 60*h1+m1
    end = 60*h2+m2
    #print(start,end)
    total = 0
    for i in range(start,end+1):
        if i+k < end:
            total += 1

    print(total)

main()


Measured memory_bytes: 62904
# https://atcoder.jp/contests/abc053/tasks/arc068_b
# 具体的操作によって理解は深まる
# ポイントとなるのは、余った分はどういう操作をしても二枚づつ消すことができる。
# 余った分というのは、カードaに対してaの出現回数-1となる数字のことである。
# つまり余った分を単純に消せばよい。
# しかし余った分が奇数個のとき、余ってないカードから一枚犠牲にする必要がある。
# これらを実装すればおk

N = int(input())
A = list(map(int, input().split()))

from collections import Counter

A_cnt = Counter(A)
amari = sum([v - 1 for v in A_cnt.values()])
print(N - amari - 1 if amari & 1 else N - amari)


Measured memory_bytes: 17652
#include <stdio.h>
struct binary_tree{
    int n;
    int l;
    int r;
};
binary_tree bt[1000000];
int now=0;
void push(int n,int t){
    if(now==0){
        bt[0].n=n;
        now++;
        return;
    }
    if(bt[t].n<n){
        if(bt[t].r==0){
            bt[t].r=now;
            bt[bt[t].r].n=n;
            now++;
        }
        else push(n,bt[t].r);
    }
    if(bt[t].n>n){
        if(bt[t].l==0){
            bt[t].l=now;
            bt[bt[t].l].n=n;
            now++;
        }
        else push(n,bt[t].l);
    }
}
void dfs(int n){
    printf(" %d",bt[n].n);
    if(bt[n].l!=0){
        dfs(bt[n].l);
    }
    if(bt[n].r!=0){
        dfs(bt[n].r);
    }
}
void print_sorted(int n){
    if(bt[n].l!=0){
        print_sorted(bt[n].l);
    }
    printf(" %d",bt[n].n);
    if(bt[n].r!=0){
        print_sorted(bt[n].r);
    }
}
bool find(int n,int t){
    if(bt[t].n==n)return true;
    if(bt[t].n<n){
        if(bt[t].r!=0)return find(n,bt[t].r);
        return false;
    }
    if(bt[t].l!=0)return find(n,bt[t].l);
    return false;
}
int main(){
    int n,temp;
    char a[1000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        bt[i].n=bt[i].l=bt[i].r=0;
        scanf("%s",a);
        if(a[0]=='i'){
            scanf("%d",&temp);
            push(temp,0);
        }
        if(a[0]=='p'){
            print_sorted(0);
            printf("\n");
            dfs(0);
            printf("\n");
        }
        if(a[0]=='f'){
            scanf("%d",&temp);
            if(find(temp,0))printf("yes\n");
            else printf("no\n");
        }
    }
}

Measured memory_bytes: 8432
#include <iostream>
using namespace std;
int main() {
  int a,b,c; cin >> a >> b >> c;
  int d=(10*a+b)+c;
  int e=(10*b+a)+c;
  int f=(10*a+c)+b;
  int g=(10*c+a)+b;
  int h=(10*b+c)+a;
  int i=(10*c+b)+a;
  int j=max(d,e);
  int k=max(f,g);
  int m=max(h,i);
  int n=max(j,k);
  int o=max(m,n);
  cout << o << endl;
}


Measured memory_bytes: 384
object Main extends App {
  import scala.io.StdIn._

  val Array(a, b, x) = readLine.trim.split(' ').map(_.toInt)
  println(
    search(a, b, x)
  )
  def search(a: Int, b: Int, x: Int)(implicit memo: Array[Int] = Array.tabulate(x + 1){_ ⇒ -1}): Int = {
    if (x <= 0) 0
    else if (memo(x) > 0) memo(x)
    else math.min(search(a, b, x - 1000) + a, search(a, b, x - 500) + b).also(p ⇒ memo(x) = p)
  }
  implicit class ScopeFunc[T](value: T){
    def let[A](func: T ⇒ A): A = func(value)
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
  }
}


Measured memory_bytes: 44544
#include<stdio.h>

int main(void)
{
  int i,j;
  int H,W;

  while(1){
    scanf("%d %d",&H,&W);
    if(H == 0 && W == 0)break;
    else
      for(i=1;i<=H;i++){        
	for(j=1;j<=W;j++){
	  if(i == 1||j == 1||i == H||j == W){
	      printf("#");
	    }
	    else {
		printf(".");
	    }
	}
	printf("\n");
      }
    printf("\n");
  }
  return 0;
} 

Measured memory_bytes: 572
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define FI first
#define SE second
#define MA(i,j) make_pair(i,j)
#define PA pair<int,int>
#define PB push_back
#define PQ priority_queue<int>
#define PGQ priority_queue<int,vector<int>,greater<int> >
#define VE vector<int>
#define VP vector<PA>
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define MOD 1000000007
#define INF 1000000007
using namespace std;
//
int main(){
  string S;
  cin>>S;
  int P=0;
  FOR(i,0,(int)S.size()){
    if(S[i]=='p'){
      P++;
    }
  }
  cout<<(int)S.size()/2-P<<endl;
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define int long long
#define mod 1000000007
using namespace std;
signed main() {
	int n; cin >> n;
	if (n % 2)cout << (double)(n + 1) / n / 2 << endl;
	else cout << 0.5 << endl;
}

Measured memory_bytes: 256
import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
AB = [LI() for _ in range(M)]
graph = {i:collections.deque() for i in range(1,N+1)} #1_indexed
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,N+1):
    if not graph[i]:
        print('No')
        exit()
else:
    print('Yes')
seen = [0]*(N+1) #1_indexed
min_dist = [-1]*(N+1) #1_indexed
queue = collections.deque() #頂点NOを入れておく
def bfs():
    c_graph = copy.deepcopy(graph)
    seen[1] = 1
    queue.append(1)
    min_dist[1] = 0
    while queue:
        q_NO = queue.popleft()
        q_dist = min_dist[q_NO]
        if not c_graph[q_NO]:
            continue
        g = c_graph[q_NO]
        for _ in range(len(g)):
            g_NO = g.popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            queue.append(g_NO)
            min_dist[g_NO] = q_dist+1
bfs()
for j in range(2,N+1):
    ans,dist = 0,float('INF')
    for x in graph[j]:
        if dist>=min_dist[x]:
            ans = x
            dist = min_dist[x]
    print(ans)


Measured memory_bytes: 267576
import math
result = []
while True:
    n = input()
    if n == 0:
        break;
    score = map(float,raw_input().split(" "))
    
    ave = sum(score)/len(score)

    alpha = math.sqrt(sum([(s-ave)**2 for s in score])/len(score))
    result.append(alpha)

for r in result:
    print r

Measured memory_bytes: 6588
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

score = 0
remain = 0
for i in range(n):
    score += min(a[i], b[i] + remain)
    if a[i] > b[i] + remain:
        remain = 0
    else:
        if remain > a[i]:
            remain = b[i]
        else:
            remain = max(b[i]-a[i]+remain, 0)

score += min(remain, a[-1])
print(score)

Measured memory_bytes: 19116
import sys
input = sys.stdin.readline
import fractions

a,b,k=map(int,input().split())
d=fractions.gcd(a,b)
l=[]
for i in range(1,d+1):
        if a%i==0 and b%i==0:
                l.append(i)

l=l[::-1]
print(l[k-1])





Measured memory_bytes: 5048
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<climits>
#include<queue>

using namespace::std;


int main(){
    int N,M;
    cin >> N >> M;
    priority_queue<double> a;
    for(int i=0; i<N; i++){
        double t;
        cin >> t;
        a.push(t);
    }
    for(int i=0; i<M; i++){
        double t = a.top();
        a.pop();
        a.push(t/2.0);
    }
    long long ans = 0;
    for(int i=0; i<N; i++){
        ans += floor(a.top());
        a.pop();
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1400
num1, num2 = gets.split(" ").map(&:to_i)
check = []
for i in 1..1009
  a = (i * 0.08).floor
  b = (i * 0.10).floor
  if num1 == a && num2 == b
    puts i
    check << -1
    break
  end
end

if check == []
  puts -1
end

Measured memory_bytes: 3836
#ifdef __APPLE__
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <iomanip>
#include <cmath>
#include <ctgmath>
#include <math.h>
#include <cassert>
#include <chrono>
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define io ios_base::sync_with_stdio(false), cin.tie(NULL)
#define GFOR(i,a,n) for (i=a;i<n;i++)
#define FOR(i,a,n) for (int i=a;i<n;i++)
#define RFOR(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define tc(t) for (int tc=1; tc<=t; tc++)
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long int> vll;
typedef vector<pair<int, int> > vpi;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll modInverse (ll a) {ll p = mod - 2; return powmod(a, p);}
// head

void solve() {
    ll k;
    cin >> k;
    vector<bool> v(k);
    int c = 1;
    ll curr = 7%k;
    while (!v[curr]) {
        if (curr == 0) {
            cout << c << "\n";
            goto good;
        }
        v[curr] = true;
        c++;
        curr = curr*10 + 7;
        curr %= k;
    }

    cout << -1 << "\n";
    return;
    good:;
}

int main() {
    #ifdef LOCAL
    auto t1 = std::chrono::high_resolution_clock::now();
    #endif

    io;
    solve();

    #ifdef LOCAL
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();

    std::cout << "Time Taken: " << duration << "\n";
    #endif

}
// check for edge cases in limits
// printing double may print 1.223232e9 like values, beware of that
// carefully observe simulation of test cases


Measured memory_bytes: 3732
n = int(input())

a = list(map(int, input().split()))
ans = [0] * n
b = set()


for i in range(n-1, -1, -1):
    tmp = sum(ans[i::i+1])
    if tmp % 2 == a[i]:
        continue
    else:
        b.add(i+1)
        ans[i] = 1

cnt = len(b)


if cnt == 0:
    print(0)
else:
    print(cnt)
    print(*b)

Measured memory_bytes: 17200
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<(S)<<endl
using namespace std;

string abcgene(string anss){
	string c;
	string s=anss;
	bool flag=true;
	while(1){
		if(s=="ABC") return "Yes";
		if(!flag||s.size()<5) return "No";
		if(s.substr(0,3)=="ABC") c="A";
		else if(s.substr(s.size()-3,3)=="ABC") c="C";
		else c="B";
		int cnt=0;
                flag=false;
		REP(i,0,(int) s.size()-2){
			if(s.substr(i,3)=="ABC"){
				s.replace(i,3,c);
				cnt++;
				flag=true;
			}
		}
		if(cnt != count(s.begin(),s.end(),c[0])) return "No";
	}
}

int main(){
	string ans;
	cin>>ans;
	p(abcgene(ans));
	return 0;
}

Measured memory_bytes: 3240
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int h = S / 3600;
		int m = (S % 3600) / 60;
		int s = S % 3600 % 60;
		System.out.println(h + ":" + m + ":" + s);
	}
}

Measured memory_bytes: 26160
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);
parse_tuple!(A, B, C, D);
parse_tuple!(A, B, C, D, E);

// ===

const MOD: u64 = 1000000007;

struct Combination {
    fact: Vec<u64>,
    invfact: Vec<u64>
}

impl Combination {
    fn inv(a: u64) -> u64 {
        Combination::pow(a, MOD-2)
    }

    fn pow(a: u64, p: u64) -> u64 {
        let mut p = p;
        let mut aa = a;
        let mut ret = 1;
        while p >= 1 {
            if p & 1 == 1 {
                ret *= aa;
                ret %= MOD;
            }
            p >>= 1;
            aa = aa * aa % MOD;
        }
        ret
    }

    fn new(upto: usize) -> Self {
        let mut fact = vec![0; upto];
        let mut invfact = vec![0; upto];

        fact[0] = 1;
        for i in 1..upto {
            fact[i] = fact[i-1] * (i as u64) % MOD;
        }

        invfact[upto-1] = Combination::inv(fact[upto-1]);
        invfact[0] = 1;
        for i in (1..upto-1).rev() {
            invfact[i] = invfact[i+1] * ((i+1) as u64) % MOD;
        }

        Combination { fact: fact, invfact: invfact }
    }

    fn comb(&self, n: usize, r: usize) -> u64 {
        if r < 0 || r > n {
            return 0;
        }
        self.fact[n] * self.invfact[r] % MOD * self.invfact[n-r] % MOD
    }
}

fn main() {
    let (h, w, a, b): (usize, usize, usize, usize) = read();
    let comb = Combination::new(h+w+10);

    let mut a = h-a;
    let mut b = b+1;
    let mut ans = 0;

    while a >= 1 && b <= w {
        ans += ways(&comb, 1, 1, a, b) * ways(&comb, a, b, h, w) % MOD;
        a -= 1;
        b += 1;
    }
    println!("{}", ans % MOD);
}


fn ways(c: &Combination, fy: usize, fx: usize, ty: usize, tx: usize) -> u64 {
    if fx > tx || fy > ty {
        return 0
    }
    let dx = tx-fx;
    let dy = ty-fy;
    c.comb(dx+dy, dx)
}


Measured memory_bytes: 8444
#include<stdio.h>
int main(){
	int n,m,i,a[100],temp,j;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(j=0;j<m;j++){
		for(i=0;i<n-1;i++){
			if((a[i]%(j+1))>(a[i+1]%(j+1))){
				temp=a[i];
				a[i]=a[i+1];
				a[i+1]=temp;
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

Measured memory_bytes: 2716
#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
    int N;
    cin >> N;
    set<string> st;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        st.insert(str);
    }
    if (st.size() == 3) {
        cout << "Three" << endl;
    }else{
        cout << "Four" << endl;
    }
}

Measured memory_bytes: 256
using System;
using System.Linq;

class A
{
    private static char[] c;
    static void Main()
    {
        var s = Console.ReadLine();
        c = s.ToCharArray();
        if (c[c.Length - 1] != 's')
        {
            s = new String(c) + "s";
        }
        else
        {
            s = new String(c) + "es";
        }
        Console.WriteLine(s);
    }
}

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


public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        InputReader.OutputWriter out = new InputReader.OutputWriter(outputStream);

        int n = in.nextInt();
        int [] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        
        int mid = a[n/2] - a[n/2 - 1];
        out.println(mid);
        out.flush();
    }
    static int gcd (int a,int b) {
        return b == 0 ? a : gcd(b,a%b);
    }


    private static int [] mergeTwoArrays(int [] a, int [] b) {
        int [] res = new int[a.length + b.length];
        int i = 0;
        int j = 0;
        int index = 0;
        while (i<a.length && j<b.length) {
            if(a[i]<b[j]) {
                res[index++] = a[i++];
            }
            else {
                res[index++] = b[j++];
            }
        }
        System.out.println(i + " " + j);
        if(j == b.length - 1) {
            while (i<a.length) {
                res[index++] = a[i++];
            }
        }
        else {
            while (j<b.length) {
                res[index++] = b[j++];
            }
        }
        return res;
    }
}
class Point {
    private int left;
    private int right;

    public int getLeft() {
        return left;
    }

    public int getRight() {
        return right;
    }
    public Point(int left,int right) {
        this.left = left;
        this.right = right;
    }
}

class InputReader extends BufferedReader {
    StringTokenizer tokenizer;

    public InputReader(InputStream inputStream) {
        super(new InputStreamReader(inputStream), 32768);
    }

    public InputReader(String filename) {
        super(new InputStreamReader(Thread.currentThread().getContextClassLoader().getResourceAsStream(filename)));
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(readLine());
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
        return tokenizer.nextToken();
    }

    public Integer nextInt() {
        return Integer.valueOf(next());
    }
    public Long nextLong() {return  Long.valueOf(next());}

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream outputStream) {
            super(outputStream);
        }

        public OutputWriter(Writer writer) {
            super(writer);
        }

        public OutputWriter(String filename) throws FileNotFoundException {
            super(filename);
        }

        public void close() {
            super.close();
        }
    }
}

Measured memory_bytes: 36012
N = int(input())
An = list(map(int,input().split()))
Bn = list(map(int,input().split()))
ans=0
for b in range(len(Bn)):
    left = min(An[b],Bn[b])
    ans+=left
    An[b]-=left
    Bn[b]-=left
    right = min(An[b+1],Bn[b])
    ans+=right
    An[b+1]-=right
    Bn[b]-=right
print(ans)


Measured memory_bytes: 18476
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() {FIN
  	int a, b;
	cin >> a;
	cin >> b;
	cout << 6 - (a + b) << "\n";
	return 0;           
}

Measured memory_bytes: 256
n,k = map(int,input().split())

d_list = []
a_list = []
for k_tmp in range(k):
    d_tmp=int(input())
    d_list.append(d_tmp)
    a_list_tmp = list(map(int,input().split()))
    a_list.append(a_list_tmp)

ans_set = set()
for i in range(len(a_list)):
    for j in range(len(a_list[i])):
        ans_set.add(a_list[i][j])

print(n - len(ans_set))

Measured memory_bytes: 9228
using System;
using System.IO;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Linq;

namespace atcoder_past_problem
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new Input(Console.In));
        }

        public void Solve(Input input)
        {
            var n = input.ReadInt;
            var k = input.ReadInt;

            var tokuten = new Dictionary<char, int>() { {'s', input.ReadInt}, {'p', input.ReadInt}, {'r', input.ReadInt} };

            var t = input.Read.ToArray();

            var total = 0;
            for (var i = 0; i < n; ++i)
            {
                if (i - k >= 0 && t[i] == t[i - k])
                {
                    t[i] = 'x';
                    continue;
                }
                total += tokuten[t[i]];
            }
            Console.WriteLine(total);
        }
    }

    public class Input
    {
        private TextReader Stream { get; }
        private char Separator { get; }
        private Queue<string> InputStream { get; }

        public Input(TextReader stream, char separator = ' ')
        {
            Stream = stream;
            Separator = separator;
            InputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if (InputStream.Count != 0) return InputStream.Dequeue();
                string[] tmp = Stream.ReadLine().Split(Separator);
                for (int i = 0; i < tmp.Length; ++i)
                    InputStream.Enqueue(tmp[i]);
                return InputStream.Dequeue();
            }
        }

        public string ReadLine => Stream.ReadLine();
        public int ReadInt => int.Parse(Read);
        public long ReadLong => long.Parse(Read);
        public double ReadDouble => double.Parse(Read);
        public int[] ReadIntArray => Stream.ReadLine().Split(Separator).Select(i => int.Parse(i)).ToArray();
        public long[] ReadLongArray => Stream.ReadLine().Split(Separator).Select(l => long.Parse(l)).ToArray();
    }
}


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

const int MOD=1000000007;
//~ const int MOD=998244353;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

bool is_prime(ll n){
	if(n==1)return false;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0)return false;
	}
	return true;
}
vector<ll>divisor(ll n){
	vector<ll>res;
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			res.push_back(i);
			if(i!=n/i)res.push_back(n/i);
		}
	}
	return res;
}
map<ll,int>prime_factor(ll n){
	map<ll,int>res;
	for(ll i=2;i*i<=n;i++){
		while(n%i==0){
			res[i]++;
			n/=i;
		}
	}
	if(n!=1)res[n]++;
	return res;
}
ll factor(ll n,ll a){
	ll cnt=0;
	while(n%a==0){
		cnt++;
		n/=a;
	}
	return cnt;
}

vector<ll>prime_enum(int n){
	vector<bool>is_prime(n+1,true);
	is_prime[0]=is_prime[1]=false;
	vector<ll>res;
	for(int i=2;i<=n;i++){
		if(!is_prime[i])continue;
		res.push_back(i);
		for(int j=2*i;j<=n;j+=i){
			is_prime[j]=false;
		}
	}
	return res;
}
string s[300000];
int cnt[20][20];
int D1[300000],D2[300000];

int main(){
	int n;cin>>n;
	rep(i,n){
		cin>>s[i];
		string A,B;
		bool f=false;
		for(char c:s[i]){
			if(c=='.'){f=true;continue;}
			if(!f)A+=c;
			else B+=c;
		}
		for(int i=0;i<9;i++){
			if(i<B.size())A+=B[i];
			else A+='0';
		}
		bool ok=true;
		for(int i=9;i<B.size();i++){
			if(B[i]!='0')ok=false;
		}
		if(ok){
			ll d=stoll(A);
			D1[i]=min(18LL,factor(d,2));D2[i]=min(18LL,factor(d,5));
			cnt[D1[i]][D2[i]]++;
		}
	}
	ll sum=0;
	rep(i,n){
		int ans=0;
		if(D1[i]*2>=18&&D2[i]*2>=18)ans--;
		for(int j=18-D1[i];j<=18;j++){
			for(int k=18-D2[i];k<=18;k++){
				ans+=cnt[j][k];
			}
		}
		sum+=ans;
	}
	cout<<sum/2<<endl;
}

Measured memory_bytes: 14488
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define RFOR(i, begin, end) for(int i=(end)-1, i##_begin_=(begin);i>=i##_begin_;i--)
#define rep(i, N) FOR(i, 0, N)
#define rrep(i, N) RFOR(i, 0, N)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
using namespace std;
using ll = long long int;
using V = vector<ll>;
using P = pair<ll, ll>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
constexpr int mod = 1e9+7;
ll gcd(ll a, ll b) { return b? gcd(b, a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}

ll n;

int main() {
    cin >> n;
    V h(n);
    rep(i, n) cin >> h[i];
    ll ret = 0;
    ll cur = 0;
    rep(i, n-1) {
        if(h[i] >= h[i+1]) {
            cur ++;
        }
        else{
            ret = max(ret, cur);
            cur = 0;
        }
    }
    ret = max(ret, cur);
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

func main() {
	resolve(os.Stdin)
}

func resolve(r io.Reader) {
	const (
		initialBufSize = 100000
		maxBufSize     = 1000000
	)
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	s := scanString(sc)
	fmt.Println(strings.Repeat("x", len(s)))
}

// snip-scan-funcs
func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}
func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 640
#include<stdio.h>

int main(){
	int dx,dy,sx,sy,tx,ty,i;
	scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
	dx=tx-sx;
	dy=ty-sy;
	for(i=0;i<dy;i++){
		printf("U");
	}
	for(i=0;i<dx;i++){
		printf("R");
	}
	for(i=0;i<dy;i++){
		printf("D");
	}
	for(i=0;i<dx;i++){
		printf("L");
	}
	printf("L");
	for(i=0;i<dy+1;i++){
		printf("U");
	}
	for(i=0;i<dx+1;i++){
		printf("R");
	}
	printf("DR");
	for(i=0;i<dy+1;i++){
		printf("D");
	}
	for(i=0;i<dx+1;i++){
		printf("L");
	}
	printf("U");
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
ll n;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	ll ans=0;
	for(ll i=1;i*i<=(n-1);i++){
		if(i*i==(n-1))
		ans++;
		else
		if((n-1)%i==0)
		ans+=2;
	}
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
		ll now=n;
		while(now%i==0)
	    now/=i;
	    now%=i;
	    if(now==1)
	    ans++;
		}
   	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;
    out(n/3);
    re0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define vec(type) vector<type>

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

    long long ans;
    if (b >= c) ans = b+c;
    else if (a+b < c) ans = a+b + b + 1;
    else ans = c + b;

    cout << ans << endl;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<lint> a(n);
    lint ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > 2) {
            ans += (a[i] - 1) / 2;
            a[i] -= ((a[i] - 1) / 2) * 2;
        }
    }
    a.push_back(0);
    for (int i = 0; i < n; i++) {
        if (a[i] == 2) {
            ans++;
        } else if (a[i] == 1) {
            if (a[i + 1] >= 1) {
                ans++;
                a[i]--;
                a[i + 1]--;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<cmath>
#include <numeric>
using namespace std;
typedef unsigned long long ll;
ll mod = (10e+8)+ 7;


int main(){
	int N;
	cin>>N;
	vector<int>V(N);
	for(int i = 0; i < N; i++){
		cin>>V[i];
		
	}
	sort(V.begin(),V.end());
	double ans=0;
	ans = (V[0] + V[1])/2.0;
	for(int i = 2; i < N; i++){
		ans += V[i];
		ans /= 2.0;
		
	}
	cout<<ans<<endl;
}

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

int main()
{
  int A, B, C, D;
  int left, right;
  
  cin >> A >> B >> C >> D;
  
  left = A + B;
  right = C + D;
  
  if(left > right)
    cout << "Left" << endl;
  else if(right > left)
    cout << "Right" << endl;
  else
    cout << "Balanced" << endl;
}

Measured memory_bytes: 256
// Problem : B - Frog 2
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;

#define ff first
#define fs second
#define lb lower_bound
#define ub upper_bound

#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector< vi >
#define vpii vector< pii >
#define vb vector<bool>
#define si set<int>
#define mii map<int, int>
#define mci map<char, int>
#define md 1000000007
#define pb push_back
#define eb emplace_back
#define fio ios_base::sync_with_stdio (false); cin.tie (NULL);  cout.tie (NULL);
#define qw1(x) cerr<<#x<<": "<<x<<" "<<endl
#define qw2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define qw3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define qw4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl


#define f(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define rl(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define all(x) x.begin(),x.end()
#define endl '\n'
void printv(vector<int>  v){ for(int i=0;i<v.size();i++) cout<<v[i]<<' '; cout<<endl;   }
int bem(int m , int n, int mod) { int res=1; while(n){
	     			        if(n%2!=0) { res*=m; res%=mod; }
	    			        m*=m;   m%=mod;   n/=2;
			                          }
				return res;	}
int be(int a, int b) { int res=1; 	while(b){
				if(b%2!=0) res*=a;
				a*=a; b/=2;
				}
			return res;	}
void sieve(int n, vb &prime){
    prime[0]=false;     prime[1]=false;
    for(int i=2;i*i<=n;i++){
         if(prime[i]==true){
              for(int j=i*i;j<=n;j+=i)    prime[j]=false;
             	  }
    	 }
	}
vi v;
vi dp;
int k;
/*int fun( int n)
{
	if(dp[n]!=-1) return dp[n];
	if(n==0) return dp[n]=0;
	int z=max((int)0, n-k);
	dp[n]=fun(z)+abs(v[z]-v[n]);
	f(i, 1, min(k-1, n-2)) dp[n]=min(dp[n], fun(n-i)+abs(v[n]-v[n-i]));
	return dp[n];
}
void solve()
{
int n; cin>>n>>k;
v.resize(n); f(i, 0, n-1) cin>>v[i];
dp.resize(n, -1);
cout<<fun(n-1)<<endl;
// printv(dp);
}*/
void solve()
  {
int n, k; cin>>n>>k;
v.resize(n); f(i, 0, n-1) cin>>v[i];
dp.resize(n, INT_MAX);
dp[0]=0;
f(i ,0, n-1)
  f(j, i+1, i+k)
  {
  	if(j<n)
  	dp[j]=min(dp[j], dp[i]+abs(v[i]-v[j]));
  }
 // printv(dp);
cout<<dp[n-1]<<endl;
}


int32_t main ()
{
//fio
int t=1; 
//cin>>t; 
while(t--){
	solve();
}
 
}








Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <numeric>
#include <utility>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef pair<int,int> pii;
int main(){
    int n;
    cin >> n;
    vector<int>t(n);
    rep(i,n)cin >> t[i];
    int ans = accumulate(t.begin(),t.end(),0);
    int m;
    cin >> m;
    rep(i,m){
        int p,x;
        cin >> p >> x;
        p--;
        if(1){
            cout << ans-t[p]+x << endl;
        }
    }
    
}

Measured memory_bytes: 256
if __name__ == '__main__':

	n = int(input())

	A = []
	for i in range(n):
		cmd = input().split()
		A.append([i+1,cmd[0],int(cmd[1])])

	B = sorted(A,key=lambda x:(x[1],-x[2]))
	for j in B:
		print(j[0])


Measured memory_bytes: 9144
open System

// prelude
let readStr () = stdin.ReadLine()

let read f () = readStr() |> f
let reads f () = readStr().Split() |> Array.map f

let pair = function
| [|a; b|] -> (a, b)
| _ -> failwith "owatta"

let triple = function
| [|a; b; c|] -> (a, b, c)
| _ -> failwith "owatta"

let readPair f g () =
  let (a,b) = readStr().Split() |> pair
  (f a, g b)

let readTriple f g h () =
  let (a,b,c) = readStr().Split() |> triple
  (f a, g b, h c)

let inc n = n + 1
let dec n = n - 1

let inline flip f a b = f b a
let rec fix f = fun x -> (f (fix f)) x

module Option =
  let getOr defaultValue = function
  | Some x -> x
  | None -> defaultValue

module Array =
  let modify (arr: _ []) i f =
    arr.[i] <- f arr.[i]

module Array2D =
  let modify (arr: _ [,]) i j f =
    arr.[i, j] <- f arr.[i, j]

// start
let (N,M) = readPair int int ()
let H = reads int ()

let g = Array.init N (fun _ -> ResizeArray<int>())
for _ in 1..M do
  let (A,B) = reads int () |> Array.map dec |> pair
  g.[A].Add B
  g.[B].Add A

seq {
  for i in 0..(N-1) do
    let h=H.[i]
    let good =
      g.[i].ToArray()
      |> Array.forall (fun j -> h>H.[j])
    yield if good then 1 else 0
}
|> Seq.sum
|> printfn "%d"


Measured memory_bytes: 63428