12150 - Pole Position

All about problems in Volume 121. 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
Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

12150 - Pole Position

Post by Kenpachi24 » Wed Dec 11, 2013 6:57 am

In this problem, We have 3 variables

N= (2 ? N ? 10^3)
C= (1 ? C ? 10^4)
P= ( -10^6 ? P ? 10^6)

I think that the the variable P can not take values higher or lower outside the range of absolute value N. ----- P= ( -10^4 ? P ? 10^4)

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

Re: Problem UVA 12150 - Pole Position

Post by brianfry713 » Thu Dec 12, 2013 9:26 pm

If the value of P would cause that car to be outside the starting grid or two cars map to the same starting grid position then that test case is invalid and you should print -1.
Check input and AC output for thousands of problems on uDebug!

cse dipto
New poster
Posts: 22
Joined: Tue Oct 29, 2013 6:46 pm

Re: Problem UVA 12150 - Pole Position get WA! plz help

Post by cse dipto » Tue May 06, 2014 7:47 pm

Code: Select all

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <sstream>
#include <utility>
#define size 10000

using namespace std;

pair<long long int , long long int> p[size] ;
long long int grid[size] ;

int main()
{
    long long int i,j,k,t_case,car_no,pos,tmp,pos2,flag ;
    while(cin >> t_case)
    {
        memset(grid , 0 , sizeof(grid)) ;
        if(t_case == 0)
            break ;
        for(i = 0 ; i < t_case ; i++)
        {
            cin >> car_no >> pos ;
            p[i] = make_pair(car_no , pos) ;
        }
        for(i = 0 ; i < t_case ; i++)
        {
            flag = 1 ;
            pos2 = 0 ;
            tmp = p[i].second ;
            if(tmp > (t_case - 1))
            {
                //cout << p[i].first << " " ;
                flag = 0 ;
                printf("-1\n") ;
                break ;
            }
            else if(tmp < 0)
            {
                tmp = (tmp * (-1)) ;
                pos2 = i - tmp ;
                if(pos2 < 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[pos2] != 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[pos2] == 0)
                {
                    grid[pos2] = p[i].first ;
                }
            }
            else if(tmp > 0)
            {
                pos2 = i + tmp ;
                if(grid[pos2] != 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[pos2] == 0)
                {
                    grid[pos2] = p[i].first ;
                }
            }
            else if(tmp == 0)
            {
                if(grid[i] != 0)
                {
                    //cout << p[i].first << " " ;
                    flag = 0 ;
                    printf("-1\n") ;
                    break ;
                }
                if(grid[i] == 0)
                {
                    grid[i] = p[i].first ;
                }
            }
        }
        if(flag != 0)
        {
            for(i = 0 ; i < t_case ; i++)
            {
                cout << grid[i] ;
                if(i != (t_case -1))
                {
                    cout << " " ;
                }
            }
            cout << endl ;
        }
    }
    return 0;
}

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: Problem UVA 12150 - Pole Position get WA! plz help

Post by lbv » Wed May 07, 2014 2:08 am

cse dipto wrote:code omitted
You may try these cases:

Input

Code: Select all

3
20 0
10 2
30 0
5
47 4
64 1
81 1
58 3
52 -4
0
Output

Code: Select all

-1
-1

cse dipto
New poster
Posts: 22
Joined: Tue Oct 29, 2013 6:46 pm

Re: Problem UVA 12150 - Pole Position

Post by cse dipto » Wed May 07, 2014 4:30 pm

@lbv thnks a lot bro :D got AC thnks again and you are great and also your's counter test cases thnks :D

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 12150 - Pole Position

Post by anacharsis » Tue Aug 18, 2015 6:06 am

I don't understand the second test case in the problem statement.

4
22 1
9 1
13 0
21 -2

The answer is given as -1 in the sample output.
But, isn't the following a valid starting grid for this case:
21 9 22 13

Any help appreciated!

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 12150 - Pole Position

Post by anacharsis » Thu Aug 20, 2015 3:31 pm

Actually, never mind; I misunderstood the problem.
I thought that the car and position g/l information had been garbled.
It's not - the input is the current pole.
You just have to reconstruct the starting grid, which is a much easier problem than I tried to solve... :)

Post Reply

Return to “Volume 121 (12100-12199)”