Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Please give me a test with"No Solution" | Yrii | 1042. Центральное отопление | 18 ноя 2021 20:39 | 6 |
Re: Ivan Georgiev 15 фев 2002 23:17 There is always a solution and it is always only one -- you have n linear independent vectors (that is the determinant of the linear system is <> 0) and using Cramer's rule you have a single solution. Re: Vinicius Fortuna 7 мар 2002 00:54 But they are modular equations. Is Cramer's rule still valid for such equations? > There is always a solution and it is always only one -- > > you have n linear independent vectors (that is the determinant of the > linear system is <> 0) and using Cramer's rule you have a single > solution. Ok I understand that but i decided that there are bugs in my proof so ... 3 1 2 -1 2 3 -1 2 3 -1 Edited by author 17.07.2010 19:16 Edited by author 17.07.2010 19:16 |
Runtime error (access violation) #8 | Andor Vari-Kakas | 1042. Центральное отопление | 5 фев 2019 02:27 | 1 |
|
Getting WA#2 | Anand Zutshi | 1042. Центральное отопление | 4 дек 2016 10:10 | 1 |
ll n; ll ar[300][300]; int main(){ cin >> n; for(ll i = 1; i <= n; i ++) for(ll j = 1; j <= n; j ++) ar[i][j] = 0; for(ll i = 1; i <= n; i ++){ while(1){ ll x; cin >> x; if(x == -1) break; ar[x][i] = 1; } } for(ll i = 1; i <= n; i ++) ar[i][n+1] = 1; ll col = 1; while(col <= n){ if(ar[col][col] == 1){ for(ll i = 1; i <= n; i ++){ if(i == col) continue; if(ar[i][col] == 1){ //choose ith row for(ll j = 1; j <= n+1; j ++) ar[i][j] = ar[i][j]^ar[col][j]; } } } else{ break; } col ++; } bool f = 1; ll br[300][300]; for(ll i = 1; i <= n; i ++) for(ll j = 1; j <= n; j ++) if(i==j) br[i][j] = 1; for(ll i = 1; i <= n; i ++){ for(ll j = 1; j <= n; j ++) if(ar[i][j]!=br[i][j]) f = 0; } if(!f) cout << "No solution" << endl; else{ for(ll i = 1; i <= n; i ++){ if(ar[i][n+1]==1) cout << i << " "; } } return 0; } I have used basic Gauss algorithm making the augmented matrix equal to an identity matrix. Still getting WA. Please help Thank you :) Edited by author 04.12.2016 10:11 |
what is test3???I couldn't be wrong! | Childish | 1042. Центральное отопление | 10 сен 2012 18:59 | 1 |
|
Hint | hoan | 1042. Центральное отопление | 13 апр 2012 15:20 | 3 |
Hint hoan 14 дек 2010 23:48 there is only one answer or no answer, therefor if the solution exist it's the shortest. hope can help you. GOOD LUCK!!! Re: Hint Tony Beta Lambda 18 фев 2012 10:58 No, consider the following case: 3 1 -1 1 -1 1 2 3 -1 both 3 and 1 2 3 are correct answer but 3 is the shortest. Read the description carefully! Your case is wrong because technician 1 and 2 can replace each other! As the condition indicates that these vectors are linear independent, it's likely that there be zero or one solution. |
Solution | askhatik | 1042. Центральное отопление | 1 мар 2012 04:29 | 1 |
let's assume that a1, a2, a3,...an are will mean the relation of first mechanic to valves, b1, b2, b3, b4...bn are relation of second mechanic to valves, i.e if a1 = 1 then first mechanic must switch the first valve, else no. let's assume that x1 means whether mechanic to send to switch his valves, x2 for 2-nd mech, so on... then it's obvious that a1 * x1 + a2 * x2 + a3 * x3..... = 1 mod 2 b1 * x1 + b2 * x2+ b3 * x3 .... = 1 mod 2 ,...... this Linear system equation can be solved by Gaussian algorithm we need to find only x1, x2, x3,,,, where if xi (1<= i <= n) is 1 then we will send him, otherwise no. if the determinant is 0, then No solution...
|
who can tell me why there is no 'No solution' | sNow.orz | 1042. Центральное отопление | 27 фев 2012 03:06 | 2 |
There is no any test for "No solution" :) I forgot about this case, but had AC :) |
How to choose from answers the shortest one ? | nc | 1042. Центральное отопление | 3 янв 2011 14:28 | 1 |
we make equations for the input 3 1 3 -1 2 -1 1 2 3 -1 whe construct the maxtrix 1 0 1 = 1 0 1 1 = 1 1 0 1 = 1 The two answers 1 2 and 3 which is right ? |
How to choose from answers the shortest one? | Aram Shatakhtsyan | 1042. Центральное отопление | 30 сен 2010 17:52 | 2 |
This problem can be solved by equations, for example we make equations for the input: 3 1 2 -1 1 2 3 -1 3 -1 whe construct the matrix 1 1 0 = 1 1 1 0 = 1 0 1 1 = 1 since 1st and 2nd equations are the same, it means that you are free to choose the value for the 3rd variable, but in fact if you choose its value arbitrarily, answer length can be changed, two possible answers are 1,2 and 3, but only 3 is the right answer, because it's the shortest. What to do with that? this test is incorrect, because 1 combine 3 = 2 |
This is a beautiful problem!!!I'm really happy that i got AC | King Without Kingdom | 1042. Центральное отопление | 24 июл 2010 19:57 | 3 |
|
WA 7 C++ Help... | Kenny | 1042. Центральное отопление | 9 сен 2008 19:36 | 1 |
Em.... Got AC... Edited by author 29.09.2008 19:39 |
I only use full search and I got AC in 0.015 sec. | Y.Y.M. | 1042. Центральное отопление | 20 июл 2008 10:03 | 4 |
We can prove that nobody will turn the vales more than once, beacuse if so,he will do things with no effect so that the answer will not be the best one. So there are 2^N situations. I only use search with cut some "bad" answer and got AC. Sorry for my bad English... I also tried this method and got TLE. Can you give me your code? My e-mail is barssimfi@mail.ru Could you paste your code here? What is "bad" in your opinion? |
Why WA6? | Neizvestnii | 1042. Центральное отопление | 12 окт 2007 21:17 | 6 |
Please help!!! Give me Test#6 please!!! Please anybody help me........ This is my code: const maxn=2510; var n,i,j:longint; sol,a:array[0..maxn,0..maxn] of longint; lines:array[0..maxn] of longint; function aor(a:longint):boolean; begin if a<>0 then result:=true else result:=false; end; procedure ReadInput; var i,j:longint; begin readln(n); for i:=1 to n do begin while true do begin read(j); if j=-1 then begin readln; break; end; a[j,i]:=1; end; a[i,0]:=1; end; end; procedure Solve; var i,j,k,ok:longint; begin for i:=1 to n-1 do begin ok:=1; for j:=1 to n do if (not(aor(Lines[j]))) and (aor(A[j][i])) then begin ok:=0; break; end; Lines[j]:=1; for k:=0 to n do begin if k=i then sol[i,k]:=0 else sol[i,k]:=a[j,k]; end; for k:=1 to n do begin if (not(aor(Lines[k]))) and (aor(A[k][i])) then begin a[k,i]:=0; for j:=0 to n do a[k,j]:=a[k,j] xor sol[i,j]; end; end; end; sol[n,0]:=a[n,0]; for i:=n downto 0 do for j:=i-1 downto 0 do if aor(sol[j,i]) then begin sol[j,i]:=0; sol[j,0]:=sol[j,0] xor sol[i,0]; end; for i:=1 to n do if aor(sol[i,0]) then write(i,' '); end; begin {$IFNDEF ONLINE_JUDGE} reset(input,'input.txt'); rewrite(output,'output.txt'); {$ENDIF} ReadInput; Solve; {$IFNDEF ONLINE_JUDGE} close(output); {$ENDIF} end. Edited by author 24.06.2007 19:25 Big thanks to Alias (Alexander Prudaev) for his help in finding my stupid bug!)) AlexF [USTU Frogs] please say, why i get wa#6. Incorrect algo or program? Anybody say me, why I have WA#6? By bug were in Gauss) Just incorrect place of "}". This problem is just Gauss)Nothing special. GL) |
I've got AC 0.001s 158 КБ using Gauss. Who has better solution? | Daniel Neiter | 1042. Центральное отопление | 21 мар 2007 09:46 | 4 |
Edited by author 20.07.2006 19:13 20 июл 2006 reiten C++ 0.031 236 КБ You LIER :) |
Where can I read about my solution?(+) | SPIRiT | 1042. Центральное отопление | 29 янв 2007 21:18 | 1 |
Thanks to the ideas on the forum I solved this task with Hauss-Jordan and XOR's. However, this is my first solution which correctness I can't prove! Where can I read in the Internet about linear equations mod 2 theory? Thanks in advance... |
Problem 1042 "Central heating" has been rejudged (+) | Vladimir Yakovlev (USU) | 1042. Центральное отопление | 20 янв 2007 17:45 | 1 |
New tests has been added TL has been decreased to 1 second 141 authors lost AC |
what is in test 3 ? I always wa here.. | mai | 1042. Центральное отопление | 19 май 2006 20:05 | 4 |
4 2 3 4 -1 2 -1 4 -1 1 2 -1 Edited by author 30.01.2005 20:15 my wa program give:1 2 4? Hi! I'm also having troubles with test 3. Here's my code. I've already gotten AC with a very similar code that uses integers and XOR operations, but I want to know why it won't work with floats. Thanks! [code deleted] Edited by moderator 09.12.2019 18:46 |
Help me to solve this problem, please! | Aleksei Zobnin | 1042. Центральное отопление | 27 мар 2006 18:56 | 4 |
But it seems to me that in some situations my program doesn't work properly. For example, when the rank of matrix is less than n, there are several solutions. I didn't choose the shortest one of them, but nevertheless I've got AC. There can't be more than one solution ;-) Because if there could, some group of workers could do the same work as the other. >It is well known that every technician earns his money not in vain so it’s impossible to replace any technician by any combination of other technicians. PS Sorry for bad english |
What does it mean? | Sid | 1042. Центральное отопление | 24 июн 2005 23:11 | 2 |
What does it mean?...It is well known that every technician earns his money not in vain so it’s impossible to replace any technician by any combination of other technicians... So is such test correct? 4 1 2 3 -1 2 3 4 -1 2 3 -1 1 2 3 4 -1 Certainly NOT! You can fire the last technician (-: The first three working altogether will do his work. |
How about this test data?Have solution?? | daizi sheng(from USTC) | 1042. Центральное отопление | 16 май 2004 17:55 | 3 |
No.1 and No.2 can make combination to No.3. So this input is incorrect. |