Общий форум| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | My O(n) loop solution AC 0.001s, but O(1) sum solution AC 0.015s :)) | coder | 1068. Сумма | 16 окт 2025 09:07 | 1 | | | Problem 1281. River Basin reworked | Vladimir Yakovlev (USU) | 1281. River Basin | 16 окт 2025 03:44 | 1 | Clarifications added to the problem statement regarding river basin definition, river intersection restrictions and input precision.
Tests that were invalid according to the clarifications have been fixed or replaced. Tests 9 and 13 contained overlapping segments making the river flow the same path back and forth; the tests have been replaced with new tests. Tests 15, 16, 18, 19 contained rivers with self-intersections; the tests have been corrected. Test 23 contained a river with a mouth lying on the segment of the other river and didn’t count as tributary; the test has been corrected, this situation is no longer allowed in the tests.
New tests have been added. In particular, tests with more than 2 rivers in a basin have been introduced.
All solutions have been rejudged. 106 authors lost, and 12 other authors gained the solved status for the problem. | | If you have WA#47 | Keworker `~ | 2102. Миша и криптография | 11 окт 2025 20:12 | 2 | Test 47 is some number from 1e14 to 1e18 with correct answer "No". I am stucking at Test 47. I tried some number from 1e14 to 1e18. My program give me expected result. But I cannot figure out why Test 47 give me WA. :( | | the last digit of N...... | Imback | 1049. Отважные воздухоплаватели | 11 окт 2025 12:45 | 1 | | | use long long but not double | Imback | 1011. Кондукторы | 10 окт 2025 13:10 | 1 | use long long integer and mod operator....... fuck the double. | | If you have WA6 | ~'Yamca`~ | 2163. Собеседование | 23 сен 2025 21:38 | 1 | try this test:
3 3
2 2
0 0 0
0 0 0
ans: 1 | | WA2 Помогите! | Bob | 1226. йынтарбО кодяроп | 17 сен 2025 00:00 | 1 | Почему не робит второй тест? | | Soo the problem is only math. | Shomik Shahriar | 1209. 1, 10, 100, 1000... | 14 сен 2025 23:22 | 3 | I tried with precalculating with map for setting up the index with 1 only rest will be auto 0 but miraculously WA at 4. so i figured out that the author only wants you to solve with his idea only. So good luck. These problems are trivial once you start thinking about things algebraically. The author made the constraints the way they are to try to force you in that direction as its an educational problem. | | Brute force Accept in 1.625 | zser | 1044. Счастливые билеты. Easy! | 14 сен 2025 22:58 | 2 | #include <bits/stdc++.h>
using namespace std;
int cal(int x){
int ret = 0;
while (x > 0){
ret += x % 10;
x /= 10;
}
return ret;
}
bool lucky(int x, int mm){
int a = x / mm;
int b = x % mm;
if (cal(a) == cal(b)) return true;
return false;
}
int main(){
int n;
cin >> n;
int nn = round(pow(10, n)) - 1;
int mm = round(pow(10, n / 2));
int tot = 0;
for (int i = 0; i <= nn; i++){
if (lucky(i, mm)) tot++;
}
cout << tot << endl;
}
if your code is simple and fast enough, brute force can work. the input N consists of only even numbers, meaning the number of digits won't be odd.
moreover, input range is limited between 2 and 8, meaning the only possible inputs are 2, 4, 6 and 8.
now this would be my approach :
lets say, the input number is 4 digits in length. meaning, the sum of the first 2 digits need to be equal to the sum of the last 2 digits.
what i'd do is, i'd check for all 2-digit numbers starting from 00 all the way to 99, and store the sum of their digits in an array (in this particular case there are total 100 numbers so that'd be the array length).
after storing the sums in an array, i'd run nested loops through the array. the outer loop would take a sum value from an index. the inner loop would search through all elements in the array from the beginning to the end (including that index from the outer loop too) to see if any sum value matches the outer loop's index sum value. if there's a match, the count increases by 1. the final value of the count is the answer. this process of nested loops is time consuming, so we can sort the array first and then only run the inner loop as long as the next sum values match with the current sum value. this will only improve the performance slightly, as there will still be cases that need the inner loop to run for longer.
a far better approach would be to find the maximum possible value of the sums, and then take an array of that size plus 1. for our example of 4-digit numbers, the maximum possible sum of 2-digit numbers would be 9+9=18 (or 9x2=18) because 99 is the largest 2-digit number. thus the array size here would be 18+1=19 (so that we can access from array[0] all the way to array[18] when needed).
initially, all index values of this array would be 0. as we go through all the 2-digit numbers, we'll find the sum of their digits and raise the value of the corresponding index in the array by 1. this way, we'll immediately know how many times a particular sum has occurred by just looking at that sum's index value, instead of running nested loops. for example, if array[4]=5, then the sum 4 has occurred 5 times in all 2-digit numbers (04, 13, 22, 31, 40). again, if array[5]=6, then the sum 5 has occurred 6 times (05, 14, 23, 32, 41, 50). all we need to do then is find the total sum of all the individual sum count's squares from the entire array.
in case someone doesn't understand why we need to square the individual sum counts : we only counted the sums for 2-digits in our example. but all the possible cases of the 2-digits for a particular sum will occur in both the left half and the right half of a 4-digit number. lets say, the sum value was 4 and a total of 5 cases were found where the 2-digits sum up to 4. then, for each of these 5 cases in one side, all of these 5 cases will occur too in the other side. thus, there will be 5x5=25 total cases where a 4-digit number will have the sum of its left half digits as 4 and the sum of its right half digits as 4 as well. if the sum value was 5, then we'd find 6x6=36 total such 4-digit numbers. that's why we square the individual sum counts before adding them up to the total sum.
there might be even better approaches that i'm not familiar with just yet. maybe an alien would be able to help you with such superior alien concepts. | | Help me with the algorithm | nushrat | 1044. Счастливые билеты. Easy! | 14 сен 2025 22:23 | 2 | Hi,
I need desperate help with building the algo. It seemed easy at first, but I am getting all confused. Can anyone explain the step for calculation ?
Suppose the input is 4 digits, so that means I have to fill up 4 spaces with 9 digits(0-9) for each space and from the combinations, find the one that has equal sum for first 2 and last 2 digits.
If someone can help me with the steps, I think I can figure out the rest.
Thanks in advance. the input N consists of only even numbers, meaning the number of digits won't be odd.
moreover, input range is limited between 2 and 8, meaning the only possible inputs are 2, 4, 6 and 8.
now this would be my approach :
lets say, the input number is 4 digits in length. meaning, the sum of the first 2 digits need to be equal to the sum of the last 2 digits.
what i'd do is, i'd check for all 2-digit numbers starting from 00 all the way to 99, and store the sum of their digits in an array (in this particular case there are total 100 numbers so that'd be the array length).
after storing the sums in an array, i'd run nested loops through the array. the outer loop would take a sum value from an index. the inner loop would search through all elements in the array from the beginning to the end (including that index from the outer loop too) to see if any sum value matches the outer loop's index sum value. if there's a match, the count increases by 1. the final value of the count is the answer. this process of nested loops is time consuming, so we can sort the array first and then only run the inner loop as long as the next sum values match with the current sum value. this will only improve the performance slightly, as there will still be cases that need the inner loop to run for longer.
a far better approach would be to find the maximum possible value of the sums, and then take an array of that size plus 1. for our example of 4-digit numbers, the maximum possible sum of 2-digit numbers would be 9+9=18 (or 9x2=18) because 99 is the largest 2-digit number. thus the array size here would be 18+1=19 (so that we can access from array[0] all the way to array[18] when needed).
initially, all index values of this array would be 0. as we go through all the 2-digit numbers, we'll find the sum of their digits and raise the value of the corresponding index in the array by 1. this way, we'll immediately know how many times a particular sum has occurred by just looking at that sum's index value, instead of running nested loops. for example, if array[4]=5, then the sum 4 has occurred 5 times in all 2-digit numbers (04, 13, 22, 31, 40). again, if array[5]=6, then the sum 5 has occurred 6 times (05, 14, 23, 32, 41, 50). all we need to do then is find the total sum of all the individual sum count's squares from the entire array.
in case someone doesn't understand why we need to square the individual sum counts : we only counted the sums for 2-digits in our example. but all the possible cases of the 2-digits for a particular sum will occur in both the left half and the right half of a 4-digit number. lets say, the sum value was 4 and a total of 5 cases were found where the 2-digits sum up to 4. then, for each of these 5 cases in one side, all of these 5 cases will occur too in the other side. thus, there will be 5x5=25 total cases where a 4-digit number will have the sum of its left half digits as 4 and the sum of its right half digits as 4 as well. if the sum value was 5, then we'd find 6x6=36 total such 4-digit numbers. that's why we square the individual sum counts before adding them up to the total sum.
there might be even better approaches that i'm not familiar with just yet. maybe an alien would be able to help you with such superior alien concepts.
Edited by author 14.09.2025 22:42 | | Your computer won't explode if you will do like here))) | IlushaMax | 1044. Счастливые билеты. Easy! | 14 сен 2025 16:58 | 2 | Just use brute force for getting values for 2,4,6,8 and write it
Edited by author 01.04.2016 23:55 | | I HAVE THE CODE | SorrowAngel | 1044. Счастливые билеты. Easy! | 14 сен 2025 16:53 | 3 | {$APPTYPE CONSOLE}
uses
SysUtils;
var
n:integer;
begin
reset (input,'input.txt');
rewrite (output,'output.txt');
read (n);
if n=2 then
begin
write (10);
halt;
end;
if n=3 then
begin
write (100);
halt;
end;
if n=4 then
begin
write (670);
halt;
end;
if n=5 then
begin
write (6700);
halt;
end;
if n=6 then
begin
write (55252);
halt;
end;
if n=7 then
begin
write (552520);
halt;
end;
if n=8 then
begin
write (4816030);
halt;
end;
if n=9 then
begin
write (48160300);
halt;
end;
if n=10 then
begin
write ('432457640');
halt;
end;
{rewrite (output,'output.txt');
res:=0;
for i:=0 to 9 do
for f:=0 to 9 do
for g:=0 to 9 do
for k:=0 to 9 do
for j:=0 to 9 do
for d:=0 to 9 do
for h:=0 to 9 do
for a:=0 to 9 do
for s:=0 to 9 do
for q:=0 to 9 do
if i+f+g+k+j=d+h+a+s+q then }
end. You are the best problemreader WOW, lol. if only such methods could solve all real life problems.
edit : we solve problems to enhance our skills, not to get the result fast.
Edited by author 14.09.2025 16:54 | | what about odd number of digits? Could someone explain Please | Anupam Ghosh, Wipro Technologies | 1044. Счастливые билеты. Easy! | 14 сен 2025 16:51 | 5 | Hi,
Is this number 63363 lucky number?
Is it necessary all lucky numbers have to be a palindrome?
Regards
Anupam If number of digits is odd, answer is 0. I don't agree. There is no such rule. So you can solve the n-1 problem and then multiplicate it on 10. According to the problem the input number isn't odd as it is divisible 2. source:
"Output
should contain a number of tickets such that the sum of the first half of digits is equal to the sum of the second half of digits." the input says "an even integer N", so there should be no odd number as input. | | test that might help you | Biscuit | 2046. Первый раз в первый класс | 13 сен 2025 12:28 | 1 | 4
lessonk lessonk lessonk lessonk lessonk
Tuesday 1
tententen lollollol yeah yeah kkk
Thursday 1
sevenll four thr haha
Saturday 1
twostrings yeah
Thursday 3 | | <-- Some Test Cases --> | diego.OCI.2019@gmail.com | 1837. Число Исенбаева | 7 сен 2025 14:14 | 2 | Hi, I writed this post because I wanted to share with you some of the test cases* that helped me a lot at the time. I hope it helps you :)
--> Test 1:
1
A B C
--> Answer:
A undefined
B undefined
C undefined
------------------------------
--> Test 2:
5
Isenbaev A B
A B C
D Q P
C H N
G N P
--> Answer:
A 1
B 1
C 2
D 5
G 4
H 3
Isenbaev 0
N 3
P 4
Q 5
------------------------------
--> Test 3:
13
Fominykh Isenbaev BBB
BBB CCC AAA
Ayzenshteyn Oparin Samsonov
Ayzenshteyn Chevdar Samsonov
Dublennykh Fominykh Ivankov
Burmistrov Dublennykh Kurpilyanskiy
Cormen Leiserson Rivest
Oparin AA AAA
Isenbaev Oparin Toropov
AA DD PP
PP QQ RR
RR SS TT
TT Toropov Oparin
--> Answer:
AA 2
AAA 2
Ayzenshteyn 2
BBB 1
Burmistrov 3
CCC 2
Chevdar 3
Cormen undefined
DD 3
Dublennykh 2
Fominykh 1
Isenbaev 0
Ivankov 2
Kurpilyanskiy 3
Leiserson undefined
Oparin 1
PP 3
QQ 4
RR 3
Rivest undefined
SS 3
Samsonov 2
TT 2
Toropov 1
------------------------------
--> Test 4:
3
Isenbaev A B
A B C
A Q W
--> Answer:
A 1
B 1
C 2
Isenbaev 0
Q 2
W 2
------------------------------
*(All test cases were made by other users, so you'll probably found them in other Posts/Topics/Discussions).
Acknowledgments to:
-> "Vit Demidenko" & "Nathalie"
-> "Pavel Nikolov"
-> "mccolt89"
-> "Megakrit"
-How I solved it:
I solved this problem in Java, for that, I used:
->1 java.util.Scanner
->1 java.util.HashMap
->1 java.util.TreeMap
->3 java.util.HashSet
->1 java.util.LinkedList
->? java.util.StringTokenizer (or you can just simply use the Scanner method "next()").
(The structures can be declared inside loops or other structures).
Hope all this helped you :)
Edited by author 08.04.2020 00:48
Edited by author 08.04.2020 00:49 | | Problem 1102 “Strange Dialog” was rejudged (+) | Sandro (USU) | 1102. Странный диалог | 7 сен 2025 01:41 | 1 | New tests were added. 192 authors lost AC. | | What's wrong out there ? Problem 1001 | Iftekhar | 1001. Обратный корень | 6 сен 2025 16:55 | 2 | #include<stdio.h>
#include<math.h>
int main(){
unsigned long long int a,b,c,d;
double Sqrt,Sqrt1,Sqrt2,Sqrt3;
scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
Sqrt=sqrt(a);
Sqrt1=sqrt(b);
Sqrt2=sqrt(c);
Sqrt3=sqrt(d);
printf(" %0.4lf %0.4lf %0.4lf %0.4lf",Sqrt,Sqrt1,Sqrt2,Sqrt3);
}
Edited by author 23.06.2022 13:46
Edited by author 23.06.2022 13:46 | | TLE? | Nisikto | 1846. НОД 2010 | 29 авг 2025 14:31 | 1 | TLE? Nisikto 29 авг 2025 14:31 use iterative segment tree | | ADMINS, PLEASE ADD NEW TESTS (tests are weak) | Oleg Vasilenko (Chelyabinsk) | 1508. Японский кроссворд | 24 авг 2025 14:10 | 1 | My Accepted solution got wrong answer on test:
10 3
1 1 6
??????????
My output: X?X?XXXXXX
Correct output: X.X.XXXXXX | | Idea | __Andrewy__ | 1615. Трамвайный пасьянс | 12 авг 2025 22:26 | 1 | Idea __Andrewy__ 12 авг 2025 22:26 1) Посмотрим, как выглядят плохие расстановки. Тогда ответ = количество хороших расстановок / количество всех расстановок. Обозначим расстановки карт как x = x_1 x_2 ... x_2n.
2) Количество всех расстановок (2n)!
3) Как выглядят плохие расстановки, те когда пасьянс в конце будет содержать >=3 карт?
Чтобы нельзя было сделать ход, нужно чтобы суффикс имел вид (1) ai * bj либо (2) bi * aj, где i != j, а * - любая карта. Заметим, что если какой-то суффикс x после всех просеиваний переходит в один из таких видов, то пасьянс не сойдётся. Можно доказать обратное: если никакой суффикс x при просеиваниях не перейдёт в (1) или (2), то пасьянс сойдется.
4) Из 3) можно построить все плохие расстановки. Они будут иметь вид:
x_1 ... x_[2n-3] bj x_[2n-1] ai
x_1 ... x_[2n-4] bj a_l1 a_l2 ai
x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 ai
x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 a_l4 ai
...
Здесь bj, ai, a_l1, a_l2, ... - выбранные карты (j != i), x_k - оставшиеся карты.
Аналогично к плохим расстановкам будут относится все с заменой местами bj и ai (вместо a_l1, a_l2, ... будут b_l1, b_l2, ...).
Первых расстановок ровно 2n*(n-1)*(2n-2)!
Вторых расстановок 2n*(n-1)*(n-1)*(n-2)*(2n-4)! = 2n*(n-1)*(n-1)! * (2n-4)!
Третьих расстановок 2n*(n-1)*(n-1)*(n-2)*(n-3)*(2n-5)! = 2n*(n-1)*(n-1)! / 2! * (2n-5)!
Четвертых расстановок 2n*(n-1)*(n-1)*(n-2)*(n-3)*(n-4)*(2n-6)! = 2n*(n-1)*(n-1)! / 3! * (2n-6)!
И т.д. до n+1.
Итого плохих расстановок bad_cnt = 2n*(n-1)*(2n-2)! + 2n*(n-1)*(n-1)! * sum((2n-k)!/(n-k+1)!), k=4,...,n+1
good_cnt = (2n)! - bad_cnt
d = gcd(good_cnt, (2n)!)
Ответ = (good_cnt / d, (2n)! / d)
PS: надеюсь не опечатался
Тесты:
(2, '2/3')
(3, '8/15')
(4, '13/28')
(5, '19/45')
(6, '13/33')
(7, '34/91')
(8, '43/120')
(9, '53/153')
(10, '32/95')
(11, '76/231')
(12, '89/276')
(13, '103/325')
(14, '59/189')
(15, '134/435')
(16, '151/496')
(17, '169/561')
(18, '94/315')
(19, '208/703')
(69, '2483/9453')
(100, '5149/19900')
(666, '111388/443223')
(1234, '381614/1522139')
(10000, '50014999/199990000')
(100000, '5000149999/19999900000')
Edited by author 12.08.2025 22:29 |
|
|
