Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Can someone give me some detailed explanations about his solutions to this problem? | aclsh | 1791. Дядя Стёпа и автобусы | 23 апр 2015 22:25 | 1 |
My email is 843539450@qq.com,Thank you very much~ |
WA17 | George Agapov | 1791. Дядя Стёпа и автобусы | 11 май 2014 14:17 | 3 |
WA17 George Agapov 31 окт 2010 02:19 Any ideas, what's wrong? (I used greedy alogorithm) I've this test wrong too. Here's my code: #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <utility> #include <set> #include <ctime> using namespace std; #define forn(i,n) for (int i = 0; i < (int)n; i++) struct bus { int l, r, type, num; friend bool operator<(const bus &bus1, const bus &bus2) { if (bus1.type != bus2.type) { return bus1.r < bus2.r; } else { return bus1.num < bus2.num; } } }; int n, m; vector<pair<int, int> > v1, v2; bus mas[300000]; multiset<bus> s; multiset<bus>::iterator iter; int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); scanf("%d", &n); v1.resize(n); forn(i,n) { scanf("%d%d", &v1[i].first, &v1[i].second); v1[i].second += v1[i].first - 1; } scanf("%d", &m); v2.resize(m); forn(i,m) { scanf("%d%d", &v2[i].first, &v2[i].second); v2[i].second += v2[i].first - 1; } for (int i = 1; i <= n; i++) { mas[i].l = v1[i - 1].first; mas[i].r = v1[i - 1].second; mas[i].type = 1; mas[i].num = i; } for (int i = 1; i <= m; i++) { mas[i + n].l = v2[i - 1].first; mas[i + n].r = v2[i - 1].second; mas[i + n].type = 2; mas[i + n].num = i; } int p1 = 1, p2 = n + 1; int t = min(mas[p1].l, mas[p2].l); while ((p1 <= n && p2 <= m + n) || t <= 230000000) { while (p1 <= n && mas[p1].l <= t) { if (mas[p1].r < t) { printf("NO"); return 0; } else { s.insert(mas[p1++]); } } while (p2 <= m + n && mas[p2].l <= t) { if (mas[p2].r < t) { printf("NO"); return 0; } else { s.insert(mas[p2++]); } } iter = s.begin(); if (iter != s.end()) { if ((*iter).r < t) { printf("NO"); return 0; } else { s.erase(iter); } t++; } else { t = 230000000; if (p1 <= n) { t = min(t, mas[p1].l); } if (p2 <= n + m) { t = min(t, mas[p2].l); } if (t == 230000000) { printf("YES"); return 0; } } } printf("YES"); //printf("%.5lf", 1.0 * clock() / (1.0 * CLOCKS_PER_SEC)); } Where's bug? Re: WA17 Vit Demidenko 11 май 2014 14:17 1 1 3 2 1 4 1 2 answer is "YES" |
how to solve with dp? | xurshid_n | 1791. Дядя Стёпа и автобусы | 24 апр 2012 19:13 | 3 |
Who can tell me , how to solve this problem with Dynamic programming? Ac!! after some correction! Hint: passed time and waited time need to corrected (i.e. change to real values) Write your e-mail. I help you. |
In the same order? | Newbies | 1791. Дядя Стёпа и автобусы | 19 апр 2012 00:15 | 2 |
"The buses running in one direction should pass the section under repair in the same order they approach it." Does it means that answer to: 2 1 2 1 1 1 2 2 will be NO? |
Anybody would like to share some ideas? Thanks. | [York Hotel] 3xian | 1791. Дядя Стёпа и автобусы | 16 янв 2011 21:36 | 7 |
Anybody would like to share some ideas? Thanks. Greedy algorithm. For every bus you can comptute "Critical time"=p[i]+t[i]-i. If 1st Bus from "Small Vasyuki" will pass the road after critical time of ith bus from "Small Vasyuki" then ith bus will be late. If jth bus from "Small Vasyuki" will pass the road after (critical time + j-1) then ith bus will be late. If k1-1 buses from "Small Vasyuki" passed and k2-1 buses from "Big Vasyuki" passed then buses from direction with lower critcaltime(of some bus)+k (k1 or k2) are prefered. Edited by author 17.10.2010 14:17 Let 'l' and 'r' be the waiting buses on each direction. Let l[i].f be l[i].t + l[i].p I define the priority between buses as follows: 1. If l[i].t < r[j].t then l[i] should pass first. 2. If l[i].t > r[j].t then r[j] should pass first. ELSE (l[i].t==r[j].t) 3. If l[i].f < r[j].f then l[i] should pass first. 4. If l[i].f > r[j].f then r[i] should pass first. ELSE (l[i].f==r[j].f) 5. If l[i+1] should pass before r[j+1] then l[i] should pass first, else r[j] Can anyone provide a counterexample for this approach? Thanks in advance. --- Nevermind, I was terribly wrong. Edited by author 18.10.2010 22:10 You said about greedy criterion as it is your discovery. More rightly to note math theorem, name of schedulling problem, article in wiki. We have two decks of cards. On each step we dicide from which of them to take one card. For decision we must compare two new states acording two way of choice. You formula is criterion of compairing. But prove is unknown and criterion may be very deep but not absolute greedy. Edited by author 19.10.2010 16:01 Consider the following algorithm: current_time = 0 While there are buses, select a bus i according to Avriskin's priority. If current_time + 1 > ti + pi then answer "NO" else current_time = max(current_time, ti) + 1 and erase the bus. Does anyone see something wrong? I used simple dynamic programming :) |
I ac | Ibragim Atadjanov (Tashkent U of IT) | 1791. Дядя Стёпа и автобусы | 23 окт 2010 15:12 | 9 |
I ac Ibragim Atadjanov (Tashkent U of IT) 20 окт 2010 11:27 At first I got wa on test 12 19 ... After this test I got ac 6 1 10 1 10 1 6 1 10 1 10 6 3 2 3 1 3 2 Edited by author 20.10.2010 14:21 Is the ans YES? But I wa on 10... Greedy... Re: I ac Ibragim Atadjanov 22 окт 2010 00:53 Edited by author 23.10.2010 03:27 That is also my way to greed I have done it but still wa Is there any tricks? Re: I ac Ibragim Atadjanov (Tashkent U of IT) 22 окт 2010 12:04 give me your email. I'll send you my code(in java) f4f4f404 at 163.com Thanks! I've sent (-) Ibragim Atadjanov (Tashkent U of IT) 23 окт 2010 02:24 Recieved. Thank you! I thought I misunderstood the problem's description... |
Simple Testcase | Alexander Georgiev | 1791. Дядя Стёпа и автобусы | 19 окт 2010 00:08 | 1 |
Be sure to pass the following testcase: 6 1 10 1 10 1 10 1 10 1 10 6 3 1 4 1 |
WA 12 | okulov-nikolay | 1791. Дядя Стёпа и автобусы | 18 окт 2010 13:37 | 1 |
WA 12 okulov-nikolay 18 окт 2010 13:37 |