Amedeo
SYMBIOSYS OF
PURPOSE & STYLE
Follow us

Search

ekusiadadus
  -  Programming   -  Competitive Programming   -  AtCoder   -  ABC   -  AtCoder Beginner Contest 196

AtCoder Beginner Contest 196 Solutions with Golang


問題名
実行時間制限メモリ制限
ADifference Max2 sec1024 MB提出
BRound Down2 sec1024 MB提出
CDoubled2 sec1024 MB提出
DHanjo2 sec1024 MB提出
EFilters2 sec1024 MB提出
FSubstring 23 sec1024 MB提出

A. Difference Max

A – Difference Max Editorial / 


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 100100 points

Problem Statement

Given are integers aabbcc, and dd.
We will choose integers xx and yy such that a≤x≤ba≤x≤b and c≤y≤dc≤y≤d. Find the maximum possible value of x−yx−y here.

Constraints

  • All values in input are integers.
  • −100≤a≤b≤100−100≤a≤b≤100
  • −100≤c≤d≤100−100≤c≤d≤100

Solution

package main

import (
  "fmt"
)

func main(){
  var a,b,c,d int
  fmt.Scan(&a, &b, &c, &d)
  fmt.Println(c-b)
}

B.Round Down

B – Round Down Editorial / 


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 200200 points

Problem Statement

Given an integer or a decimal XX, round it down to an integer and print the result.

Constraints

  • 0≤X≤101000≤X≤10100
  • XX is an integer or a decimal with at most 100100 digits after the decimal point, without unnecessary leading zeros.

solution

package main

import (
	"fmt"
)

func main(){
	var s string
	fmt.Scan(&s)
	var t string
	for i := 0; i < len(s); i++ {
		if(s[i] == '.') {
			break
		} else {
			t = t+string(s[i])
		}
	}
	fmt.Println(t)
}

C.Doubled

C – Doubled Editorial / 


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

Given is an integer NN.
How many integers xx between 11 and NN (inclusive) satisfy the following condition?

  • The decimal representation (without leading zeros) of xx has an even number of digits, and its first and second halves are equal as strings.

Constraints

  • NN is an integer.
  • 1≤N<10121≤N<1012

solution

package main

import (
	"fmt"
	"math"
)

func main(){
	var ans int64
	var n int64
	fmt.Scan(&n)
	var i int64
	for i = 1; i <= 1000000; i++ {
		var t int64 = i
		d := 0
		for ; t >= 1;{
			t = t/10
			d++
		}
		 t = i+i*(int64)(math.Pow(10.0, (float64)(d)))
		 if t <= n {
			 ans++
		 }else{
			 break
		 }
	}
	fmt.Println(ans)
}

D.Hanjo

D – Hanjo Editorial / 


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 400400 points

Problem Statement

We have a rectangular room that is HH meters long and WW meters wide.
We will cover this room with AA indistinguishable 22 meters ×× 11 meters rectangular tatami mats and BB indistinguishable 11 meter ×× 11 meter square tatami mats. The rectangular mats can be used in either direction: they can be 22 meters long and 11 meter wide, or 11 meter long and 22 meters wide.
How many ways are there to do this?
Here, it is guaranteed that 2A+B=HW2A+B=HW, and two ways are distinguished if they match only after rotation, reflection, or both.

Constraints

  • All values in input are integers.
  • 1≤H,W1≤H,W
  • HW≤16HW≤16
  • 0≤A,B0≤A,B
  • 2A+B=HW2A+B=HW

Solution

package main

import (
	"fmt"
)

var h,w int
var d[16][16] int

