codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1426.md (4893B)


      1 Source: https://codeforces.com/blog/entry/83120
      2 
      3 [1426A - Floor Number](/contest/1426/problem/A "Codeforces Round 674 (Div. 3)")
      4 
      5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 for i in range(int(input())):
     15     n, x = map(int, input().split())
     16     print(1 if n <= 2 else (n - 3) // x + 2)
     17 ```
     18 
     19 [1426B - Symmetric Matrix](/contest/1426/problem/B "Codeforces Round 674 (Div. 3)")
     20 
     21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution**
     28 
     29 ```
     30 for i in range(int(input())):
     31 	n, m = map(int, input().split())
     32 	a = []
     33 	for i in range(n):
     34 		a.append([[int(x) for x in input().split()] for i in range(2)])
     35 	ok = False
     36 	for i in range(n):
     37 		ok |= a[i][0][1] == a[i][1][0]
     38 	ok &= m % 2 == 0
     39 	print("YES" if ok else "NO")
     40 ```
     41 
     42 [1426C - Increase and Copy](/contest/1426/problem/C "Codeforces Round 674 (Div. 3)")
     43 
     44 Idea: [vovuh](/profile/vovuh "Master vovuh")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution**
     51 
     52 ```
     53 #include <bits/stdc++.h>
     54 
     55 using namespace std;
     56 
     57 int main() {
     58 #ifdef _DEBUG
     59 	freopen("input.txt", "r", stdin);
     60 //	freopen("output.txt", "w", stdout);
     61 #endif
     62 	
     63 	int t;
     64 	cin >> t;
     65 	while (t--) {
     66 		int n;
     67 		cin >> n;
     68 		int ans = 1e9;
     69 		for (int x = 1; x * x <= n; ++x) {
     70 			ans = min(ans, x - 1 + ((n - x) + x - 1) / x);
     71 		}
     72 		cout << ans << endl;
     73 	}
     74 	
     75 	return 0;
     76 }
     77 ```
     78 
     79 **Solution 2**
     80 
     81 ```
     82 #include<bits/stdc++.h>
     83 
     84 using namespace std;
     85 
     86 const long double EPS = 1e-9;
     87 
     88 long long f(long long x)
     89 {                                                        
     90 	long long z = sqrtl(x);
     91 	long long ans = 1e18;
     92 	for(int i = -5; i <= 5; i++)
     93 	{
     94 	 	long long z2 = z - i;
     95 	 	if(z2 > x || z2 < 1)
     96 	 		continue;
     97 	 	ans = min(ans, z2 - 2 + (x + z2 - 1) / z2);
     98 	}
     99 	return ans;
    100 }
    101 
    102 int main()
    103 {
    104  	int t;
    105  	cin >> t;
    106  	for(int i = 0; i < t; i++)
    107  	{
    108  	 	long long x;
    109  	 	cin >> x;
    110  	 	cout << f(x) << endl;
    111  	}
    112 }
    113 ```
    114 
    115 [1426D - Non-zero Segments](/contest/1426/problem/D "Codeforces Round 674 (Div. 3)")
    116 
    117 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...
    122 
    123 **Solution**
    124 
    125 ```
    126 n = int(input())
    127 a = [int(x) for x in input().split()]
    128 d = set()
    129 d.add(0)
    130 cur = 0
    131 ans = 0
    132 for i in range(n):
    133 	cur += a[i]
    134 	if cur in d:
    135 		ans += 1
    136 		d = set()
    137 		d.add(0)
    138 		cur = a[i]
    139 	d.add(cur)
    140 print(ans)
    141 ```
    142 
    143 [1426E - Rock, Paper, Scissors](/contest/1426/problem/E "Codeforces Round 674 (Div. 3)")
    144 
    145 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
    146 
    147 **Tutorial**
    148 
    149 Tutorial is loading...
    150 
    151 **Solution**
    152 
    153 ```
    154 #include <bits/stdc++.h>
    155 
    156 #define sz(v) int(v.size())
    157 #define all(v) v.begin(), v.end()
    158 #define pb push_back
    159 #define ft first
    160 #define sc second
    161 
    162 using namespace std;
    163 
    164 int n;
    165 vector<int> a, b;
    166 
    167 inline void read() {
    168 	cin >> n;
    169 	a.resize(3);
    170 	b.resize(3);
    171 	for (int i = 0; i < 3; i++) cin >> a[i];
    172 	for (int i = 0; i < 3; i++) cin >> b[i];
    173 }
    174 	
    175 inline void solve() {
    176 	int ans1 = INT_MAX;
    177 	vector<pair<int, int> > ord;
    178 	ord.pb({0, 0});
    179 	ord.pb({0, 2});
    180 	ord.pb({1, 1});
    181 	ord.pb({1, 0});
    182 	ord.pb({2, 2});
    183 	ord.pb({2, 1});
    184 	sort(all(ord));
    185 	do {
    186 		vector<int> a1 = a, b1 = b;
    187 		for (int i = 0; i < sz(ord); i++) {
    188 			int cnt = min(a1[ord[i].ft], b1[ord[i].sc]);
    189 			a1[ord[i].ft] -= cnt;
    190 			b1[ord[i].sc] -= cnt;			
    191 		}
    192 		int cur = min(a1[0], b1[1]) + min(a1[1], b1[2]) + min(a1[2], b1[0]);
    193 		ans1 = min(ans1, cur);
    194 	} while(next_permutation(all(ord)));
    195 	int ans2 = min(a[0], b[1]) + min(a[1], b[2]) + min(a[2], b[0]);
    196 	cout << ans1 << ' ' << ans2 << endl;
    197 }
    198 
    199 int main () {
    200     read();
    201     solve();
    202 }
    203 ```
    204 
    205 [1426F - Number of Subsequences](/contest/1426/problem/F "Codeforces Round 674 (Div. 3)")
    206 
    207 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
    208 
    209 **Tutorial**
    210 
    211 Tutorial is loading...
    212 
    213 **Solution**
    214 
    215 ```
    216 #include <bits/stdc++.h>
    217                             
    218 using namespace std;
    219 
    220 const int MOD = int(1e9) + 7;
    221 const int N = 200043;
    222 const int K = 4;
    223 
    224 int add(int x, int y)
    225 {
    226  	x += y;
    227  	while(x >= MOD) x -= MOD;
    228  	while(x < 0) x += MOD;
    229  	return x;
    230 }
    231 
    232 int mul(int x, int y)
    233 {
    234  	return (x * 1ll * y) % MOD;
    235 }
    236 
    237 int n;
    238 string s;
    239 int dp[N][K][K];
    240 char buf[N];
    241 int pow3[N];
    242 
    243 int main() {
    244 	scanf("%d", &n);
    245 	scanf("%s", buf);
    246 	s = buf;
    247 	int cntQ = 0;
    248 	for(auto c : s)
    249 		if(c == '?')
    250 			cntQ++;
    251 	pow3[0] = 1;
    252 	for(int i = 1; i < N; i++)
    253 		pow3[i] = mul(pow3[i - 1], 3);
    254 	dp[0][0][0] = 1;
    255 	for(int i = 0; i < n; i++)
    256 		for(int j = 0; j <= 3; j++)
    257 			for(int k = 0; k <= 3; k++)
    258 			{
    259 			 	if(!dp[i][j][k]) continue;
    260 			 	dp[i + 1][j][k] = add(dp[i + 1][j][k], dp[i][j][k]);
    261 			 	if(j < 3 && (s[i] == '?' || s[i] - 'a' == j))
    262 			 	{
    263 			 	 	int nk = (s[i] == '?' ? k + 1 : k);
    264 			 	 	dp[i + 1][j + 1][nk] = add(dp[i + 1][j + 1][nk], dp[i][j][k]);
    265 			 	}
    266 		   	}
    267 	int ans = 0;
    268 	for(int i = 0; i <= 3; i++)
    269 		if(cntQ >= i)
    270 			ans = add(ans, mul(dp[n][3][i], pow3[cntQ - i]));
    271 	printf("%d\n", ans);
    272 }
    273 ```