| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Proof | andreyDagger | 1578. Охота на мамонта | 11 июн 2022 17:48 | 1 |
Proof andreyDagger 11 июн 2022 17:48 Why can we always choose the farthest point?
Suppose the opposite. Let we have 3 adjacent points in our way, which make obtuse angle. Let's call them A, B and C. angle ABC is obtuse, that means that |AC|>|AB| and |AC|>|BC|. But that's impossible because our algorithm chooses the farthest point, but B is not the farthest, C is further than B. Contradiction.
Edited by author 11.06.2022 17:49
Edited by author 11.06.2022 17:49 |
| WA15 | andreyDagger | 1578. Охота на мамонта | 11 июн 2022 17:40 | 1 |
WA15 andreyDagger 11 июн 2022 17:40 I had X[2000], then I changed it to X[2002] and got AC |
| I got accepted with a wrong program | georg | 2143. Victoria! | 10 июн 2022 15:47 | 1 |
Test:
99 10
***|_|***
.*.|_|***
*.*|_|***
***|_|***
.*.|_|***
*.*|_|***
and so on (block of 3 rows repeated 33 times).
My program hangs out on this test (takes infinite time), but I got accepted. |
| Strange approach | andreyDagger | 1483. Настольный футбол | 8 июн 2022 21:18 | 2 |
It's obvious that answer for first team is n - 1
How to get answer for second team. Of course total number of points do not exceed
3 * (n * (n - 1) / 2), because we played n * (n - 1) / 2 matches, and in every match summary points not exceed 3. Assume looser team got k points, that mean that total number of points >= k * n. But k * n can't be greater than 3 * n * (n - 1) / 2, so:
k * n <= 3 * n * (n - 1) / 2, then k <= 3 * (n - 1) / 2.
Answer is 3 * (n - 1) / 2. But how to prove that we can make such competition where k is the smallest value and we have (n - 1) values that are not less?
Edited by author 08.06.2022 21:21 |
| explain the logic behind this problem | Unsocial_A | 1023. Пуговицы | 7 июн 2022 10:19 | 3 |
I have seen many people solve this problem using divisor of given number(k).But i cannot understand how it works.Can anyone explain me how this logic works??
sorry for bad english you need to be in control. you are in control when you keep the first player in "loop". if you take number of buttons is 6, say, then the "loop" length is 3, i.e. if you take max number of buttons as 3 - 1 = 2, then whatever amount the first player takes you can keep them in loop. if they take first time 1, you take 2 - in sum 3, 3 - remaining, you are a winner. if they take 2 - you take 1, 3 remaining again - you are a winner.
so, idea is to find the smallest divisor of a number > 2 & answer will be that - 1. hope that makes sense.
Edited by author 18.01.2019 19:50 WLOG, let's break `k` elements of heap into block of length `d`. The numbers below are listed from 1, ..., k in their congruent modulo of `d`.
[1, 2, ...., (d - 1), d], [1, 2, ...., (d - 1), d], ......(k / d) blocks. Here [..] is a block notation. B = #blocks of length `d` = (k / d)
Basis: If B = 1, it's always true, as `first player` can pick whatever from 1, ..., (d - 1), `second player` always left with atleast 1 element by less then d to be picked. So `second player` player will greedily pick all remaining element in the block as an optimal move for his/her winning.
Hypothesis: Let say it's true upto (B - 1) blocks that `second player` has taken the last element.
Proof:
If we have B block then since it is true for (B - 1) blocks we left with 1 block of element to pick and since `first player` is the who pick first in the last 1 block by using the `basis` we know that `second player` is always the winner. Hence, if we take the divisor of number of elements in the heap (k) we always end of with `second player` being the winner.
Edited by author 07.06.2022 10:23
Edited by author 07.06.2022 10:23 |
| WA18 hint | andreyDagger | 1498. Удар с разбега | 6 июн 2022 19:30 | 1 |
Knight can't step on the cell with the horned demon |
| Sokoban visualizer | Grandmaster | 1589. Сокобан | 6 июн 2022 01:52 | 1 |
|
| It will make test for you | D4nick | 1846. НОД 2010 | 5 июн 2022 23:20 | 1 |
int make_test() {
fstream inp("input2.txt", ios::out | ios::binary | ios::in | ios::trunc);
if (!inp)
{
_Post_equals_last_error_ DWORD er = GetLastError();
cerr << er << '\n';
_getch();
exit(1);
}
int n = 100;
inp << n << '\n';
srand(time(0));
for (int i = 0; i < n; i++) {
int sign = rand() % 2;
if (sign == 1 || i < 2) {
int a = rand() % 300;
while (find(simple.begin(), simple.end(), a) != simple.end()) {
a = rand() % 300;
}
inp << "+ " << a << '\n';
v.push_back(a);
}
else if (v.size() > 1) {
int a = rand() % v.size();
inp << "- " << v[a] << '\n';
v.erase(v.begin() + a);
}
}
inp.close();
return 0;
} |
| For reading input in c# | ₰ҟᾷѓßὂνṑγ (ONPU) | 1006. Квадратные рамки | 5 июн 2022 14:12 | 1 |
...
TextReader reader = new StreamReader(Console.OpenStandardInput(), System.Text.Encoding.GetEncoding("iso-8859-1"));
...
string line = reader.ReadLine();
... |
| Could you explain some moments in this problem? | roman velichkin | 1650. Миллиардеры | 1 июн 2022 13:12 | 1 |
Is there possible such test:
1
A aa 10
1 1
1 A bb ?
If then, what correct solution will be: 'aa 1' or 'aa 1, bb 1'?
k - is it a day when person comes to city? Or it is a day when he goes to that city - so person comes in this city on next day?
Why in example 25 days, but result has only 20 days? If two cities have same largest amount of money then it shouldn't be counted?
Edited by author 02.06.2022 13:52 |
| wa#2?? what mean this?? | Hao123 | 1835. Болотный доктор | 1 июн 2022 10:56 | 2 |
Why always i get wrong answer in test#2??
which is the case i didnt condiser??
in the case>>
aa@ab.c
aa@as.a
aa@abs.l
my code return "7"
Edited by author 23.10.2014 02:42
Edited by author 23.10.2014 02:43 ab@ab@ab
4
aa@ab.c
aa@as.a
aa@abs.l
14 |
| WA test#7 | Rudo | 1242. Оборотень | 31 май 2022 02:24 | 1 |
Have no idea what's wrong
I used simple plan with massive of relations and recursive function that checks all ancesters (only up moving) and all descendants (only down moving). There is some part of code in C++:
int checkforblood(int index, int** mas, int* checkmas, int range, int direct) {
if (checkmas[index - 1] == 1) return 0;
checkmas[index-1] = 1;
for (int i = 0; i < range; i++) {
if (( mas[i][0] == index )&&(direct > -1)) {
checkforblood(mas[i][1], mas, checkmas, range, 1);
}
if (( mas[i][1] == index ) && (direct < 1)) {
checkforblood(mas[i][0], mas, checkmas, range, -1);
}
}
return 0;
}
I can't see the problem, so if you can't too i will know, that problem in output method.
Edited by author 31.05.2022 02:26 |
| WA#5 help! | Daria | 1078. Отрезки | 30 май 2022 16:14 | 2 |
Does somebody know what test I need to try to solve this problem? |
| python 3.6 hint | Bergus | 1100. Таблица результатов | 30 май 2022 08:50 | 2 |
limit the number of conversions str->int |
| WA #13 | lijian | 1577. Электронная почта | 30 май 2022 04:00 | 2 |
WA #13 lijian 20 окт 2007 08:03 please give some test data!!
Edited by author 20.10.2007 08:04 Mind mod, I had 10^7+7 and it was failing |
| rounding in python is easy | yyll | 1300. Налогообложение | 28 май 2022 13:02 | 1 |
You can just do calculations with floats as much as possible, e.g., 15% = 0.15, binary search with epsilon = 0.0001.
Rounding with round(x, 2) are needed only when:
1. K*L
2. output of T(K)
-- "The calculation of the regional coefficient and all kinds the taxes is made with rounding off to two digits after a decimal point."
while K itself is float. |
| very short, but MLE/TLE python solution | yyll | 1863. Мирный атом | 28 май 2022 09:37 | 1 |
n, s, k = map(int, input().split())
a = 1 << s
for u in map(int, input().split()):
a = a >> u | (a & (1 << n+1-u) - 1) << u
print((a & -a).bit_length() - 1, a.bit_length() - 1) |
| compiler problem | khodezatuk kobra | 1083. Факториалы!!! | 27 май 2022 20:45 | 1 |
#include<bits/stdc++.h>
using namespace std;
int solve(int n, string k){
int ans=k.size();
if(n>=1){
return n*solve(n-ans);
}
else{
return 1;
}
}
int main()
{
int t,n;
string k;
cin>>n;
cin>>k;
int result=solve(n,k);
cout<<result<<endl;
return 0;
} |
| Wrong answer Test 2 | DrDynamic | 1788. О пользе зонтов | 27 май 2022 18:08 | 1 |
|
| (Test № 4 here) | Iosif inf-10 | 1613. Для любителей статистики | 27 май 2022 08:41 | 6 |
This is Test 4
11
1 2 2 1 1 1 2 2 1 2 1
11
1 1 3
1 4 1
2 8 1
10 11 1
1 3 1
2 3 1
3 7 2
4 6 2
5 9 2
11 11 2
10 11 2
Answer is 01111010101
Edited by author 08.02.2013 04:06 |
