محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت لئونارد در یک شرکت ژنتیکی استخدام شده…
- User
محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت لئونارد در یک شرکت ژنتیکی استخدام شده که روی تغییر دنباله DNA گیاهان برای تولید محصولات بهتر کار میکند. یک ژن دنبالهای از حروف A، C، G و T است.
در تحقیقات اخیر مشخص شده که اگر ژن سیب، شامل ژن t t به صورت یک زیر رشته باشد، ماندگاری بیشتری خواهد داشت. برای رسیدن به این هدف میخواهیم تعدادی حرف در مکانهای مشخصی از ژن سیب تزریق کنیم تا در نهایت ژن نهایی شامل ژن t t شود (ژن t t را به عنوان زیررشته داشته باشد).
تزریق هر یک از چهار کاراکتر هزینهی خاصی دارد. وظیفه لئونارد یافتن مکانهای تزریق ژن و کاراکترهای هر تزریق است بهطوری که در نهایت هزینه کمینه شود. به او کمک کنید تا کمینه هزینه را محاسبه کند.
ورودی در خط اول یک رشته از n n کاراکتر داریم که ژن سیب را مشخص می کند. خط دوم شامل m m کاراکتر است که رشتهی t t را مشخص می کند. کاراکترها حروف انگلیسی بزرگ هستند. خط سوم شامل چهار عدد صحیح است که به ترتیبِ A، C، G و T هزینه اضافه کردن هر کاراکتر را مشخص می کند.
1 ≤ n ≤ 10
000 1≤n≤10 000
1 ≤ m ≤ 5000 1≤m≤5000
0 ≤ a i ≤ 1000 0≤a i ≤1000
خروجی در یک خط کمینه هزینه را چاپ کنید.
مثال ورودی نمونه ۱ TATA CACA 3 0 3 0 Plain text خروجی نمونه ۱ 3 Plain text در این مثال هزینهی اضافه کردن A و G برابر با ۳ و هزینهی اضافه کردن C و T برابر با صفر است. لئونارد میتواند قبل از آخرین A حرف C و بعد از آن حرفهای CA را اضافه کند و در مجموع ۳ واحد هزینه میکند.
ورودی نمونه ۲ TCGCGAG TGCAG 10 10 15 15 Plain text خروجی نمونه ۲ 25 Plain text در این مثال هزینهی اضافه کردن A و C برابر با ۱۰ و هزینهی اضافه کردن G و T برابر با ۱۵ است. لئونارد میتواند قبل از دومین G حرف T و بعد از آن حرف C را اضافه کند و به رشتهی TCGCTGCAG برسد که TGCAG را به عنوان زیر رشته دارد و در مجموع ۲۵ واحد هزینه میکند. write code in java17
- Assistant
To solve this problem, the goal is to determine the minimum cost required to modify the given gene sequence
Ssuch that it containsTas a substring. The modification is done by injecting characters intoS, each with a specific cost.Step-by-Step Reasoning:
-
Understanding the Problem:
- You need to find a minimum cost to insert characters into
Sso thatTbecomes a substring of the modifiedS. - The cost of inserting each character (
A,C,G,T) is provided.
- You need to find a minimum cost to insert characters into
-
Initial Observations:
- The cost to insert each character contributes to the total cost.
- If a character in
Talready matches a character inSat a certain alignment, no cost is incurred for that character.
-
Approach:
- Total Insertion Cost: First, calculate the total cost of inserting all characters of
Tif none of them overlap withS. - Max Overlap Gain: To minimize the insertion cost, maximize the overlap between
SandT. The maximum overlap gain is the maximum sum of the costs of characters inTthat already match with characters inSwhen aligned at various positions. - Final Cost: The minimal cost is then the total insertion cost minus the maximum overlap gain.
- Total Insertion Cost: First, calculate the total cost of inserting all characters of
-
Efficient Calculation:
- Preprocess the positions in
Twhere each character appears. - For each character in
S, check if it aligns with characters inTand accumulate the cost appropriately. - Finally, determine the maximum possible overlap and compute the minimum insertion cost.
- Preprocess the positions in
-
Edge Cases:
- When
Tis already a substring ofS, no insertion is needed. - Ensure that all possible alignments (including those where
Tstarts before or ends afterS) are considered.
- When
Implementation:
Here's the Java implementation based on the above reasoning:
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Read S String S = br.readLine(); int n = S.length(); // Read T String T = br.readLine(); int m = T.length(); // Read costs String[] costStr = br.readLine().split(" "); int costA = Integer.parseInt(costStr[0]); int costC = Integer.parseInt(costStr[1]); int costG = Integer.parseInt(costStr[2]); int costT = Integer.parseInt(costStr[3]); // Map character to cost Map<Character, Integer> charCost = new HashMap<>(); charCost.put('A', costA); charCost.put('C', costC); charCost.put('G', costG); charCost.put('T', costT); // Precompute sum_insert_cost long sum_insert_cost = 0; for(int j=0; j<m; j++) { char cj = T.charAt(j); sum_insert_cost += charCost.get(cj); } // Preprocess T: for each character, store list of j where T[j] == c Map<Character, List<Integer>> T_positions = new HashMap<>(); T_positions.put('A', new ArrayList<>()); T_positions.put('C', new ArrayList<>()); T_positions.put('G', new ArrayList<>()); T_positions.put('T', new ArrayList<>()); for(int j=0; j<m; j++) { char cj = T.charAt(j); T_positions.get(cj).add(j); } // Initialize overlap_gain array // p ranges from -m+1 to n-1, total p_count = n + m -1 int p_count = n + m -1; long[] overlap_gain = new long[p_count]; // Iterate over S for(int i=0; i<n; i++) { char ci = S.charAt(i); if(!T_positions.containsKey(ci)) continue; List<Integer> js = T_positions.get(ci); int size = js.size(); for(int k=0; k<size; k++) { int j = js.get(k); int p = i - j; if(p >= -m +1 && p <= n -1){ int index = p + m -1; if(index >=0 && index < p_count){ overlap_gain[index] += charCost.get(ci); } } } } // Find max_overlap_gain long max_overlap_gain = 0; for(int idx=0; idx<p_count; idx++) { if(overlap_gain[idx] > max_overlap_gain){ max_overlap_gain = overlap_gain[idx]; } } // Compute min_total_cost long min_total_cost = sum_insert_cost - max_overlap_gain; System.out.println(min_total_cost); } }Explanation of the Code:
-
Input Reading:
- The gene sequence
S, the target sequenceT, and the costs for insertingA,C,G, andTare read from the input.
- The gene sequence
-
Preprocessing:
- A map
charCostis used to store the insertion cost for each character. - The total insertion cost
sum_insert_costis calculated as the sum of the costs of all characters inT. - For each character in
T, its positions are stored in lists within theT_positionsmap.
- A map
-
Overlap Gain Calculation:
- For each character in
S, we look up all positions inTwhere this character appears. - For each such position, we calculate the alignment position
pand accumulate the cost if the characters match.
- For each character in
-
Final Calculation:
- The maximum overlap gain
max_overlap_gainis determined. - The minimal insertion cost is calculated by subtracting the maximum overlap gain from the total insertion cost.
- The maximum overlap gain
-
Output:
- The minimal insertion cost is printed as the result.
Sample Runs:
Sample Input 1:
TATA CACA 3 0 3 0Output:
3Sample Input 2:
TCGCGAG TGCAG 10 10 15 15Output:
25This solution efficiently calculates the minimum cost by leveraging character alignments and optimizing overlap gains, ensuring it works within the given constraints.
-