1172 - The Bridges of Kolsberg

All about problems in Volume 11. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Degiac
New poster
Posts: 2
Joined: Thu Sep 04, 2014 11:41 pm
Location: Salerno, Italy
Contact:

Re: 1172 - The Bridges of Kolsberg

Post by Degiac » Wed Sep 17, 2014 10:39 pm

Has someone got some tricky test cases for this problem? I keep getting WA and I can't realize why. I wrote some test cases myself but I always get the right answer

EDIT: nvm, solved

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1172 - The Bridges of Kolsberg

Post by brianfry713 » Thu Sep 18, 2014 8:08 pm

I added some random input at:
http://www.udebug.com/UVa/1172
Check input and AC output for thousands of problems on uDebug!

bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 1172 - The Bridges of Kolsberg

Post by bradd123 » Sun Feb 22, 2015 3:28 pm

Hi, Can anybody tell me How to proceed to solve this problem? It looks like matching with some constraints. Please give me some hints?

Ahmad_Elsagheer
New poster
Posts: 3
Joined: Thu Jul 09, 2015 5:20 am

Re: 1172 - The Bridges of Kolsberg

Post by Ahmad_Elsagheer » Fri Aug 07, 2015 5:47 am

Hey guys,

I solved this problem and only got accepted after considering the constraint: no city could be an endpoint of more than one bridge. Does the problem description imply this constraint ? If anyone got accepted without considering such a constraint, I would appreciate telling me briefly his algorithm to look for my bug, if any.

Thanks

Shafayat
New poster
Posts: 7
Joined: Mon Jan 19, 2015 11:32 am

Re: 1172 - The Bridges of Kolsberg

Post by Shafayat » Fri Sep 09, 2016 4:28 pm

Why I'm getting WA?
I've submitted without comments.

Code: Select all

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;

struct bridge
{
    long long int cost;
    char city[1000],os[1000];
}le[1000],ri[1000];     //store inputs. 'le' for first bank and 'ri' for second bank

struct table
{
    long long int pos;
    long long int co;   // stores the cost
    long long int cou;  // count the bridge
}tab[1000][1000];         //table for current maximum cost and minimum number of bridge

/* in this solve function I use algorithm like coin change algorithm.
here, I create a table.
for all bridges in 're', i choose bridge from 'le' and find current maximum cost and minimum number of bridge.*/

void solve(long long int a,long long int b)
{
    memset(tab,0,sizeof(tab));
    for(long long int i=0;i<a;i++)     //Select bridge from le
    {
        for(long long int j=0;j<b;j++)   //Select bridge from re
        {
            if(strcmp(le[i].os,ri[j].os)==0)      // compare OS name
            {
                if((tab[i][j].co+le[i].cost+ri[j].cost)>tab[i][j+1].co && (tab[i][j].co+le[i].cost+ri[j].cost)>tab[i+1][j].co)  // check if (cost stored in previous diagonal cost from table+ cost of current bridge) is greater than cost stored in upward position and left position of the table
                {
                    tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
                    tab[i+1][j+1].pos=j+1;   // stores the position where I get current maximum
                    tab[i+1][j+1].cou=tab[i][j].cou+1;   // count the bridge number

                }
                else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i][j+1].co)   // if current cost and cost of upward position in table is same than choose that one which contains minimum number of bridge
                {
                    tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
                    if((tab[i][j].cou+1)<tab[i][j+1].cou)
                    {
                        tab[i+1][j+1].pos=j+1;
                        tab[i+1][j+1].cou=tab[i][j].cou+1;
                    }
                    else
                    {
                        tab[i+1][j+1].pos=tab[i][j+1].pos;
                        tab[i+1][j+1].cou=tab[i][j+1].cou;
                    }

                }
                else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i+1][j].co)  // if current cost and cost of left position in table is same
                {
                    tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
                    if((tab[i][j].cou+1)<tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].pos=j+1;
                        tab[i+1][j+1].cou=tab[i][j].cou+1;
                    }
                    else
                    {
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }

                }
                // conditions after this line works if (cost stored in previous diagonal cost from table+ cost of current bridge) is smaller than upward and left position
                else if(tab[i][j+1].co>tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i][j+1].co;
                    tab[i+1][j+1].pos=tab[i][j+1].pos;
                    tab[i+1][j+1].cou=tab[i][j+1].cou;
                }
                else if(tab[i][j+1].co<tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i+1][j].co;
                    tab[i+1][j+1].pos=tab[i+1][j].pos;
                    tab[i+1][j+1].cou=tab[i+1][j].cou;
                }
                else
                {
                    if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou<tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i][j+1].co;
                        tab[i+1][j+1].pos=tab[i][j+1].pos;
                        tab[i+1][j+1].cou=tab[i][j+1].cou;
                    }
                    else if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou>tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                    else
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                }
            }
            else    // if OS name does not matches than I choose from upward and left position
            {
                if(tab[i][j+1].co>tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i][j+1].co;
                    tab[i+1][j+1].pos=tab[i][j+1].pos;
                    tab[i+1][j+1].cou=tab[i][j+1].cou;
                }
                else if(tab[i][j+1].co<tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i+1][j].co;
                    tab[i+1][j+1].pos=tab[i+1][j].pos;
                    tab[i+1][j+1].cou=tab[i+1][j].cou;
                }
                else
                {
                    if(tab[i][j+1].cou<tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i][j+1].co;
                        tab[i+1][j+1].pos=tab[i][j+1].pos;
                        tab[i+1][j+1].cou=tab[i][j+1].cou;
                    }
                    else if(tab[i][j+1].cou>tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                    else
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                }
            }
        }
    }

}

