akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys

# https://en.wikipedia.org/wiki/Cycle_detection
def floyd_cycle_finding(f, x0):
    '''
    循環していない部分の長さをlam
    循環部分の長さをmuとして
    (lam, mu)
    を返す
    >>> floyd_cycle_finding(lambda x: x**2 % 3, 2)
    (1, 1)
    >>> floyd_cycle_finding(lambda x: x**2 % 1001, 2)
    (2, 4)
    >>> floyd_cycle_finding(lambda x: x**2 % 16, 2)
    (2, 1)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 3)
    (0, 4)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 0)
    (0, 1)
    '''
    # a_i = a_j
    # の関係が成り立つ時
    # a_{lam+n+k*mu} = a_{lam+n+k'*mu}
    # より|i-j|は循環の長さの整数倍になる
    # そこで
    # a_m = a_2m
    # なるmを見つける
    # 前述の性質からmは循環の長さの整数倍となっているため
    # 2m - m = m = k*mu = lam + n + k'*mu
    # したがって、lam + nはmuの倍数となるので
    # 地点mからlamステップ進むと循環の開始点に到達する
    # lamが求まれば後は流れでmuも求まる
    
    tortoise = f(x0)
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
    lam = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        lam += 1
    mu = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        mu += 1
    return lam, mu

def solve(N: int, X: int, M: int):
    f = lambda x: x**2 % M

    def g(x):
        while True:
            yield x
            x = f(x)
            
    lam, mu = floyd_cycle_finding(f, X)
    ans = 0
    gg = g(X)
    k = max((N - lam) // mu, 0)
    for i in range(min(N, lam)):
        ans += next(gg)
    for i in range(mu):
        ans += k * next(gg)
    for i in range(max((N-lam)%mu, 0)):
        ans += next(gg)
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    print(solve(N, X, M))


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()


Measured memory_bytes: 17500
N, M=map(int, input().split())
A=list(map(int, input().split()))
bc=[]
for i in range(M):
  b, c=map(int, input().split())
  bc.append((c,b))
for i in range(N):
  bc.append((A[i], 1))
  
bc=sorted(bc, key=lambda x : x[0], reverse=True)

ans=0
res=N
for x in bc:
  c=x[0]
  b=min(x[1], res)
  ans+=c*b
  res-=b
  if res==0:
    break
    
print(ans)

Measured memory_bytes: 33732
package main

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

func main() {
	scanInit()

	n := nextInt()

	now := 0
	for i := 0; i < n; i++ {
		a := nextInt()
		b := nextInt()
		if a == b {
			now++
			if now >= 3 {
				fmt.Println("Yes")
				return
			}
		} else {
			now = 0
		}
	}
	fmt.Println("No")
	return

}

// ---- readfunc
var sc = bufio.NewScanner(os.Stdin)

func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1784
n=gets.to_i
s=Array.new(n)
s=gets
ans=0
for i in 0..n-1
  if s[i]=='A'
    i+=1
    if s[i]=='B'
      i+=1
      if s[i]=='C'
        ans+=1
      end
    end
  end
end
puts ans


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

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

int main() {

    int N;
    cin >> N;
    vector<int> C(4, 0);
    rep(i,N) {
        string S;
        cin >> S;
        if (S == "AC") C[0]++;
        if (S == "WA") C[1]++;
        if (S == "TLE") C[2]++;
        if (S == "RE") C[3]++;
    }

    printf("AC x %d\n", C[0]);
    printf("WA x %d\n", C[1]);
    printf("TLE x %d\n", C[2]);
    printf("RE x %d\n", C[3]);
    
    return 0;
}

Measured memory_bytes: 3728
import itertools
n,m,x=map(int,input().split())
l=list()
for i in range(n):
    l.append(list(map(int,input().split())))
pp=list()
for i in range(1,n+1):
    for j in itertools.combinations(l,i):
        r=[0 for i in range(m)]
        for k in j:
            a=0
            p=0
            for i in range(1,m+1):
                r[i-1]+=k[i]
                a+=r[i-1]>=x
            if a==m:
                for c in j:
                    p+=c[0]
                pp.append(p)
if len(pp)==0:
    print(-1)
else:
    print(min(pp))


Measured memory_bytes: 9584
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String readStr;
    int c = 0;
    while ((readStr = reader.readLine()) != null) {
      int[] list = new int[3];
      list[0] = Integer.parseInt(readStr.split(" ")[0]);
      list[1] = Integer.parseInt(readStr.split(" ")[1]);
      String sssss = String.format("%.6f", (1.0 * list[0] / list[1]));
      System.out.println((int)(list[0] / list[1]) + " " + (list[0] % list[1]) + " " + sssss);
      break;
    }
  }

}

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

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define lrep(i,n) for(long long  i = 0; i < (long long)(n); i++)
#define lrep2(i,a,n) for(long long i = (long long)(a); i <= (long long)(n); i++)

