| ENG RUS | Timus Online Judge |
Common Boards.mohsen please help me :( //// What is Test 10? /// thanks :) // Problem 1123. Salary 8 Jan 2020 00:47 n000 Hotel - Trivago // Problem 1319. Hotel 7 Jan 2020 02:09 ACSpeed What's your algo? [4] // Problem 1604. Country of Fools 25 Nov 2011 20:46 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 :) gautamvs Re: What's your algo? // Problem 1604. Country of Fools 27 Mar 2013 12:56 Greedy approach is fine but why output pairs with maximum number and minimum number ?? ACSpeed wrote 25 November 2011 20:46 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 :) Ion Ureche Re: What's your algo? [2] // Problem 1604. Country of Fools 16 Sep 2013 14:30 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. :) B@R5uk Re: What's your algo? [1] // Problem 1604. Country of Fools 10 Jan 2018 15:41 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. Mapu Re: What's your algo? // Problem 1604. Country of Fools 5 Jan 2020 23:27 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 vtalgo19_manisimova WA 20 [1] // Problem 1604. Country of Fools 23 Apr 2019 14:58 What is test 20? Mapu Re: WA 20 // Problem 1604. Country of Fools 5 Jan 2020 22:45 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 SButterfly [Samara SAU] If you have WA5 [2] // Problem 1987. Nested Segments 6 Jan 2015 23:12 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 Ealham Re: If you have WA5 // Problem 1987. Nested Segments 24 Feb 2019 19:44 SButterfly [Samara SAU] wrote 6 January 2015 23:12 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. megacrab-3000 Re: If you have WA5 // Problem 1987. Nested Segments 5 Jan 2020 19:55 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 Claudiu Anyone can tell me why is not working? (Test 4 Wrong answer) // Problem 2018. The Debut Album 4 Jan 2020 18:02 #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; } Tranvick WA #7 [2] // Problem 1577. E-mail 13 Dec 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; } Shallowy Re: WA #7 [1] // Problem 1577. E-mail 24 Jul 2018 11:25 You can try this: dcfc dbf Answer:2 Alikhan Zimanov Re: WA #7 // Problem 1577. E-mail 3 Jan 2020 16:42 LOL, replying after 7 years. rusden220 To admins WA Test1 in C# // Problem 1104. Don’t Ask Woman about Her Age 2 Jan 2020 21:49 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; } } } Tigoan Matei Maybe you did the same! // Problem 2056. Scholarship 1 Jan 2020 17:00 dont use ',' use '.' at 4.5 Yermak Sheer bliss! [5] // Problem 1763. Expert Flea 3 Feb 2011 05:33 I did it! I figured out this formula! xurshid_n Re: Sheer bliss! [4] // Problem 1763. Expert Flea 8 Jun 2012 19:53 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. bsu.mmf.team Re: Sheer bliss! [3] // Problem 1763. Expert Flea 4 Dec 2012 16:51 Yes, you are right. k = 19. Good luck! :-D Shen Yang Re: Sheer bliss! [2] // Problem 1763. Expert Flea 24 Oct 2017 05:37 (n-19>=7) start from 7... xurshid_n Re: Sheer bliss! [1] // Problem 1763. Expert Flea 31 Dec 2019 16:31 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 Gilles Deleuze Re: Sheer bliss! // Problem 1763. Expert Flea 31 Dec 2019 18:39 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 Znol Easy solution C++ // Problem 1902. Neo-Venice 31 Dec 2019 17:07 #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; } } } Znol Test 6 Access Violation // Problem 1001. Reverse Root 31 Dec 2019 14:43 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; } } Mickkie Minimum n for k=18 ? [1] // Problem 2049. Chemistry 30 Dec 2019 01:02 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 Mickkie Re: Minimum n for k=18 ? // Problem 2049. Chemistry 30 Dec 2019 20:46 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. anupam ghosh unable to understand first example. can anyone please kindly explain. // Problem 1671. Anansi's Cobweb 30 Dec 2019 17:16 unable to understand first example. can anyone please kindly explain. SMMaster So easy / phyton 3 solution // Problem 1021. Sacrament of the Sum 30 Dec 2019 14:32 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') bhn Test 8 python [6] // Problem 1196. History Exam 25 May 2016 14:36 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 Oleg Baskakov Re: Test 8 python [3] // Problem 1196. History Exam 25 May 2016 15:27 https://en.wikipedia.org/wiki/Binary_search_algorithm Study it. Good luck. Ilanya Klirik Re: Test 8 python [2] // Problem 1196. History Exam 16 Aug 2017 15:31 There is "Time limit exceeded" with binary search too. ivan228 Re: Test 8 python [1] // Problem 1196. History Exam 16 Oct 2018 20:34 i think that on python i wil not can solve this ToadMonster Re: Test 8 python // Problem 1196. History Exam 25 Oct 2018 13:11 ToadMonster Re: Test 8 python // Problem 1196. History Exam 26 May 2016 14:52 Probably you should use data structure with quick search, like python set/dictionary. https://docs.python.org/3/tutorial/datastructures.html SMMaster Re: Test 8 python // Problem 1196. History Exam 30 Dec 2019 14:31 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) Neeraj Kumar TLE #8: How can I make this Python code faster? [1] // Problem 1196. History Exam 3 Jan 2016 10:09 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) SMMaster Re: TLE #8: How can I make this Python code faster? // Problem 1196. History Exam 30 Dec 2019 14:30 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) SMMaster So easy / phyton 3 solution // Problem 1567. SMS-spam 29 Dec 2019 17:53 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) some_programming_novice Hint. // Problem 1059. Expression 29 Dec 2019 07:19 Horner's method. despair_101 Why Wrong Answer №6? // Problem 1263. Elections 28 Dec 2019 21:59 using System; namespace Training { class Program { static void Main(string[] args) { string[] n = Console.ReadLine().Split(' '); int N = Convert.ToInt32(n[0]); int M = Convert.ToInt32(n[1]); double cnt = 1; int arr = 0; int[] ans = new int[M]; double[] vs = new double[N]; for (int i = 0; i < M; i++) ans[i] = Convert.ToInt32(Console.ReadLine()); Array.Sort(ans); Array.Resize(ref ans, ans.Length+1); Console.WriteLine(); for (int j = 0; j < M; j++) { if (ans[j] == ans[j + 1]) cnt++; else { double x = Math.Round(cnt / M * 100, 2); if ((int)x == x) Console.WriteLine(x + ".00%"); else Console.WriteLine(x + "%"); arr++; cnt = 1; } } if (arr < N) for (int j = 0; j < N - arr; j++) Console.WriteLine("0.00%"); } } }
|