int main()
{
    long long int a,b,c,d,e,f,g,h;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>a;
    for(b=1;b<=a;b++)
    {
        cin>>c;
        for(d=0;d<c;d++)
        {
            cin>>le[d].city>>le[d].os>>le[d].cost;
        }
        cin>>d;
        for(e=0;e<d;e++)
        {
            cin>>ri[e].city>>ri[e].os>>ri[e].cost;
        }
        solve(c,d);
        for(int i=0;i<=c;i++)
        {
            for(int j=0;j<=d;j++)
            {
                printf("%8lld-%lld ",tab[i][j].co,tab[i][j].cou);
            }
            cout<<endl;
        }
        printf("%lld %lld\n",tab[c][d].co,tab[c][d].cou);
    }
    return 0;
}


metaphysis
Experienced poster
Posts: 128
Joined: Wed May 18, 2011 3:04 pm

Re: 1172 - The Bridges of Kolsberg

Post by metaphysis » Mon Sep 10, 2018 4:00 pm

Be careful of the boundary condition.

muazuicom22
New poster
Posts: 25
Joined: Tue Sep 11, 2018 10:32 pm

Post by muazuicom22 » Sat Sep 29, 2018 6:14 pm

CTY TDL CHUYÊN NHẬN LÀM GIẤY TỜ :

Kính gửi Quý khách hàng , Cty TDL chúng tôi

Nhận làm tất cả các loại giấy tờ liên quan đến BĐS , từ dễ đến khó , khu vực Thành Phố HCM Và Bình Dương.
* Vẽ thiết kế xây dựng, xin giấy phép xây dựng.
* Vẽ hiện trạng đo đạc nhà đất, nhà máy, nhà xưởng.
*Dịch vụ thiết kế Phòng cháy, chữa cháy và Thẩm duyệt.
* Dịch vụ xin chuyển mục đích sử dụng đất.
* Dịch vụ hoàn công nhà xưởng, công trình trên đất.
* Dịch vụ tách thửa sổ đỏ, nhà đất, nhà xưởng, nhà máy.
* Dịch vụ xin cấp mới sổ đỏ, sổ hồng hoặc xin cấp Giấy chứng nhận Quyền sử dụng đất, quyền sở hữu nhà ở và tài sản khác gắn liền với đất.
* Dịch vụ xác định lại ranh giới, thực trạng nhà đất, cấp sổ mới.
* Dịch vụ xem xét lại quy hoạch xây dựng.
* Dịch vụ hợp thức hóa nhà đất.
* Dịch vụ sang tên , đăng bạ sang tên chủ quyền, thừa kế di chúc.


Ai có nhu cầu liên hệ 0938.242.835 c.Hong.
Quý khách Lưu lại khi cần . Trân trọng cảm ơn. Uy Tin_ chinh chuan.
Chúc Anh chị một ngày tốt lành

Post Reply

Return to “Volume 11 (1100-1199)”