#define irrep(i,n) for(int i = (int)(n); i > -1; i--)
#define irrep2(i,a,n) for(int i = (int)(n); i >= (int)(a); i--)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<v_char > v2_char;
typedef std::vector<double> v_double;
typedef std::vector<v_double > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<v_int > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<v_ll > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<v_string > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<v_bool > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

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

using namespace std; 

int main(void)
{
    int a,b,h,m;
    cin >> a >> b >> h >> m;

    double a_rad = (h*60+m) * (360.0/720.0) * (PI/180.0);
    double b_rad = (m) * (360/60) * (PI/180.0);
    
    double x = 1;
    x *= ((a * cos(a_rad)) - (b * cos(b_rad)));
    x *= ((a * cos(a_rad)) - (b * cos(b_rad)));
    double y = 1;
    y *= ((a * sin(a_rad)) - (b * sin(b_rad)));
    y *= ((a * sin(a_rad)) - (b * sin(b_rad)));
    double ans = sqrt(x+y);
    printf("%.10f\n", ans);
    return 0;
}   
/** atcoder **/


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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX

const double EPS = 1e-14;
const double PI  = acos(-1.0);


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

  printf("%.8lf\n", a / b);
}


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

int main() {
  int n;
  scanf("%d", &n);
  int A[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &A[i]);
  }
  int count = 0;
  for (int i = 0; i < n-1; i++) {
    if (A[i] == A[i+1]) {
      A[i+1] += 100000;
      count++;
    }
  }
  printf("%d\n", count);

  return 0;
}


Measured memory_bytes: 888
h_1,a_1,h_2,a_2 = map(int,input().split())

h_2//a_1
h_1//a_2

if h_2%a_1!=0 and h_1%a_2!=0:
    if h_2//a_1 <= h_1//a_2:
        print("Yes")
    else:
        print("No")
elif h_2%a_1!=0 and h_1%a_2==0:
    if h_2//a_1+1 < h_1//a_2:
        print("Yes")
    else:
        print("No")
elif h_2%a_1==0 and h_1%a_2!=0:
    if h_2//a_1 <= h_1//a_2+1:
        print("Yes")
    else:
        print("No")
