Masala #UT4PSM4V6C
Noto'g'ri yig'indi
Sobirjonda uzunligi \(n\) ga teng \(arr\) butun sonlar massivi bor. Sobirjon shunday ikkita \(i,j(i \neq j)\) sonlar olmoqchiki, \(arr[i] + arr[j]\) yig'indi maksimal bo'lsin.
Ammo muammo shundaki, Sobirjon qo'shish amalini xato bajaradi. U sonlarni qo'shganda xona ko'chisini inobatga olmaydi. Ya'ni qaysidir xonalar uchun, shu xonalardagi raqamlar yig'indisi 9 dan oshsa ham, 1 ni yodda saqlamaydi, keyingi razryadga ta'sir qildirmaydi. Aniq misollar bilan tushuntirgan quyroq.
5 + 5 = 0; 23+17 = 30; 354 + 168 = 412; 55 + 55 = 0; 9+11 = 10;
1000023 + 1070099 = 2070012; 12 + 7 = 19; 9 + 7 = 6; 124 + 123 = 247;
Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 10)\) testlar soni kiritiladi.
Keyin har bir test uchun alohida, birinchi qatorda butun son - \(n(1 \leq n \leq 2 * 10^5)\) kitiriladi. Keyingi qatorda \(n\) ta butun son, \(arr\) massivi elementlar kiritiladi. Sonlar \(0..10^9\) oralig'ida ekanligi kafolatlanadi.
Barcha testlar kesimida \(n\) larning summasi \(10^6\) dan oshmasligi kafolatlanadi.
Har bir test uchun alohida qatorda, uchta butun son chiqaring:
maksimal \(arr[i] + arr[j]\) yig'indini, \(i\) va \(j\) ni. To'g'ri keluvchi \((i, j)\) lar juftligi bir nechta bo'lsa, oldin \(i\) ni minimallashtirishga harakat qiling, so'ngra \(j\) ni minimallashtirishting.
# | input.txt | output.txt |
---|---|---|
1 |
3 3 12 9 7 2 55 55 4 155 55 955 555 |
19 1 3 0 1 2 900 2 3 |