299 - Train Swapping

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

Moderator: Board moderators

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

Re: 299 why worng answer? please help me

Post by brianfry713 » Wed Feb 12, 2014 12:17 am

If L is 0 there is probably a blank line after it, as "Each test case consists of two input lines."
You're not printing the period at the end of the line.
Check input and AC output for thousands of problems on uDebug!

ltanure
New poster
Posts: 1
Joined: Mon Apr 28, 2014 7:33 pm

299 Runtime Error.

Post by ltanure » Mon Apr 28, 2014 7:38 pm

I tested this code some many times. I can't get why is runtime error.
There is no way this could be wrong. I tested with the 299_input.zip that has 10000 inputs.

I always get this :

Hi,

This is an automated response from UVa Online Judge.

Your submission with number 13559676 for the problem 299 - Train Swapping has failed with verdict Runtime error.

This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.

Best regards,

The UVa Online Judge team

My code :

################################################
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

#define MAX_LINE_SIZE 2500

typedef struct _node {
int x;
struct _node *next;
struct _node *previous;
} Node;
Node * root = NULL;
Node * tail = NULL;
int list_length = 0;


void free_list(){
Node * tmp = tail;
while(tmp != NULL){
tail = tmp->previous;
free(tmp);
tmp = tail;
list_length--;
}
root = NULL;
tail = NULL;
list_length = 0;
}

int is_ordened(){
Node * tmp = root;
while(tmp->next != NULL){
if(tmp->x > (tmp->next)->x){
return 0;
}
tmp = tmp->next;
}
return 1;
}

Node * find_max(int * pos){
Node * tmp = root;
Node * max_add = NULL;
int max = -1;
int position = 0;

while(tmp != NULL){
if(tmp->x > max){
max_add = tmp;
max = tmp->x;
(*pos) = position;
}
tmp = tmp->next;
position++;

}
return max_add;
}

void remove_number(Node * item){
if(item->next != NULL){
(item->next)->previous = item->previous;
} else {
tail = item->previous;
}
if(item->previous != NULL){
(item->previous)->next = item->next;
} else {
root = item->next;
}
free(item);
list_length--;
}

void add_number(int number){
Node * new = (Node *) malloc(sizeof(Node));
new->x = number;
new->next = NULL;
if(root == NULL){
root = new;
tail = new;
new->previous = NULL;
}else{
tail->next = new;
new->previous = tail;
tail = new;
}
list_length++;
}

int read_int_ptr(char * str, int * pos){
int number = 0;
while(str[*pos]!='\0' && str[*pos] != ' ' && str[*pos] != '\n'){
number = (number*10) + (str[*pos]-48);
(*pos)++;
}
(*pos)++;
return number;
}

int read_int(char * str){
int zero = 0;
return read_int_ptr(str,&zero);
}

void read_int_vet(char * str, int len){
int i= 0;
int pos = 0;
for(i=0;i<len;i++){
add_number(read_int_ptr(str,&pos));
}
}

int optimum_swaps(){
int pos = 0;
int swaps = 0;

while(list_length>0){
if(is_ordened()){break;}
Node * tmp = find_max(&pos);
swaps += list_length-(pos+1);
remove_number(tmp);
}
return swaps;
}

int main(){
char * ret;
char buffer[MAX_LINE_SIZE];
ret = fgets(buffer, MAX_LINE_SIZE, stdin);
int total_cases = read_int(buffer);
int len = 0;
int i = 0;
for(i=0;i<total_cases;i++){
ret = fgets(buffer, MAX_LINE_SIZE, stdin);
len = read_int(buffer);
ret = fgets(buffer, MAX_LINE_SIZE, stdin);
read_int_vet(buffer, len);
printf("Optimal train swapping takes %d swaps.\n",optimum_swaps());
free_list();
}
return(0);
}
Attachments
299_input.zip
input tested
(22.76 KiB) Downloaded 82 times

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

Re: 299 Runtime Error.

Post by brianfry713 » Tue Apr 29, 2014 9:43 pm

It seems the input specification is wrong and you can't read line by line on this problem. Replace fgets with scanf and you'll get AC.
Check input and AC output for thousands of problems on uDebug!

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

299 - Train Swapping

Post by ehsanulbigboss » Sat Sep 06, 2014 11:10 pm

:oops:
Last edited by ehsanulbigboss on Thu Feb 05, 2015 10:05 pm, edited 1 time in total.

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

Re: 299 - Train Swapping

Post by brianfry713 » Mon Sep 08, 2014 8:56 pm

Next time post in the existing thread.
Your code doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

SunNEET
New poster
Posts: 1
Joined: Wed Jul 16, 2014 8:27 am

Re: 299 - Train Swapping

Post by SunNEET » Tue Mar 03, 2015 5:43 am

I used similar code to solve UVa 10810,11858,11495
I don't know why i keep getting RuntimeError in this problem :(
Have already tried the large input above(299_input.zip) and i got the same output with uDebug

Code: Select all

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
ll Count;

vll merge(vll &vec,const vll& left,const vll& right)
{
    vll result ;
    ll left_it=0,right_it=0;
    while(left_it < left.size() && right_it < right.size()){
        if(left[left_it] > right[right_it]){
            result.push_back(right[right_it]);
            right_it++;
            Count += left.size() - left_it;
        }
        else{
            result.push_back(left[left_it]);
            left_it++;
        }
    }
    while(left_it<left.size()){
        result.push_back(left[left_it]);
        left_it++;
    }
    while(right_it<right.size()){
        result.push_back(right[right_it]);
        right_it++;
    }
    vec = result;
    return vec;
}

vll merge_sort(vll &vec)
{
    if(vec.size()==1)
        return vec;

    vll::iterator middle = vec.begin() + vec.size()/2;
    
    vll left(vec.begin(),middle);
    vll right(middle,vec.end());

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(vec,left,right);
}




int main()
{
    //freopen("in","r",stdin);
    int N,n;
    scanf("%d",&N);
    while(N--){
        vll v;
        ll tmp;
        scanf("%d",&n);
        Count = 0;
        for(int i=0;i<n;i++){
            scanf("%lld",&tmp);
            v.push_back(tmp);
        }
        merge_sort(v);
        printf("Optimal train swapping takes %lld swaps.\n",Count);
    }
    return 0;
}

risk1996
New poster
Posts: 1
Joined: Fri Oct 23, 2015 8:19 am

Re: 299 - Train Swapping

Post by risk1996 » Fri Oct 23, 2015 8:22 am

Can anyone help me?
I've tried it twice and still getting WA.
I didn't forget to add the period and have tried to limit the train to 50.

Code: Select all

AC

Post Reply

Return to “Volume 2 (200-299)”