else:
    if h_2//a_1 <= h_1//a_2:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 9112
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;  typedef long long ll;
int n,ans;
const int maxn=1e6+5;
char S[maxn],T[maxn];
deque<int> q;
int main(){
	scanf("%d%s%s",&n,S+1,T+1);
	q.push_back(n+1);
	for(int t=n,p=n+1,offset=0;t;--t){
		int sav=p;
		while(p&&(p>t||S[p]!=T[t])) --p;
		if(p<1) puts("-1"),exit(0);
		if(sav==p){
			while(q.size()&&q.back()-offset>=t) q.pop_back();
			q.push_back(t+offset);
		}else{
			++offset;
			if(t!=p) ans=max(ans,(int)q.size()),q.push_front(p+offset);
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 6272
#include<stdio.h>

int main (void)
{
  long int n,m,a[1000001],i,sum=0;
  
  scanf("%ld %ld", &n,&m);
  
  for(i=0;i<m;i++){
    scanf("%ld", &a[i]);
    sum+=a[i];
  }
  
  if(sum <= n)
    printf("%ld", n-sum);
  else
    printf("-1");
  
  return 0;
}

Measured memory_bytes: 1760
import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            r = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r

    def GetWeight(self, x):
      self.Find_Root(x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
        return self.GetWeight(y) - self.GetWeight(x)

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  for i in range(M):
    l, r, d = lrd[i]
    if not U.isSameGroup(l, r):
      U.Unite(l, r, d)
    else:
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

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

using namespace std;

long long int N, v[102], w[102], W;
long long m[100002][102];


long long int resi(long long int W, long long int N)
{
    for(int i = 0; i <= N; i++)
    {
        for(int j = 0; j <= W; j++)
        {
            if(i == 0 || j == 0)
                m[j][i] = 0;
            else
            {
                if(j < w[i-1])
                {
                    m[j][i] = m[j][i-1];
                    //cout << j << " " << i << endl;
                }
                else
                {
                    m[j][i] = max(m[j-w[i-1]][i-1] + v[i-1], m[j][i-1]);
                }
                
            }
        }
    }

    // for(int i = 0; i <= N; i++)
    // {
    //     for(int j = 0; j <= W; j++)
    //     {
    //         cout << m[j][i] << "(" << j << ") " ;
    //     } 
    //     cout << endl;
    // }

    //cout << "REZ: "<< m[][];

    return m[W][N];
}

int main()
{
    cin >> N >> W;

    for(int i = 0; i < N; i++)
    {
        cin >> w[i] >> v[i];
    }

    long long int x = resi(W, N);

    cout << x;

    return 0;
}

Measured memory_bytes: 79872
from collections import deque
H,W=map(int,input().split())
S=[]
count=0
for _ in range (H):
    A=list(input())
    for a in A:
        if a=='.':
            count+=1
    S.append(A)

mas=deque([(0,0,0)])
while mas:
    y,x,n=mas.popleft()
    if 0<=y<=H-1 and 0<=x<=W-1:
        if S[y][x]=='.':
            S[y][x]=n
            mas.append((y+1,x,n+1))
            mas.append((y,x+1,n+1))
            mas.append((y-1,x,n+1))
            mas.append((y,x-1,n+1))
short=S[H-1][W-1]
if short=='.':
    print(-1)
else:
    print(count-(short+1))

Measured memory_bytes: 9468
/*
	0158:Collatz's Problem
*/
#include	<iostream>

using namespace std;

int main(void) {
	while(1) {
		int n;
		cin >> n;
		
		if(n == 0) { break; }
		
		int c = 0;
		while(n != 1) {
			if(n % 2 == 1) {
				n *= 3;
				n++;
			} else {
				n /= 2;
			}
			c++;
		}
		cout << c << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int test;cin>>test;
	int ac=0,tle=0,wa=0,re=0;
	while(test--)
	{
		string s;cin>>s;
		if(s == "AC") ac++;
		else if(s == "TLE") tle++;
		else if(s == "WA") wa++;
		else if(s == "RE") re++;
	}
	cout<<"AC x "<<ac<<endl;
		cout<<"WA x "<<wa<<endl;
		cout<<"TLE x "<<tle<<endl;
		cout<<"RE x "<<re<<endl;
}


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

import sys
from collections import deque

n = int(sys.stdin.readline())
ai = list(map(int, sys.stdin.readline().split()))

min = float('inf')
max = 0

for a in ai:
	if a < min:
		min = a

	if a > max:
		max = a

print(str(int(max - min)))


Measured memory_bytes: 3316
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;

class Procon {
    static void Main (string[] agrs) {
        int A = Int ();
        int B = Int ();

        Dbg (Max (A + B, A - B, A * B));
    }

    static Scanner cin = new Scanner ();
    const int M = 1000000007;
    static StreamWriter sw = new StreamWriter (Console.OpenStandardOutput ()) { AutoFlush = false };
    static void Dbg (object a) => Console.WriteLine (a);
    static void Dbg<T> (IEnumerable<T> a) => Dbg (string.Join (" ", a));
    static void Dbg<T> (params object[] a) => Dbg (string.Join (" ", a));
    static void Dbgs<T> (IEnumerable<T> a) => Dbg (string.Join ("\n", a));
    static void Dbgs<T> (params object[] a) => Dbg (string.Join ("\n", a));
    static void Dbgs (object a) => Console.WriteLine (a);
    static int Int () => cin.nextInt ();
    static long Long () => cin.nextLong ();
    static int[] Ints () => cin.arrayInt ();
    static long[] Longs () => cin.arrayLong ();
    static double Double () => cin.nextDouble ();
    static double[] Doubles () => cin.arrayDouble ();
    static string String () => cin.nextString ();
    static string[] Strings () => cin.arrayString ();
    static T Max<T> (params T[] a) => a.Max ();
    static T Min<T> (params T[] a) => a.Min ();
}

class Scanner {
    string[] s;
    int i;
    int max_i;

    public Scanner () {
        s = new string[0];
        max_i = 0;
        i = 0;
    }

    public string nextString () {
        if (i >= s.Length) {
            s = Console.ReadLine ().Split (' ');
            max_i = s.Length;
            i = 0;
            if (max_i == 0) {
                return "";
            }
            return s[i++];
        } else {
            return s[i++];
        }
    }

    public int nextInt () {
        return int.Parse (nextString ());
    }

    public long nextLong () {
        return long.Parse (nextString ());
    }

    public double nextDouble () {
        return double.Parse (nextString ());
    }

    public string[] arrayString () {
        return Console.ReadLine ().Split (' ');
    }

    public int[] arrayInt () {
        string[] str = Console.ReadLine ().Split (' ');
        int[] array = new int[str.Length];
        for (int i = 0; i < str.Length; i++) {
            array[i] = int.Parse (str[i]);
        }
        return array;
    }

    public long[] arrayLong () {
        string[] str = Console.ReadLine ().Split (' ');
        long[] array = new long[str.Length];
        for (int i = 0; i < str.Length; i++) {
            array[i] = long.Parse (str[i]);
        }
        return array;
    }

    public double[] arrayDouble () {
        string[] str = Console.ReadLine ().Split (' ');
        double[] array = new double[str.Length];
        for (int i = 0; i < str.Length; i++) {
            array[i] = double.Parse (str[i]);
        }
        return array;
    }
}

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

using namespace std;

typedef short sho;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef string str; 
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll; 
typedef pair<ld,ld> pld;
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pld> vpd;

#define LOCAL
#define MP make_pair 
#define FF first
#define SS second
#define sz(x) (int)x.size()
#define begin(x) (x).begin() 
#define end(x) (x).end()
#define rbegin(x) (x).rbegin()
#define rend(x) (x).rend()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define PF push_front 
#define PB push_back
#define PP push
#define lb lower_bound 
#define ub upper_bound
#define lowbit(x) x&(-x)
#define testbit(x,i) x&(1<<i)

inline void checkmin(int &x,int y){x=min(x,y);}
inline void checkmax(int &x,int y){x=max(x,y);}

long long x;

int main() 
{
	#ifndef LOCAL
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /* start code */
    cin>>x;
    long long now=100;
    int cnt=0;
    while(now<x)
    {
    	now+=now/100;
    	cnt++;
	}
	cout<<cnt<<endl;
    /* end code */
	return 0;
}

Measured memory_bytes: 3652
//{{{
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printw) FUNC(printwe) FUNC(printb) FUNC(printbe) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<unordered_map<string, ll>> dp(n - 2);
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            for(int k = 0; k < 4; k++){
                string str = string() + "ACGT"[i] + "ACGT"[j] + "ACGT"[k];
                if(str == "AGC"){ continue; }
                if(str == "ACG"){ continue; }
                if(str == "GAC"){ continue; }
                dp[0][str] = 1;
            }
        }
    }
    for(int i = 1; i <= n - 3; i++){
        for(auto& mp : dp[i - 1]){
            for(int j = 0; j < 4; j++){
                string str = mp.first + "ACGT"[j];
                if(str.substr(1) == "AGC"){ continue; }
                if(str.substr(1) == "ACG"){ continue; }
                if(str.substr(1) == "GAC"){ continue; }
                if(str[0] == 'A' && str.substr(2) == "GC"){ continue; }
                if(str.substr(0, 2) == "AG" && str[3] == 'C'){ continue; }
                dp[i][str.substr(1)] += mp.second;
                dp[i][str.substr(1)] %= M;
            }
        }
    }
    printde(dp);
    ll ans = 0;
    for(auto& mp : dp[n - 3]){
        ans = ans + mp.second;
        ans %= M;
    }
    cout << ans << '\n';
}


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

#define jaldi ios_base::sync_with_stdio(false)
#define fr(i,j,n) for(i=j;i<n;i++)
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%ld",&x)
#define sll(x) scanf("%lld",&x)
#define sc(x) scanf("%c",&x)
#define ss(x) scanf("%s",x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%ld",x)
#define pll(x) printf("%lld",x)
#define pc(x) printf("%c",x)
#define ps(x) printf("%s",x)
#define vi vector<int> 
#define vl vector<long> 
#define vll vector<long long>
#define vc vector<char>  
#define vs vector<string>
#define vvi vector<vector<int>> 
#define vvll vector<vector<long long>> 
#define F first
#define S second
#define ll long long
#define pb push_back
#define ppii pair<int,int> 
#define ppll pair<long long,long long>
#define ppcc pair<char,char>
#define ppss pair<string,string> 
#define vpll vector<pair<long long,long long>>
#define PI 3.1415926535897932384626
#define precision(x) cout<<fixed<<setprecision(x) 
#define mod 1000000007

int x_d[8] = {-1,1,0,0,-1,-1,1,1};
int y_d[8] = {0,0,-1,1,-1,1,-1,1};

ll power(ll b,ll e)
{
    if(b==0)
        return 0;
    
    ll r=1;
    while(e>0)
    {
        if(e%2)
            r=(r*b)%mod;
        b=(b*b)%mod;
        e/=2;
    }
    return r;
}

int main()
{
    jaldi;
    precision(20);
    ll i,j;

    ll n,k;
    cin>>n>>k;
    vll v(n,0);
    for(i=0;i<k;i++)
    {
        ll d;
        cin>>d;
        for(j=0;j<d;j++)
        {
            ll a;
            cin>>a;
            a--;
            v[a]++;
        }
    }
    ll ans=0;
    for(i=0;i<n;i++)
    {
        if(v[i]==0)
            ans++;
    }
    cout<<ans;


    return 0;
}

Measured memory_bytes: 3664
import itertools
import math
import fractions
import functools

n, k = map(int, input().split())
a = []
for i in range(k):
    di = int(input())
    ai = list(map(int, input().split()))
    a.append(ai)

count = [0] * (n+1)
for i in range(k):
    for j in range(len(a[i])):
        count[a[i][j]] += 1

print(count.count(0)-1)

Measured memory_bytes: 72796
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a%b);
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 1;
    int m1 = a[n-1];
    int m2 = a[n-2];
    vector<int> m1p;
    vector<int> m2p;
    m1p.push_back(m1);
    m2p.push_back(m2);
    for(int i = 2; i * i <= m1; i++)
    {
        if(m1 % i == 0)
        {
            m1p.push_back(i);
            m1p.push_back(m1 / i);
        }
    }
    for(int i = 2; i * i <= m2; i++)
    {
        if(m2 % i == 0)
        {
            m2p.push_back(i);
            m2p.push_back(m2 / i);
        }
    }

    int i = m1;
    int cnt = 2;
    for(int i = 0; i < m1p.size(); i++)
    {
        int cand = m1p[i];
        int tmp = 0;
        for(int j = 0; j < n; j++)
        {
            if(a[j] % cand != 0) tmp++;
        }
        if(tmp <= 1)
        {
            ans = max(ans, cand);
        }
    }
    for(int i = 0; i < m2p.size(); i++)
    {
        int cand = m2p[i];
        int tmp = 0;
        for(int j = 0; j < n; j++)
        {
            if(a[j] % cand != 0) tmp++;
        }
        if(tmp <= 1)
        {
            ans = max(ans, cand);
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 640
#include <stdio.h>

int main(void){
    int i,k,t,sum=0,sum1,d=0;
    scanf("%d %d",&k,&t);
    int a[t];
    for(i=0;i<t;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    for(i=0;i<t;i++){
        sum1=sum-a[i];
        if(sum1<a[i]){
            d=a[i]-sum1-1;
        }
    }
    printf("%d\n",d);
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define ALL(a) a.begin(), a.end()
typedef long long ll;
const int INF = 100100100;
using namespace std;

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

    int a, b, c;
    cin >> a >> b >> c;

    if (a + b >= c)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v, n) sort(v, v+n)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define ddvi vector<vector<int>>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
	#define int ll
	cin.tie(0);
	ios::sync_with_stdio(false);
	// ここに処理を記述

	int N, X, Y;
	cin >> N >> X >> Y;

	// 注意!!! : 1-indexed
	vi X_dist(N+1, -1);	// Xからの距離
	vi Y_dist(N+1, -1); // Yからの距離

	FOR(i,1,N+1){
		X_dist[i] = abs(X - i);
		Y_dist[i] = abs(Y - i);
	}

	vi ans_dist(N, 0);
	vector<vector<bool>> checked(N+1,vector<bool>(N+1, false));
	FOR(i,1,N+1){
		FOR(j,1,N+1){
			if(checked[i][j] || i == j) continue;
			int i_near = min(X_dist[i], Y_dist[i]);
			int j_near = min(X_dist[j], Y_dist[j]);

			ans_dist[min(abs(i-j), i_near + j_near + 1)]++;

			/*
			int X_near = min(X_dist[i], X_dist[j]);
			int Y_near = min(Y_dist[i], Y_dist[j]);

			int x_n_point = (min(X_dist[i], X_dist[j]) == X_dist[i])?  i : j;
			int y_n_point = (min(Y_dist[i], Y_dist[j]) == Y_dist[i])?  i : j;
			if(x_n_point == y_n_point){
				if(i < min(X,Y)){
					X_near = abs(min(X,Y) - i);
				}
				else if(j < min(X,Y)){
					X_near = abs(min(X,Y) - i);
				}
				if(i > max(X,Y)){
					Y_near = abs(i - max(X,Y));
				}
				else if(j > max(X,Y)){
					Y_near = abs(j - max(X,Y));
				}
			}

			ans_dist[min(abs(i-j), X_near + 1 + Y_near)]++;
			*/

			/*
			cout << i << " to " << j << " : ";
			cout << min(abs(i-j), X_near + 1 + Y_near) << "\n";
			if(i == 1 && j == 8){
				cout << "X_near = " << X_near << "\n";
				cout << "Y_near = " << Y_near << "\n";
			}
			*/


			checked[i][j] = true;
			checked[j][i] = true;
		}
	}

	FOR(i,1,N){
		cout << ans_dist[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 896
fun main(args: Array<String>) {
    val (N, M) = listOfInt()
    val ans = N * (N - 1) / 2 + M * (M - 1) / 2
    println(ans)
}

fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun nextInt(offset: Int = 0) = nextInt() + offset
fun nextLong() = java.lang.Long.parseLong(next())
fun nextLong(offset: Long = 0L) = nextLong() + offset
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }
fun listOfInt(offset: Int = 0) = listOfString().map { Integer.parseInt(it) + offset }
fun listOfLong() = listOfString().map { java.lang.Long.parseLong(it) }
fun listOfLong(offset: Long = 0L) = listOfString().map { java.lang.Long.parseLong(it) + offset }
fun listOfDouble() = listOfString().map { it.toDouble() }


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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
	int w, h;
	int c[50][50] = {};

	void dfs(int i, int j) {
		c[i][j] = 0;

		for (int di = -1; di <= 1;di++) {
			for (int dj = -1; dj <= 1;dj++) {
				int ni = i + di;
				int nj = j + dj;

				if (0 <= ni&&ni < h && 0 <= nj&&nj < w && c[ni][nj] == 1) {
					dfs(ni, nj); 
				}
			}
		}
		return;
}

int main() {
	cin.sync_with_stdio(false);
	vector<int>ans;
	while (1) {
		cin >> w >> h;
		rep(i, h) {
			rep(j, w) {
				cin >> c[i][j];
			}
		}
		int res = 0;
		rep(i, h) {
			rep(j, w) {
				if (c[i][j] == 1) {
					dfs(i, j);
					res++;
				}
			}
		}
		if (w == 0&&h == 0) {
			break;
		}
		ans.push_back(res);


	}
	rep(i, ans.size()) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3320
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int w,h;
int grid[51][51];

void dfs(int x,int y){
  if(grid[y][x]==0)return;
  grid[y][x]=0;
  for(int i=-1;i<2;i++){
    for(int j=-1;j<2;j++){
      int ny=y+i,nx=x+j;
      if(0<=nx && nx<w && 0<=ny && ny<h)dfs(nx,ny);
    }
  }
}

int main(void){

  while(cin >> w >> h,w|h){
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)cin >> grid[i][j];
    
    int ans=0;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)
	if(grid[i][j]==1)ans++,dfs(j,i);
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1312
#include <iostream>
#include <algorithm>
 
void fastin(int &number) {
    bool negative = false;
    int c;
    number = 0;
    c = getchar_unlocked();
    if (c == '-') {
        negative = true;
        c = getchar_unlocked();
    }
    for (; (c > 47 && c < 58); c = getchar_unlocked()) number = number * 10 + c - 48;
    if (negative) number *= -1;
}
 
void fastout(int64_t n) {
    int64_t N = n, rev, count = 0;
    rev = N;
    if (N == 0) { putchar_unlocked('0'); putchar_unlocked('\n'); return ;}
    while ((rev % 10) == 0) { count++; rev /= 10;}
    rev = 0;
    while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
    while (rev != 0) { putchar_unlocked(rev % 10 + '0'); rev /= 10;}
    while (count--) putchar('0');
}
     
int main(){
        
    int N; fastin(N);
    int A[N];
    for (int i = 0; i < N; ++i) fastin(A[i]);
    sort(A, A + N, std::greater<int>());
     
    int point1 = -1; int point2 = -1;
    int len1, len2;
    for (int i = 0; i < N - 1; ++i) {
    if (A[i] == A[i + 1]){
           point1 = i; len1 = A[i]; break;
        }
    }
    if (point1 < 0){
        fastout(0); return 0;
    }
    for (int i = point1 + 2; i < N - 1; ++i) {
        if (A[i] == A[i + 1]){
            point2 = i; len2 = A[i]; break;
        }
    }
    if (point2 < 0){
        fastout(0); return 0;
    }    
    int64_t ans = 1LL * len1 * len2;
    fastout(ans);
     
    return 0;
}

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

int main() {

  int w,a,b;
  cin >> w >> a >> b;
  
  if(b >= a && b <= a+w) cout << 0 << endl;
  else if(a+w < b) cout << b-(a+w) << endl;
  else cout << a-(b+w) << endl;
  
}


Measured memory_bytes: 256
H,W,A,B = map(int, input().split())
ans = [0]*H
for i in range(H):
  if i<B:
    ans[i] = '0'*A+'1'*(W-A)
  else:
    ans[i] = '1'*A+'0'*(W-A)
print('\n'.join(ans))

Measured memory_bytes: 6900
N = int(input())
S = input()

li = []
c = 0
for i in range( len(S) ):
  if ( c < len(S)-1):
    if S[c]==S[c+1]:
      li.append(2)
      c +=2
    else:
      li.append(1)
      c+=1
  else:
    li.append(1)
    c+=1
  if (c==len(S)):
    break

if (li[0]==1):
  s = 3
else:
  s = 6

MOD = 1000000007
for i in range( len(li)-1 ):
  if ( li[i]==1 and li[i+1]==1 ):
    s = (s*2)%MOD
  if ( li[i]==1 and li[i+1]==2 ):
    s = (s*2)%MOD
  if ( li[i]==2 and li[i+1]==1 ):
    s = s
  if ( li[i]==2 and li[i+1]==2 ):
    s = (s*3)%MOD
print ( s%MOD )
      
  

Measured memory_bytes: 38512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
  ll n,A[200001],ans[200000];
  cin>>n;
  rep(i,n) cin>>A[i];
  ans[0]=0;
  rep(i,n) ans[0]+=pow(-1,i%2)*A[i];
  rep(i,n-1) ans[i+1]=2*A[i]-ans[i];
  rep(i,n) cout<<ans[i]<<" ";
}

Measured memory_bytes: 3456
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"n=int(input())\n"
"a=sorted(map(int,input().split()))\n"
"s=t=0\n"
"for i in range(n-1):\n"
"    s+=a[i]\n"
"    if s*2<a[i+1]:\n"
"        t=i+1\n"
"print(n-t)\n"
"\"";
  system(s);
  return 0;
}            

Measured memory_bytes: 15368
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <queue>
#include <stack> 
#include <sstream>
#include <set>

typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())

int gcd(int a, int b){
    if(a%b==0){
        return b;
    }else{
        return (gcd(b,a%b));
    }
}
int lcm(int a, int b){
    int x = gcd(a,b);
    return (a*b/x);
}
using namespace std;
int main(){
    string l,r;
    int a,b;
    cin >> l >> r >> a >> b;
    string x;
    cin >> x;
    if(l == x){
        a --;
    }else{
        b --;
    }
    cout << a << ' ' <<b <<endl;
}





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

int main(){
    int H, W;
    cin >> H >> W;
    vector<vector<string>> board(H, vector<string>(W));

    for(int i = 0 ; i < H ; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.size() ; j++){
            board.at(i).at(j) = s.at(j);
        }

    }

    vector<int> dx = {1, 0, -1, 0, 1, -1, -1, 1};
    vector<int> dy = {0, 1, 0, -1, 1, 1, -1, -1};

    for(int i = 0 ; i < H ; i++){
        for(int j = 0; j < W ; j++){
            if(board.at(i).at(j) == "#"){
                continue;
            }

            int num = 0;
            for(int d = 0; d < 8 ; d++){
                const int ni = i + dx[d];
                const int nj = j + dy[d];

                if(ni < 0 || H <= ni){
                    continue;
                }
                if(nj < 0 || W <= nj){
                    continue;
                }
                if(board.at(ni).at(nj) == "#"){
                    num++;
                    
                }
            }

            board.at(i).at(j) = char(num + '0');
        }

    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cout << board.at(i).at(j);
        }
        cout << endl;
    }

}

