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 ```