func dfs(i int, j int, a int, b int) int{
	res := 0
	if a < 0 || b < 0{
		return 0
	}
	if j == w {
		j = 0
		i = i+1
	}
	if i == h {
		return 1
	}
	if d[i][j] == 1{
		return dfs(i,j+1, a,b)
	}
	d[i][j] = 1
	res = res + dfs(i,j+1,a,b-1)
	if j+1 < w && d[i][j+1] == 0 {
		d[i][j+1] = 1
		res = res + dfs(i,j+1, a-1, b)
		d[i][j+1] = 0
	}
	if i+1 < h && d[i+1][j] == 0 {
		d[i+1][j] = 1
		res = res + dfs(i,j+1,a-1,b)
		d[i+1][j] = 0
	}
	d[i][j] = 0
	return res
}

func main(){
	var a, b int
	fmt.Scan(&h,&w,&a,&b)
	fmt.Println(dfs(0,0,a,b))
}

E.Filters

E – Filters Editorial / 


Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500500 points

Problem Statement

Given are integer sequences A=(a1,a2,…,aN)A=(a1,a2,…,aN)T=(t1,t2,…,tN)T=(t1,t2,…,tN), and X=(x1,x2,…,xQ)X=(x1,x2,…,xQ).
Let us define NN functions f1(x),f2(x),…,fN(x)f1(x),f2(x),…,fN(x) as follows:

fi(x)=⎧⎨⎩x+ai(ti=1)max(x,ai)(ti=2)min(x,ai)(ti=3)fi(x)={x+ai(ti=1)max(x,ai)(ti=2)min(x,ai)(ti=3)

For each i=1,2,…,Qi=1,2,…,Q, find fN(…f2(f1(xi))…)fN(…f2(f1(xi))…).

Constraints

  • All values in input are integers.
  • 1≤N≤2×1051≤N≤2×105
  • 1≤Q≤2×1051≤Q≤2×105
  • |ai|≤109|ai|≤109
  • 1≤ti≤31≤ti≤3
  • |xi|≤109

solution


This Go code was not accepted, because methods(fmt.scan, fmt.print) were too slow.
Instead of using fmt, you should use buffer methods.
But I don’t know much about it, I show you C++ solutions too.

package main

import (
	"fmt"
)

func main(){
	var n, q int64
	fmt.Scan(&n)
	a := make([]int64, n)
	t := make([]int64, n)

	var low, high, add int64
	low = (int64)(-1e18)
	high = (int64)(1e18)
	var i int64
	for i = 0; i < n; i++ {
		fmt.Scan(&a[i])
		fmt.Scan(&t[i])
		if t[i] == 1 {
			low = low + a[i]
			high = high + a[i]
			add = add + a[i]
		}else if t[i] == 2{
			if low < a[i] {
				low = a[i]
			}
			if high < a[i] {
				high = a[i]
			}
		} else {
			if low > a[i]{
				low = a[i]
			}
			if high > a[i]{
				high = a[i]
			}
		}
	}

	fmt.Scan(&q)
	for i = 0; i < q; i++ {
		var x int64
		fmt.Scan(&x)
		if x + add < low {
			fmt.Println(low)
		}else if x+add > high {
			fmt.Println(high)
		}else {
			fmt.Println(x+add)
		}
	}
}
#include<bits/stdc++.h>
using namespace std;

void chmin(ll &a, ll b){if(a > b) a = b;}
void chmax(ll &a, ll b){if(a < b) a = b;}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n, q;
  cin >> n;
  vector<int> a(n), t(n);
  for(int i = 0; i < n; ++i) cin >> a[i] >> t[i];
  cin >> q;
  vector<int> x(q);
  for(int i = 0; i < q; ++i) cin >> x[i];
  ll low = -1e18, high = 1e18, add = 0;
  for(ll i = 0; i < n; ++i){
    if(t[i] == 1){
      low += a[i];
      high += a[i];
      add += a[i];
    }else if (t[i] == 2){
      chmax(low,a[i]);
      chmax(high,a[i]);
    }else{
      chmin(low,a[i]);
      chmin(high,a[i]);
    }
  }
  for(ll i = 0; i < q; ++i){
    if(x[i]+add < low) cout << low << endl;
    else if(x[i]+add > high) cout << high << endl;
    else cout << x[i]+add << endl;
  }
  return 0;
}

Leave a Comment