Measured memory_bytes: 3644
#include <iostream>

using namespace std;

int main(){
  int h,w;

  while(cin >>h >>w, (h||w) ){


    for(int i=0; i<h; i++){
          for(int j=0; j<w; j++){
	    cout <<"#";
	  }
	  cout<<endl;
    }
    	  cout<<endl;

  }

  return 0;
}



Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}


int main(){
  long long N;
  cin >> N;
  vector<int> A(N);

  rep(i,N){cin >> A[i];}

  int ans = 0;
  ans += abs(A[0]);
  ans += abs(A[N-1]);
  rep(i,N-1){
    ans += abs(A[i] - A[i+1]);
  }
  //cout << ans << endl;
  //cout << 2*abs(min(0,A[0])) << " " << 2*abs(max(0,A[N-1])) << endl;
  rep(i,N){
    if(i == 0){
      cout << ans + abs(A[1]) - abs(A[0]) - abs(A[1] - A[0]) << endl;
    }else if(i == N-1){
      cout << ans + abs(A[N-2]) - abs(A[N-1]) - abs(A[N-2] - A[N-1]) << endl;
    }else{
      cout << ans + abs(A[i-1] - A[i+1]) - abs(A[i-1] - A[i]) - abs(A[i] - A[i+1]) << endl;
    }
  }

  return 0;
}


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int k, q; cin >> k >> q;
    vector<long long> d(k);
    for (int i = 0; i < k; i++) cin >> d[i];
    for (int qi = 0; qi < q; qi++) {
        long long n, x, m; cin >> n >> x >> m;
        n--;
        vector<long long> e(k+1, 0), eq(k+1, 0);
        for (int i = 0; i < k; i++) {
            e[i+1] = e[i] + d[i] % m;
            eq[i+1] = eq[i] + (d[i] % m == 0);
        }
        x %= m;
        long long sum = x + (n / k) * e[k] + e[n%k];
        long long sub = (n / k) * eq[k] + eq[n%k];
        cout << n - sum / m - sub << "\n";
    }
    return 0;
}

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

