|
|
This codes gives correct output in my system but submitting it shows Restricted Function. Plz help... ************************************** import Queue graph={} dic={} to_explore=Queue.Queue() def BFS(root): dic[root]=0 to_explore.put(root) while not to_explore.empty(): tmp=to_explore.get() for i in graph[tmp]: if i not in dic: dic[i]=dic[tmp]+1 to_explore.put(i) n=input() while n: s=raw_input().split() for i in s: if i not in graph: graph[i]=[] for j in s: if j!=i: if j not in graph[i]: graph[i].append(j) else: for j in s: if j!=i: if j not in graph[i]: graph[i].append(j) n-=1 if 'Isenbaev' in graph: BFS('Isenbaev') for i in graph: if i not in dic: dic[i]='undefined' for i in sorted(dic): print i,dic[i] else: for i in sorted(graph): print i,"undefined" Don`t the queue module starts with lowercase letter? Looks like: from queue(module) import Queue(function) Actually, I have pretty similar code and always have runtime error on the very first test Edited by author 20.08.2023 18:32 Edited by author 20.08.2023 18:32 This case may help you: 2 A B C B D Isenbaev ans: A 2 B 1 C 2 D 1 Isenbaev 0 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 What is test 7? ___Test 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 ____correct 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 Thank you very much - I had WA7 and this test helped me very much. I realized that some of the numbers on my output were higher (I didn't take the shortest path in the graph). You need to take the shortest path and not the first path found. I have correct answers but still cannot pass test 7 [code deleted] Edited by moderator 19.11.2019 23:08 problem was caused by comments, removed them and everything worked can anybody help me with this problem? can somebody tell what kind of test is it Check array sizes. i have already checked. all right. maximum number of participants is 300. [code deleted] Edited by moderator 19.11.2019 23:09 Maybe you found the error, but i got stuck on this problem and tried your solution. I hoped to find the problem of my submission. When there are 300 different names without Isenbaev, your program added Isenbaev with number 301 and crashes because of the array index > 300 setting array to [1..301] did the trick and AC thank you! your reply help me a lot! thank you, you saved my day I can solve it by breadth-first search with Execution time:0.218, but how to solve it with Execution time:0.015 or 0.031??? I have no idea about it. Give me please idea or algorithm's name to solve it so fast. thank you! [code deleted] his work time 0.31 Edited by moderator 19.11.2019 23:11 You can solve fast using BFS)) [code deleted] work timeL 0.015 Edited by author 20.12.2018 15:38 Edited by moderator 19.11.2019 23:11 Somebody can give me test case 4? I don't understand why it's wrong answer... Edited by author 30.10.2018 11:59 Edited by author 01.11.2018 09:17 input file: 1 Isenbae Isen Isenbaeva and, what what is your answer? Edited by author 25.06.2013 19:22 Edited by author 25.06.2013 19:22 Edited by author 25.06.2013 19:23 Isen undefined Isenbae undefined Isenbaeva undefined Love you bro <3 that me helped input file: 1 Isenbae Isen Isenbaeva and, what what is your answer? Edited by author 25.06.2013 19:22 Edited by author 25.06.2013 19:22 Edited by author 25.06.2013 19:23 Thanks a lot... :) I have been struggling hard to overcome WA 3 ... And this test helped me to pass WA-3. good hint for a beginners as me. It's better to be careful with reading a problem) I think my idea completely right What's wrong?????? import java.util.Scanner; public class Main { public static void main(String [] args) { Scanner in = new Scanner(System.in); int n; n = in.nextInt(); String s[][] = new String[n][3]; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ s[i][j] = in.next(); } } boolean all[][] = new boolean[n][3]; String ss[][] = new String[3*n][3*n]; ss[0][0] = "Isenbaev"; int []index = new int[3*n]; for(int i=0;i<n;i++){ index[i] = 0; } index[0] = 1; int d = 1; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ if(s[i][j].equalsIgnoreCase("Isenbaev"))all[i][j] = true; } } boolean BOR = false; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ if(s[i][j].equalsIgnoreCase("Isenbaev"))BOR = true; } } for(int q=0;q<3*n;q++){ boolean bormi = false; for(int i=0;i<n;i++){ boolean bor = false; for(int j=0;j<3;j++){ for(int t=0;t<index[d-1];t++){ if(ss[d-1][t].equalsIgnoreCase(s[i][j])){ bor = true; break; } }if(bor)break; } if(bor){ for(int j=0;j<3;j++){ if(!all[i][j]){ ss[d][index[d]++] = s[i][j]; all[i][j] = true; bormi = true; for(int g=0;g<n;g++){ for(int h=0;h<3;h++){ if(s[g][h].equalsIgnoreCase(s[i][j]))all[g][h] = true; } } } } } } if(bormi)d++; } String []sss = new String[3*n]; int []son = new int[3*n]; for(int i=0;i<3*n;i++){ son[i] = -1; } int koef = 0; for(int i=0;i<d;i++){ if(i==0){ if(BOR){ BOR = false; }else i++; } for(int j=0;j<index[i];j++){ sss[koef] = ss[i][j]; son[koef++] = i; } } for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ if(!all[i][j]){ boolean top = true; for(int p=0;p<koef;p++){ if(sss[p].equalsIgnoreCase(ss[i][j]))top = false; } if(top)sss[koef++] = s[i][j]; } } } n = koef; for(int i=0;i<n-1;i++){ if(sss[i].compareTo(sss[i+1])>0){ String S = sss[i]; sss[i] = sss[i+1]; sss[i+1] = S; int SS = son[i]; son[i] = son[i+1]; son[i+1] = SS; i=-1; } } for(int i=0;i<koef;i++){ if(son[i]!=-1)System.out.println(sss[i] + " " + son[i]); else System.out.println(sss[i] + " undefined" ); } } } Edited by author 25.07.2018 00:30 Edited by author 27.07.2018 23:09 What is the test 19? Help please! Don't know, what's wrong. Give me tests please. Create three dictionaries : used <boolean> connections <set<string>> distance <string> Then import queue. Then breadth - first search. Edited by author 30.09.2013 09:17 Edited by author 30.09.2013 09:17 ___Test 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 ____correct 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 Other lexicographical order is correct also: 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 Rivest undefined RR 3 Samsonov 2 SS 3 Toropov 1 TT 2 You can see that Rivest undefined RR 3 Samsonov 2 SS 3 Toropov 1 TT 2 are ordered in other lexicographical order. You're wrong. Problem says: "The first letter of a name is capital and the other letters are lowercase", so tests can't contain names like these "RR, TT, AAA, etc.". 7 7 Isesnbaev Oparin Toropov Ayzenshteyn Oparin Samsonov Ayzenshteyn Chevdar Samsonov Fominykh Isesnbaev Oparin Dublennykh Fominykh Ivankov Burmistrov Dublennykh Kurpilyanskiy Cormen Leiserson Isenbaev test this case [code deleted] Edited by moderator 19.11.2019 23:13 check 1 a aa aaa answer a undefined aa undefined aaa undefined Test 3 is RTE What can I optimise? n=int(input()) dic={} for i in range(n): team=input().split() for x in team: if x in dic: dic[x].extend((y for y in team if y!=x and y not in dic[x])) else: dic[x]=[y for y in team if y!=x] names=sorted(dic.keys()) s='Isenbaev' level = { s: 0 } k = 1 frontier = [s] while frontier: next = [] for u in frontier: for v in dic[u]: if v not in level: level[v] = k next.append(v) frontier = next k += 1 print('\n'.join((x+' '+str(level.get(x, 'undefined')) for x in names))) Edited by author 09.08.2016 16:37 class Node: def __init__(self, name, number): self.name = name self.number = number self.children = [] def d(self, name): for i in self.children: if i.name == name: self.children.remove(i) for i in self.children: i.d(name)
def fnc(cmds, item, isenb, root): for c in cmds: if item.name in c: for n in c: if not n in isenb: isenb[n] = item.number + 1 item.children.append(Node(n, item.number + 1)) elif isenb[n] > (item.number + 1): isenb[n] = item.number + 1 root.d(n) item.children.append(Node(n, item.number + 1)) for i in item.children: fnc(cmds, i, isenb, root)
import sys if __name__=='__main__': n_command = input() if(int(n_command) > 0): isenb = {} cmds = [] for i in range(0,int(n_command)): cmds.append(input().split()) flag = False for c in cmds: if "Isenbaev" in c: flag = True break if flag: root = Node("Isenbaev", 0) isenb["Isenbaev"] = 0 fnc(cmds, root, isenb, root) for c in cmds: for i in c: if not i in isenb: isenb[i] = "underfined" s = '' for key,value in sorted(isenb.items()): if s == '': s += (str(key) + ' ' + str(value)) else: s += ('\n' + str(key) + ' ' + str(value)) sys.stdout.write(s) else: sys.stdout.flush() Why? My solution is ok when i run with other tests that i have seen in this forum, but when i submit here, i get WA#1! Is there a problem about the output? Thanks. BFS (Поиск в ширину). [code deleted] Edited by moderator 19.11.2019 23:14 |
|
|