Общий форум| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | WA18? | fatnot | 1424. Маршрутка | 8 янв 2020 23:52 | 1 | WA18? fatnot 8 янв 2020 23:52 How can i fix WA18? Im solving using greedy algo | | some test cases | reshke | 1758. К вопросу о лысине 2 | 8 янв 2020 19:42 | 1 | 50
39
1 33 11 22 44 4 28 14 42 21 7 35 5 25 50 10 20 40 8 32 16 48 24 12 36 18 6 30 15 45 9 27 3 39 13 26 2 34 17
21
17
1 16 8 4 20 10 5 15 3 9 18 6 12 2 14 7 21 | | please help me :( //// What is Test 10? /// thanks :) | s.mohsen | 1123. Зарплата | 8 янв 2020 00:47 | 1 | | | Hotel - Trivago | n000 | 1319. Отель | 7 янв 2020 02:09 | 1 | | | What's your algo? | ACSpeed | 1604. В Стране Дураков | 5 янв 2020 23:27 | 5 | Can you guys share your approach ( and proof if possible ) because mine, though AC, is not very certain. I rely on greedy approach which output pairs with maximum number and minimum number.
Use sort and find min and max after output each pair.
Quite slow, 0.14s :) Greedy approach is fine but why output pairs with maximum number and minimum number ?? Can you guys share your approach ( and proof if possible ) because mine, though AC, is not very certain. I rely on greedy approach which output pairs with maximum number and minimum number.
Use sort and find min and max after output each pair.
Quite slow, 0.14s :) I used a max heap in which I hold pairs like, number i (index of the sign) and frequency of that sign. Each time I pop out from that heap the 2 index with maximal frequency, decrement their frequency and update the heap from their indexes.
I was sure that there is a more simplier aproach to that problem(like greedy), without using heap, but I was just 99.9% sure that with heap I will got AC, and so it was. :)
The same here. I'm using heap, but I'm pulling entries one by one, decrementing and not adding them back until next entry is pulled. I was 146% sure this would work when I decided to implement this algo and it not that bad in terms of time: O(n log k). But I wondered if there is a simple straightforward algo that also would work. Turned out there is. I created an array of pairs (quantity, index) and sorted it. Output the maximum and the next one with a positive quantity, and if there are elements with the same quantity that remains at the maximum, I output them the same way, each step decreasing the number of the output element
Sorry for my English
tests with my answers:
4
8 5 4 3
1 2 1 2 1 2 1 2 1 2 3 1 3 4 1 3 4 1 3 4
5
9 7 4 4 3
1 2 1 2 1 2 1 2 1 2 1 2 4 3 1 2 4 3 5 1 4 3 5 1 4 3 5 | | WA 20 | vtalgo19_manisimova | 1604. В Стране Дураков | 5 янв 2020 22:45 | 2 | WA 20 vtalgo19_manisimova 23 апр 2019 14:58 Test
3
3 3 3
3
1 2 7
5
7 5 4 1 1
Edited by author 05.01.2020 22:51
Edited by author 05.01.2020 23:18 | | If you have WA5 | SButterfly [Samara SAU] | 1987. Вложенные отрезки | 5 янв 2020 19:55 | 3 | Try this test:
5
2 10
2 4
3 4
6 9
7 8
11
1
2
3
4
5
6
7
8
9
10
11
Answer:
-1
2
3
3
1
4
5
5
4
1
-1 Try this test:
5
2 10
2 4
3 4
6 9
7 8
11
1
2
3
4
5
6
7
8
9
10
11
Answer:
-1
2
3
3
1
4
5
5
4
1
-1 My code passes this test... Still getting WA5. The following test helped me to get AC:
7
2 8
2 6
3 3
6 6
7 7
8 8
9 10
10
1
2
3
4
5
6
7
8
9
10
Answer:
-1
2
3
2
2
4
5
6
7
7
I used points sorting + stack approach. My error was in sorting function: I didn't handle situation when points have the same coordinates, the same types, but belong to different segments. Once I added condition which deals with segment numbers, I got AC.
By the way, different compilers may give different results: my program compiled with visual studio gave correct results, while g++ did not.
Edited by author 05.01.2020 20:01 | | Anyone can tell me why is not working? (Test 4 Wrong answer) | Claudiu | 2018. Дебютный альбом | 4 янв 2020 18:02 | 1 | #include <iostream>
using namespace std;
long long maxi,sum=1,sum1=1,n,a,b,i,v[100000],v1[100000];
int main()
{
cin>>n>>a>>b;
if(a>b)
maxi=a;
else
maxi=b;
v[maxi]=1;
v1[maxi]=1;
for(i=maxi+1;i<n+maxi;i++)
{
v[i]=sum1;
v1[i]=sum;
sum=sum+v[i]-v[i-a];
sum1=sum1+v1[i]-v1[i-b];
}
cout<<sum+sum1;
return 0;
} | | WA #7 | Tranvick | 1577. Электронная почта | 3 янв 2020 16:42 | 3 | WA #7 Tranvick 13 дек 2011 16:56 What's this test?? My code: #include <string> #include <algorithm> #include <iostream> #define N 2222 #define MOD 1000000007ll using namespace std; long long f[N][N],d[N][N]; int n,m; string s1,s2; void init(){ getline(cin,s1); getline(cin,s2); n=s1.length(),m=s2.length(); } int main(){ init(); for (int i=0;i<=n;i++) d[i][0]=i; for (int i=0;i<=m;i++) d[0][i]=i; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s1[i-1]==s2[j-1]) d[i][j]=d[i-1][j-1]+1; else d[i][j]=min(d[i-1][j],d[i][j-1])+1; for (int i=0;i<=n;i++) f[i][0]=1; for (int i=0;i<=m;i++) f[0][i]=1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ if (d[i][j]==i || d[i][j]==j) f[i][j]=1; else{ if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]; else f[i][j]=f[i-1][j]+f[i][j-1]; } f[i][j]%=MOD; } cout<<f[n][m]<<endl; } You can try this:
dcfc
dbf
Answer:2 LOL, replying after 7 years. | | To admins WA Test1 in C# | rusden220 | 1104. Не спрашивай даму о возрасте | 2 янв 2020 21:49 | 1 | If you get WA for the first test in C#
using System;
namespace Timus1104
{
class Program
{
static void Main(string[] args)
{
var inputNumber = Console.ReadLine();
Console.WriteLine("22");
}
}
}
just add return value
using System;
namespace Timus1104
{
class Program
{
static int Main(string[] args)
{
var inputNumber = Console.ReadLine();
Console.WriteLine("22");
return 0;
}
}
} | | Maybe you did the same! | Tigoan Matei | 2056. Стипендия | 1 янв 2020 17:00 | 1 | dont use ',' use '.' at 4.5 | | Sheer bliss! | Yermak | 1763. Блоха-знаток | 31 дек 2019 18:39 | 6 | I did it! I figured out this formula! give any hint: F[n] = summa(a[i] * F[n-i], i=1..k) are right? (here a[i], and k - are consts).
k=?
a[]- easy generate, iff k - know. Yes, you are right. k = 19.
Good luck! :-D (n-19>=7) start from 7... Hint: solve system equation with Gauss method (19x19).
Edited by author 31.12.2019 16:33
static constexpr int results[] =
{ // 0 1 2 3 4 5
0, 0, 0, 0, 0, 0,
/*Answer for n = 6 is*/ 12,
/*Answer for n = 7 is*/ 46,
/*Answer for n = 8 is*/ 144,
/*Answer for n = 9 is*/ 110,
/*Answer for n = 10 is*/ 312,
/*Answer for n = 11 is*/ 290,
/*Answer for n = 12 is*/ 670,
/*Answer for n = 13 is*/ 706,
/*Answer for n = 14 is*/ 1538,
/*Answer for n = 15 is*/ 1732,
/*Answer for n = 16 is*/ 3504,
/*Answer for n = 17 is*/ 4288,
/*Answer for n = 18 is*/ 8098,
/*Answer for n = 19 is*/ 10568,
/*Answer for n = 20 is*/ 19044,
/*Answer for n = 21 is*/ 26042,
/*Answer for n = 22 is*/ 45222,
/*Answer for n = 23 is*/ 64220,
/*Answer for n = 24 is*/ 108382,
/*Answer for n = 25 is*/ 158324,
/*Answer for n = 26 is*/ 261754,
/*Answer for n = 27 is*/ 390314,
/*Answer for n = 28 is*/ 635666,
/*Answer for n = 29 is*/ 962282,
/*Answer for n = 30 is*/ 1550244,
/*Answer for n = 31 is*/ 2372372,
/*Answer for n = 32 is*/ 3792560,
/*Answer for n = 33 is*/ 5848746,
/*Answer for n = 34 is*/ 9299148,
/*Answer for n = 35 is*/ 14419296,
/*Answer for n = 36 is*/ 22838014,
/*Answer for n = 37 is*/ 35548790,
/*Answer for n = 38 is*/ 56153296,
/*Answer for n = 39 is*/ 87640646,
/*Answer for n = 40 is*/ 138180196,
/*Answer for n = 41 is*/ 216065986,
/*Answer for n = 42 is*/ 340223834,
/*Answer for n = 43 is*/ 532680994,
/*Answer for n = 44 is*/ 838025410,
/*Answer for n = 45 is*/ 1313251780,
/*Answer for n = 46 is*/
};
Edited by author 31.12.2019 16:33 Thanks for the sequence! The problem is indeed solved with linear recurrence (your message from 2012). Although, it seems k=20 here, and one needs to run Gauss on 20x20 matrix. I got by solution by using Berlekamp—Massey though.
I wonder, how could you guess there is a linear recurrence and that K is small enough to brute force the sequence in finite time (I assume that's how you got it).
Edited by author 31.12.2019 18:41 | | Easy solution C++ | Znol | 1902. Нео-Венеция | 31 дек 2019 17:07 | 1 | #include <string> #include <iostream> #include <algorithm> #include <iomanip> #include <math.h> using namespace std; int main() { double n, t, s; cin >> n >> t >> s; double opposite[1000]; for (int i = 0; i < n; i++) { cin >> opposite[i]; if (opposite[i] >= s) { cout << fixed << setprecision(6) << ((opposite[i] + (s + t)) / 2) << endl; } else { cout << fixed << setprecision(6) << ((s + (opposite[i] + t)) / 2) << endl; } } } | | Test 6 Access Violation | Znol | 1001. Обратный корень | 31 дек 2019 14:43 | 1 | I think the promblem is in i-=2; This is to reduce i for ^Z symbol; idk how to fix this. #include <iostream> #include <algorithm> #include <iomanip> #include <math.h> using namespace std; int main() { double num[1000]; int i = 0; for (i; cin; i++) { cin >> num[i]; } for (i-=2; i >= 0; i--) { cout << fixed << setprecision(4) << sqrt(num[i]) << endl; } } | | Minimum n for k=18 ? | Mickkie | 2049. Химия | 30 дек 2019 20:46 | 2 | Does solution for (n,k) (19,18) exist?
I only find the answer for (21,18).
Do you guy have a better idea?
31
2 1
4 3
3 1
1 5
7 6
6 5
5 1
1 5
9 8
8 5
5 10
12 11
11 10
10 5
5 1
1 5
13 10
10 5
5 14
16 15
15 14
14 5
5 14
18 17
17 14
14 19
21 20
20 19
19 14
14 5
5 1 turns out n=19
you can reach state (10,9) and get to (1,18)
this problem has the very beautiful soln. thanks to author. | | unable to understand first example. can anyone please kindly explain. | anupam ghosh | 1671. Паутина Ананси | 30 дек 2019 17:16 | 1 | unable to understand first example. can anyone please kindly explain. | | So easy / phyton 3 solution | SMMaster | 1021. Таинство суммы | 30 дек 2019 14:32 | 1 | o = 0
k = int(input())
a = [0] * (65536*2)
for i in range(k):
a[int(input()) + 32768] = 1
h = int(input())
for i in range(h):
if a[10000 - int(input()) + 32768] != 0:
o += 1
if o >= 1:
print('YES')
else:
print('NO') | | Test 8 python | bhn | 1196. Экзамен по истории | 30 дек 2019 14:31 | 7 | time limit exceed on python3
there a code:
a=[]
for i in range(int(input())):
a.append(input())
b=[]
n=0
for j in range(int(input())):
if input() in a:
n+=1
print(n)
please help me There is "Time limit exceeded" with binary search too. i think that on python i wil not can solve this import sys
ll = set()
for i in range(int(sys.stdin.readline())):
ll.add(sys.stdin.readline())
n = 0
for j in range(int(sys.stdin.readline())):
if sys.stdin.readline() in ll:
n += 1
print(n) | | TLE #8: How can I make this Python code faster? | Neeraj Kumar | 1196. Экзамен по истории | 30 дек 2019 14:30 | 2 | import sys
p = input()
p_list = []
for i in range(int(p)):
x = input()
p_list.append(x)
s = input()
s_list = []
for i in range(int(s)):
x = input()
s_list.append(x)
count = 0
l = set(s_list).intersection(p_list)
for i in l:
count += s_list.count(i)
print (count) import sys
ll = set()
for i in range(int(sys.stdin.readline())):
ll.add(sys.stdin.readline())
n = 0
for j in range(int(sys.stdin.readline())):
if sys.stdin.readline() in ll:
n += 1
print(n) | | So easy / phyton 3 solution | SMMaster | 1567. SMS-спам | 29 дек 2019 17:53 | 1 | a = input()
s = 0
ll = ['c','f','i','l','o','r','u','x','!']
hh = ['b','e','h','k','n','q','t','w','z',',']
pp = ['a','d','g','j','m','p','s','v','y','.',' ']
for i in range(len(a)):
if a[i] in ll:
s+=3
elif a[i] in hh:
s+=2
elif a[i] in pp:
s+=1
print(s) |
|
|