int main() {
  int A, B, M;
  cin >> A >> B >> M;
  int a[A], b[B], x, y, c, mina=1000000000, minb=1000000000;
  for(int i=0; i<A; i++) {
     cin >> a[i];
     if(a[i]<mina){
       mina=a[i]; 
     }
  }
  for(int i=0; i<B; i++) {
     cin >> b[i];
     if(b[i]<minb){
        minb=b[i]; 
     }
  }
  int min = mina+minb;
  for(int i=0; i<M; i++) {
    cin >> x >> y >> c;
    int d=a[x-1]+b[y-1]-c;
    if(d<min) {
      min = d;
    }
  }
  cout << min << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
 
using namespace std;
 
struct P {
    int y, x;
    P(int y, int x) : y{y}, x{x} {}
};
 
int limit;
vector<int> v;
 
P getPos(int x)
{
    if (x == 0) return P(0, 2);
    if (1 <= x && x <= 3) return P(1, x);
    if (4 <= x && x <= 8) return P(2, x - 4);
    if (9 <= x && x <= 11) return P(3, x - 8);
    return P(4, 2);
}
 
int getPos(P p)
{
    switch (p.y) {
        case 0:
            return (p.x == 2 ? 0 : -1);
        case 1:
            return (1 <= p.x && p.x <= 3 ? p.x : -1);
        case 2:
            return (0 <= p.x && p.x <= 4 ? p.x + 4 : -1); 
        case 3:
            return (1 <= p.x && p.x <= 3 ? p.x + 8 : -1);
        case 4:
            return (p.x == 2 ? 12 : -1);
    }
    return -1;
}
 
int getMD()
{
    int sum = 0;
    for (int i = 0; i < 13; i++) {
        if (v[i] == 0) continue;
        P np = getPos(i);
        P tp = getPos(v[i]);
        sum += abs(np.x - tp.x) + abs(np.y - tp.y);
    }
    return sum;
}
 
constexpr int dx[] = {-1, 0, 1, 0};
constexpr int dy[] = {0, -1, 0, 1};
 
bool dfs(int sp1, int sp2, int step)
{
    int md = getMD();
    if (md == 0) return 1;
    if (md + step > limit) {
        return 0;
    }
    P p[2] = {getPos(sp1), getPos(sp2)};
    for (int i = 0; i < 2; i++) {
        int x = p[i].x, y = p[i].y;
        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j], ny = y + dy[j];
            P np(ny, nx);
            int next = getPos(np);
            if (next == -1) continue;
            if (i == 0) {
                swap(v[sp1], v[next]);
                if (dfs(next, sp2, step + 1)) {
                    return 1;
                }
                swap(v[sp1], v[next]);
            } else {
                swap(v[sp2], v[next]);
                if (dfs(sp1, next, step + 1)) {
                    return 1;
                }
                swap(v[sp2], v[next]);
            }
        }
    }
    return 0;
}
 
