5/22/24, 12:10 PM Problem - 1729F - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 820 (Div. 3)
F. Kirei and the Linear Function Finished
time limit per test: 3 seconds Practice
memory limit per test: 256 megabytes
input: standard input
output: standard output
Given the string s of decimal digits (0-9) of length n . → Virtual participation
A substring is a sequence of consecutive characters of a string. The substring of this string is
→ Clone Contest to Mashup
defined by a pair of indexes — with its left and right ends. So, each pair of indexes (l, r ),
where 1 ≤ l ≤ r ≤ n , corresponds to a substring of the string s. We will define as v(l, r)
the numeric value of the corresponding substring (leading zeros are allowed in it). → Submit?
For example, if n = 7, s ="1003004", then v(1, 3) = 100, v(2, 3) = 0 and
Language: GNU G++20 13.2 (64 bit, winlibs)
v(2, 7) = 3004.
Choose
You are given n , s and an integer w (1 Choose File No file chosen
≤ w < n). file:
You need to process m queries, each of which is characterized by 3 numbers li , ri , ki ( Submit
1 ≤ li ≤ ri ≤ n; 0 ≤ ki ≤ 8).
The answer to the i th query is such a pair of substrings of length w that if we denote them as
→ Contest materials
(L1 , L1 + w − 1) and (L2 , L2 + w − 1), then:
Announcement
L1 ≠ L2 , that is, the substrings are different;
the remainder of dividing a number Tutorial
v(L1 , L1 + w − 1) ⋅ v(li , ri ) + v(L2 , L2 + w − 1) by 9 is equal to ki .
If there are many matching substring pairs, then find a pair where L1 is as small as possible. If
there are many matching pairs in this case, then minimize L2 .
Note that the answer may not exist.
Input
The first line contains a single integer t (1 ≤ t ≤ 104 ) — number of input test cases.
The first line of each test case contains a string s, which contains only the characters 0-9 and
has a length n (2 ≤ n ≤ 2 ⋅ 105 ).
The second line contains two integers w, m (1 ≤ w < n, 1 ≤ m ≤ 2 ⋅ 105 ), where n — is
the length of the given string s. The number w denotes the lengths of the substrings being
searched for, and m is the number of queries to be processed.
The following m lines contain integers li , ri , ki (1 ≤ li ≤ ri ≤ n, 0 ≤ ki ≤ 8) — i th
query parameters.
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 105 . It is also
5
guaranteed that the sum of m over all test cases does not exceed 2 ⋅ 10 .
Output
For each request, print in a separate line:
left borders of the required substrings: L1 and L2 ;
-1 -1 otherwise, if there is no solution.
If there are several solutions, minimize L1 first, and minimize L2 second.
https://mirror.codeforces.com/problemset/problem/1729/F 1/2
5/22/24, 12:10 PM Problem - 1729F - Codeforces
Example
input Copy
5
1003004
4 1
1 2 1
179572007
4 2
2 7 3
2 7 4
111
2 1
2 2 6
0000
1 2
1 4 0
1 4 1
484
1 5
2 2 0
2 3 7
1 2 5
3 3 8
2 2 6
output Copy
2 4
1 5
1 2
-1 -1
1 2
-1 -1
1 3
1 3
-1 -1
-1 -1
-1 -1
Note
= 7, s ="1003004",
Consider the first test case of example inputs. In this test case n
w = 4 and one query l1 = 1, r1 = 2 , k1 = 1. Note that v(1, 2) = 10. We need to find a
pair of substrings of length 4 such that v(L1 , L1 + 3) ⋅ 10 + v(L2 , L2 + 3) has a
remainder of k1 = 1 when divided by 9 . The values L1 = 2, L2 = 4 actually satisfy all the
requirements: v(L1 , L1 + w − 1) = v(2, 5) = 30,
v(L2 , L2 + w − 1) = v(4, 7) = 3004. Indeed, 30 ⋅ 10 + 3004 = 3304 , which has a
remainder of 1 when divided by 9 . It can be shown that L1 = 2 is the minimum possible
value, and L2 = 4 is the minimum possible with L1 = 2 .
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/22/2024 12:06:43UTC+5 (l1).
Desktop version, switch to mobile version.
Privacy Policy
Supported by
https://mirror.codeforces.com/problemset/problem/1729/F 2/2