int main()
{
    int x;
    while (cin >> x, x != -1) {
        int sp[2];
        v.resize(13); v[0] = x;
        for (int i = 1; i < 13; i++) {
            cin >> v[i];
        }
        for (int i = 0, j = 0; i < 13; i++) {
            if (v[i] == 0) {
                sp[j++] = i;
            }
        }
        bool found = 0;
        constexpr int LIMIT = 20;
        for (limit = 0; limit <= LIMIT; limit++) {
            if (dfs(sp[0], sp[1], 0)) {
                cout << limit << endl;
                found = 1;
                break;
            }
        }
        if (!found) {
            cout << "NA" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2988
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int dp[5000];

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  cin >> n;
  dp[0]=1;
  for(int s=0;s<=2000;s++){
    for(int j=3;j<=2000;j++){
      dp[s+j] = (dp[s+j]+dp[s])%mod;
    }
  }
  cout << dp[n] << endl;

return 0;
}
///....


Measured memory_bytes: 3724
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC160
{
    class E
    {
        static void Main(string[] args)
        {
            var XYABC = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var X = XYABC[0]; var Y = XYABC[1]; var A = XYABC[2]; var B = XYABC[3]; var C = XYABC[4];
            var p = Console.ReadLine().Split().Select(long.Parse).OrderByDescending(x => x).Take((int)X).ToArray();
            var q = Console.ReadLine().Split().Select(long.Parse).OrderByDescending(x => x).Take((int)Y).ToArray();
            var r = Console.ReadLine().Split().Select(long.Parse).OrderByDescending(x => x).ToArray();

            var pqr = p.Concat(q).Concat(r).OrderByDescending(x => x).ToArray();

            var sum = 0L;
            for (int i = 0; i < X + Y; i++)
            {
                sum += pqr[i];
            }

            Console.WriteLine(sum);

        }
    }
}


Measured memory_bytes: 43988
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var a=new int[n];
		a[0]=sc.I;
		long ans=a[0]-1;
		int p=1;
		a[0]=1;
		for(int i = 1;i<n;i++) {
			a[i]=sc.I;
			if(a[i]>p+1){
				ans+=(a[i]-1)/(p+1);
				a[i]=(a[i]-1)%(p+1);
			}
			p=Max(p,a[i]);
		}
		Console.WriteLine("{0}",ans);
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)
#define EACH(i,c) for(decltype((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) whole(sort, c)
#define RSORT(c) rwhole(sort, c)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

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

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

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

//main code

int main(int argc, char *argv[])
{
	char c;
	cin >> c;
	cout << char(c+1) << endl;
	return 0;
}


Measured memory_bytes: 256